International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Laconic Function Evaluation for Turing Machines

Nico Döttling , CISPA Helmoltz Center for Information Security
Phillip Gajland , Max Planck Institute for Security and Privacy / Ruhr-University Bochum
Giulio Malavolta , Max Planck Institute for Security and Privacy
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
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.
  title={Laconic Function Evaluation for Turing Machines},
  author={Nico Döttling and Phillip Gajland and Giulio Malavolta},