Paper 2020/764
Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification
Abstract
In this work, we study the question of what set of simple-to-state assumptions suffice for constructing functional encryption and indistinguishability obfuscation (iO), 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 iO 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 a subject of extensive cryptanalysis since much before our work and 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:
\begin{itemize}
\item 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
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2021
- Keywords
- ObfuscationsPRGs
- Contact author(s)
-
romain rgay @ gmail com
aayushjain1728 @ gmail com
huijial @ gmail com
amitsahai @ gmail com - History
- 2025-01-03: last of 4 revisions
- 2020-06-24: received
- See all versions
- Short URL
- https://ia.cr/2020/764
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/764, author = {Romain Gay and Aayush Jain and Huijia Lin and Amit Sahai}, title = {Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/764}, year = {2020}, url = {https://eprint.iacr.org/2020/764} }