期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-42
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Theorem (Informal). Let τ ∈ (0, ∞), δ ∈ (0, 1), ∈ (0, 1) be arbitrary constants. Assume sub-exponential security of the following assumptions, where λ is a security parameter, and the parameters `, k, n below are large enough polynomials in λ: • the SXDH assumption on asymmetric bilinear groups of a prime order p = O(2λ ), • the LWE assumption over Zp with subexponential modulus-to-noise ratio 2 k , where k is the dimension of the LWE secret, • the LPN assumption over Zp with polynomially many LPN samples and error rate 1/`δ , where ` is the dimension of the LPN secret, • the existence of a Boolean PRG in NC0 with stretch n 1 τ , Then, (subexponentially secure) indistinguishability obfuscation for all polynomialsize circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomialsize circuits.
