Cryptology ePrint Archive: Report 2018/908

FE and iO for Turing Machines from Minimal Assumptions

Shweta Agrawal, Monosij Maitra

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 [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].

Category / Keywords: indistinguishability obfuscation, functional encryption, Turing machines

Original Publication (with major differences): IACR-TCC-2018

Date: received 25 Sep 2018, last revised 28 Sep 2018

Contact author: shweta a at gmail com, monosij maitra at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180928:072709 (All versions of this report)

Short URL: ia.cr/2018/908


[ Cryptology ePrint archive ]