부산대학교 도서관

Summary: ``We construct Indistinguishability Obfuscation $(\ssf{iO})$ and Functional Encryption $(\ssf{FE})$ schemes in the Turing machine model from the minimal assumption of compact $\ssf{FE}$ for circuits $(\ssf{CktFE})$. Our constructions overcome the barrier of sub-exponential loss incurred by all prior work. Our contributions are: \roster \item"1." We construct $\ssf{iO}$ in the Turing machine model from the same assumptions as required in the circuit model, namely, sub-exponentially secure $\ssf{FE}$ for circuits. The previous best constructions [6,41] [MR3724675; MR3388221] require sub-exponentially secure $\ssf{iO}$ for circuits, which in turn requires sub-exponentially secure $\ssf{FE}$ for circuits [5,15] [MR3420039; MR3473307]. \item"2." We provide a new construction of single input $\ssf{FE}$ for Turing machines with unbounded length inputs and optimal parameters from {\it polynomially} secure, compact $\ssf{FE}$ for circuits. The previously best known construction by Ananth and Sahai [7] [MR3487658] relies on $\ssf{iO}$ for circuits, or equivalently, sub-exponentially secure $\ssf{FE}$ for circuits. \item"3." We provide a new construction of multi-input $\ssf{FE}$ for Turing machines. Our construction supports a fixed number of encryptors (say $k$), who may each encrypt a string ${\bf{x}}_i$ of {\it unbounded} length. We rely on sub-exponentially secure $\ssf{FE}$ for circuits, while the only previous construction [10] [MR3487729] relies on a strong knowledge type assumption, namely, public coin differing inputs obfuscation. \endroster Our techniques are new and from first principles, and avoid usage of sophisticated $\ssf{iO}$ specific machinery such as positional accumulators and splittable signatures that were used by all relevant prior work [6,7,41].''