How to Run Turing Machines on Encrypted Data
Abstract. Algorithms for computing on encrypted data promise to be a funda-mental building block of cryptography. The way one models such algorithms has a crucial effect on the efficiency and usefulness of the resulting cryptographic schemes. As of today, almost all known schemes for fully homomorphic encryption, functional encryption, and garbling schemes work by modeling algorithms as circuits rather than as Turing machines. As a consequence of this modeling, evaluating an algorithm over encrypted data is as slow as the worst-case running time of that algorithm, a dire fact for many tasks. In addition, in settings where an evaluator needs a description of the algorithm itself in some “encoded ” form, the cost of computing and communicating such encoding is as large as the worst-case running time of this algorithm. In this work, we construct cryptographic schemes for computing Turing machines on encrypted data that avoid the worst-case problem. Specifically, we show: – An attribute-based encryption scheme for any polynomial-time Turing machine and Random Access Machine (RAM).