International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

FE and iO for Turing Machines from Minimal Assumptions

Authors:
Shweta Agrawal
Monosij Maitra
Download:
DOI: 10.1007/978-3-030-03810-6_18
Search ePrint
Search Google
Conference: TCC 2018
Abstract: We construct Indistinguishability Obfuscation (iO) and Functional Encryption (FE) schemes in the Turing machine model from the minimal assumption of compact FE for circuits (CktFE). Our constructions overcome the barrier of sub-exponential loss incurred by all prior work. Our contributions are:1.We construct iO in the Turing machine model from the same assumptions as required in the circuit model, namely, sub-exponentially secure FE for circuits. The previous best constructions [6, 41] require sub-exponentially secure iO for circuits, which in turn requires sub-exponentially secure FE for circuits [5, 15].2.We provide a new construction of single input FE for Turing machines with unbounded length inputs and optimal parameters from polynomially secure, compact FE for circuits. The previously best known construction by Ananth and Sahai [7] relies on iO for circuits, or equivalently, sub-exponentially secure FE for circuits.3.We provide a new construction of multi-input FE for Turing machines. Our construction supports a fixed number of encryptors (say k), who may each encrypt a string xi of unbounded length. We rely on sub-exponentially secure FE for circuits, while the only previous construction [10] relies on a strong knowledge type assumption, namely, public coin differing inputs obfuscation. Our techniques are new and from first principles, and avoid usage of sophisticated iO specific machinery such as positional accumulators and splittable signatures that were used by all relevant prior work [6, 7, 41].
BibTeX
@inproceedings{tcc-2018-29020,
  title={FE and iO for Turing Machines from Minimal Assumptions},
  booktitle={Theory of Cryptography},
  series={Theory of Cryptography},
  publisher={Springer},
  volume={11240},
  pages={473-512},
  doi={10.1007/978-3-030-03810-6_18},
  author={Shweta Agrawal and Monosij Maitra},
  year=2018
}