flâneur

Indistinguishability Obfuscation from Well-Founded Assumptions

eprint.iacr.org · 286 words · saved by 1 readers

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Theorem: Let τ∈(0,∞),δ∈(0,1),ϵ∈(0,1) be arbitrary constants. Assume sub-exponential security of the following assumptions, where λ is a security parameter, p is a λ -bit prime, and the parameters ℓ,k,n are large enough polynomials in λ : - the Learning With Errors ( LWE ) assumption over Zp with subexponential modulus-to-noise ratio 2kϵ , where k is the dimension of the LWE secret, -

Paper 2020/1003 Indistinguishability Obfuscation from Well-Founded Assumptions Aayush Jain, Huijia Lin, and Amit Sahai Abstract Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we…

saved by

related reading