PublicationsA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NPBrent Waters and David J. Wu Resources
Abstract
We construct an adaptively-sound succinct non-interactive argument (SNARG) for \( \mathsf{NP} \) in the CRS model from sub-exponentially-secure indistinguishability obfuscation (\( i\mathcal{O} \)) and sub-exponentially-secure one-way functions. Previously, Waters and Wu (STOC 2024), and subsequently, Waters and Zhandry (CRYPTO 2024) showed how to construct adaptively-sound SNARGs for NP by relying on sub-exponentially-secure indistinguishability obfuscation, one-way functions, and an additional algebraic assumption (i.e., discrete log, factoring, or learning with errors). In this work, we show that no additional algebraic assumption is needed and vanilla (sub-exponentially-secure) one-way functions already suffice in combination with \( i\mathcal{O} \). We first give a direct construction of an adaptively-sound SNARG for NP assuming (sub-exponentially-secure) \( i\mathcal{O} \) and an injective one-way function. Then, we show that it suffices to have an injective one-way function that has an inefficient sampler (i.e., sampling a challenge for the one-way function requires super-polynomial time). Because we rely on the existence of injective one-way functions only in the security proof and not in the actual construction, having an inefficient sampling procedure does not impact correctness. We then show that injective one-way functions with an inefficient sampler can be built generically from any vanilla one-way function. Our approach may be independently useful in other settings to replace injective one-way functions with standard one-way functions in applications of \( i\mathcal{O} \). BibTeX
@misc{WW24, author = {Brent Waters and David J. Wu}, title = {A Pure Indistinguishability Obfuscation Approach to Adaptively-Sound {SNARGs} for {NP}}, misc = {Full version available at \url{https://eprint.iacr.org/2024/933}}, year = {2024} } |