## CryptoDB

### Paper: FE and iO for Turing Machines from Minimal Assumptions

Authors: Shweta Agrawal Monosij Maitra DOI: 10.1007/978-3-030-03810-6_18 Search ePrint Search Google TCC 2018 We construct Indistinguishability Obfuscation ($\mathsf {iO}$) and Functional Encryption ($\mathsf {FE}$) schemes in the Turing machine model from the minimal assumption of compact $\mathsf {FE}$ for circuits ($\mathsf {CktFE}$). Our constructions overcome the barrier of sub-exponential loss incurred by all prior work. Our contributions are:1.We construct $\mathsf {iO}$ in the Turing machine model from the same assumptions as required in the circuit model, namely, sub-exponentially secure $\mathsf {FE}$ for circuits. The previous best constructions [6, 41] require sub-exponentially secure $\mathsf {iO}$ for circuits, which in turn requires sub-exponentially secure $\mathsf {FE}$ for circuits [5, 15].2.We provide a new construction of single input $\mathsf {FE}$ for Turing machines with unbounded length inputs and optimal parameters from polynomially secure, compact $\mathsf {FE}$ for circuits. The previously best known construction by Ananth and Sahai [7] relies on $\mathsf {iO}$ for circuits, or equivalently, sub-exponentially secure $\mathsf {FE}$ for circuits.3.We provide a new construction of multi-input $\mathsf {FE}$ for Turing machines. Our construction supports a fixed number of encryptors (say k), who may each encrypt a string $\mathbf {x}_i$ of unbounded length. We rely on sub-exponentially secure $\mathsf {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 $\mathsf {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
}