Laconic Function Evaluation for Turing Machines

Abstract

Laconic function evaluation (LFE) allows Alice to compress a large circuit C into a small digest d. Given Alice’s digest, Bob can encrypt some input x under d in a way that enables Alice to recover C(x), without learning anything beyond that. The scheme is said to be laconic if the size of d, the runtime of the encryption algorithm, and the size of the ciphertext are all sublinear in the size of C. Until now, all known LFE constructions have ciphertexts whose size depends on the depth of the circuit C, akin to the limitation of levelled homomorphic encryption. In this work we close this gap and present the first LFE scheme (for Turing machines) with asymptotically optimal parameters. Our scheme assumes the existence of indistinguishability obfuscation and somewhere statistically binding hash functions. As further contributions, we show how our scheme enables a wide range of new applications, including two previously unknown constructions:
– Non-interactive zero-knowledge (NIZK) proofs with optimal prover complexity.
– Witness encryption and attribute-based encryption (ABE) for Turing machines from falsifiable assumptions.