From financial information and medical records to shopping habits and Internet searches, computing devices are the virtual containers of the sensitive data of millions of users. At the same time, the proliferation of recent attacks on privacy, such as state-wide surveillance attempts revealed from whistle-blower cases, federal agencies compelling private companies to sign unsafe software, and high-profile compromises to cloud service providers, have significantly decreased trust on behalf of the users. A root cause to these problems is that modern computer architectures have always been designed for performance, and security protections are traditionally addressed as patches, continuously trying to outsmart adversaries.

To address this problem, we introduce a novel model of computation where data is manipulated directly in encrypted form, using the power of additive homomorphic encryption. Our objective is to support private and trustworthy computation that is as powerful as a traditional Turing machine. Towards that end, we offer three abstract machine variants that are based on a single-instruction computer architecture and use modular multiplication as the core homomorphic operation. Each variant offers different tradeoffs with respect to runtime memory requirements and performance overheads. Our key observation is that outsourced computation is no longer vulnerable to side-channel leakage or hardware Trojans, if sensitive information remains in encrypted format during processing.

Moreover, to enhance the trustworthiness of outsourced computation in our model, we present two integrity frameworks that enable real-time detection of computation errors. The first framework extends residue numbering to modular multiplication and uses homomorphic syndromes to detect random errors in homomorphic operations and homomorphic ciphertexts in memory. The second framework generalizes our security assumptions to active adversaries and introduces selectively-malleable keyed syndromes that enable authentication of encrypted memories, while maintaining compatibility with our random-error detection requirements. An important benefit of our cryptographic primitives is their implementation efficiency and hardware-friendliness.