Companies can greatly reduce IT costs by offloading data and computation to cloud computing services. Still, many companies are reluctant to do so, mostly due to outstanding security concerns. A recent study [2] surveyed more than 500 chief executives and IT managers in 17 countries, and found that despite the potential benefits, executives “trust existing internal systems over cloud-based systems due to fear about security threats and loss of control of data and systems”. One of the most serious concerns is the possibility of confidentiality violations. Either maliciously or accidentally, cloud provider’s employees can tamper with or leak a company’s data. Such actions can severely damage the reputation or finances of a company. In order to prevent confidentiality violations, cloud services’ customers might resort to encryption. While encryption is effective in securing data before it is stored at the provider, it cannot be applied in services where data is to be computed, since the unencrypted data must reside in the memory of the host running the computation. In Infrastructure as a Service (IaaS) cloud services such as Amazon’s EC2, the provider hosts virtual machines (VMs) on behalf of its customers, who can do arbitrary computations. In these systems, anyone with privileged access to the host can read or manipulate a customer’s data. Consequently, customers cannot protect their VMs on their own. Cloud service providers are making a substantial effort to secure their systems, in order to minimize the threat of insider attacks, and reinforce the confidence of customers. For example, they protect and restrict access to the hardware facilities, adopt stringent accountability and auditing procedures, and minimize the number of staff who have access to critical components of the infrastructure [8]. Nevertheless, insiders that administer the software systems at the provider backend ultimately still possess the technical means to access customers’ VMs. Thus, there is a clear need for a technical solution that guarantees the confidentiality and integrity of computation, in a way that is verifiable by the customers of the service