Paper 2023/502

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

Laconic function evaluation (LFE) allows Alice to compress a large circuit $\mathbf{C}$ into a small digest $\mathsf{d}$. Given Alice's digest, Bob can encrypt some input $x$ under $\mathsf{d}$ in a way that enables Alice to recover $\mathbf{C}(x)$, without learning anything beyond that. The scheme is said to be $laconic$ if the size of $\mathsf{d}$, the runtime of the encryption algorithm, and the size of the ciphertext are all sublinear in the size of $\mathbf{C}$. Until now, all known LFE constructions have ciphertexts whose size depends on the $depth$ of the circuit $\mathbf{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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2023
Laconic Function EvaluationTuring MachinesIndistinguishability Obfuscation
Contact author(s)
doettling @ cispa de
phillip gajland @ mpi-sp org
giulio malavolta @ mpi-sp org
2023-04-07: approved
2023-04-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nico Döttling and Phillip Gajland and Giulio Malavolta},
      title = {Laconic Function Evaluation for Turing Machines},
      howpublished = {Cryptology ePrint Archive, Paper 2023/502},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.