CryptoDB

Paper: Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification

Authors: Prabhanjan Ananth Aayush Jain Huijia Lin Christian Matt Amit Sahai DOI: 10.1007/978-3-030-26954-8_10 Search ePrint Search Google The existence of secure indistinguishability obfuscators ( $i\mathcal {O}$ ) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing $i\mathcal {O}$ rely on d-linear maps. While secure bilinear maps are well established in cryptographic literature, the security of candidates for $d>2$ is poorly understood.We propose a new approach to constructing $i\mathcal {O}$ for general circuits. Unlike all previously known realizations of $i\mathcal {O}$ , we avoid the use of d-linear maps of degree $d \ge 3$ .At the heart of our approach is the assumption that a new weak pseudorandom object exists. We consider two related variants of these objects, which we call perturbation resilient generator ( $\varDelta$ RG) and pseudo flawed-smudging generator ( $\mathrm {PFG}$ ), respectively. At a high level, both objects are polynomially expanding functions whose outputs partially hide (or smudge) small noise vectors when added to them. We further require that they are computable by a family of degree-3 polynomials over $\mathbb {Z}$ . We show how they can be used to construct functional encryption schemes with weak security guarantees. Finally, we use novel amplification techniques to obtain full security.As a result, we obtain $i\mathcal {O}$ for general circuits assuming:Subexponentially secure LWEBilinear Maps $\mathrm {poly}(\lambda )$ -secure 3-block-local PRGs $\varDelta$ RGs or $\mathrm {PFG}$ s
BibTeX
@article{crypto-2019-29917,
title={Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11694},
pages={284-332},
doi={10.1007/978-3-030-26954-8_10},
author={Prabhanjan Ananth and Aayush Jain and Huijia Lin and Christian Matt and Amit Sahai},
year=2019
}