CISPA
Browse
2023-502.pdf (586.64 kB)

Laconic Function Evaluation for Turing Machines.

Download (586.64 kB)
preprint
posted on 2024-03-25, 12:54 authored by Nico Döttling, Phillip Gajland, Giulio Malavolta

 

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.

 

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

BibTeX

@misc{Döttling:Gajland:Malavolta:2023, title = "Laconic Function Evaluation for Turing Machines.", author = "Döttling, Nico" AND "Gajland, Phillip" AND "Malavolta, Giulio", year = 2023, month = 5 }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC