Cryptology ePrint Archive: Report 2020/764

Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification

Romain Gay and Aayush Jain and Huijia Lin and Amit Sahai

Abstract: In this work, we study the question of what set of simple-to-state assumptions suffice for constructing functional encryption and indistinguishability obfuscation ($i\mathcal{O}$), supporting all functions describable by polynomial-size circuits. Our work improves over the state-of-the-art work of Jain, Lin, Matt, and Sahai (Eurocrypt 2019) in multiple dimensions.

New Assumption: Previous to our work, all constructions of $i\mathcal{O}$ from simple assumptions required novel pseudorandomness generators involving LWE samples and constant-degree polynomials over the integers, evaluated on the error of the LWE samples. In contrast, Boolean pseudorandom generators (PRGs) computable by constant-degree polynomials have been extensively studied since the work of Goldreich (2000). We show how to replace the novel pseudorandom objects over the integers used in previous works, with appropriate Boolean pseudorandom generators with sufficient stretch, when combined with LWE with binary error over suitable parameters. Both binary error LWE and constant-degree Goldreich PRGs have been subject to extensive cryptanalysis since much before our work. Thus, we back the plausibility of our assumption with security against algorithms studied in context of cryptanalysis of these objects.

New Techniques: We introduce a number of new techniques: - We introduce a simple new technique for proving leakage resilience when polynomial-size noise is used to hide small secrets (for example, to hide LWE-based FHE decryption errors). - We show how to build partially-hiding \emph{public-key} functional encryption, supporting degree-2 functions in the secret part of the message, and arithmetic $\mathsf{NC}^1$ functions over the public part of the message, assuming only standard assumptions over asymmetric pairing groups. - We construct single-ciphertext secret-key functional encryption for all circuits with {\em linear} key generation, assuming only the LWE assumption.

Simplification: Unlike prior works, our new techniques furthermore let us construct public-key functional encryption for polynomial-sized circuits directly (without invoking any bootstrapping theorem, nor security amplification, nor transformation from secret-key to public-key FE), and based only on the polynomial hardness of underlying assumptions. The functional encryption scheme satisfies a strong notion of efficiency where the size of the ciphertext grows only sublinearly in the output size of the circuit and not its size. Finally, assuming that the underlying assumptions are subexponentially hard, we can bootstrap this construction to achieve $i\mathcal{O}$.

Category / Keywords: foundations / Obfuscations, PRGs

Date: received 21 Jun 2020

Contact author: romain rgay at gmail com,aayushjain1728@gmail com,huijial@gmail com,amitsahai@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200624:075040 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]