Welcome to the resource topic for 2023/502
Title:
Laconic Function Evaluation for Turing Machines
Authors: Nico Döttling, Phillip Gajland, Giulio Malavolta
Abstract: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.
ePrint: https://eprint.iacr.org/2023/502
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .