Paper 2018/908

FE and iO for Turing Machines from Minimal Assumptions

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

Note: The proof of Theorem 3.1 (provided partly in Section 3.3 and in Appendix B respectively) contains a subtle bug that breaks the indistinguishability chain of TMFE. At a high level, this is caused by propagating the data structure Trap_b (for the challenge bit b \in {0, 1}) through the 1FE_1 and 1FE_2 ciphertexts across the entire computation chain; this, in turn, fails the analysis to rely on the distributional indistinguishability of 1FE_2 (and 1FE_1). Nevertheless, our theorem statement still holds true via the work in [KNTY19]. We thank Pratish Datta, Jiaxin Guan and Alexis Korb for pointing out the issue. We will attempt to fix it and post a revised version soon.