Paper 2018/908

FE and iO for Turing Machines from Minimal Assumptions

Shweta Agrawal and Monosij Maitra


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 [KLW15, AJS17] require sub-exponentially secure iO for circuits, which in turn requires sub-exponentially secure FE for circuits [AJ15, BV15]. 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 [AS16] 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 [BGJS15] 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 [KLW15, AS16, AJS17].

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2018
indistinguishability obfuscationfunctional encryptionTuring machines
Contact author(s)
shweta a @ gmail com
monosij maitra @ gmail com
2018-09-28: revised
2018-09-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shweta Agrawal and Monosij Maitra},
      title = {FE and iO for Turing Machines from Minimal Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/908},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.