CryptoDB
FE and iO for Turing Machines from Minimal Assumptions
| Authors: | |
|---|---|
| Download: | |
| Conference: | TCC 2018 |
| Abstract: | 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
}