Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
Brent Waters
Video
Abstract:
A succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement x is true with a proof of size o(|x| + |w|) where w is the associated NP witness. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this work, we provide the first adaptively-sound SNARG for NP in the plain model assuming sub-exponentially-hard indistinguishability obfuscation, sub-exponentially-hard one-way functions and either the (polynomial) hardness of the discrete log assumption or the (polynomial) hardness of factoring. This gives the first adaptively-sound SNARG for NP from falsifiable} assumptions. All previous SNARGs for in the plain model either relied on non-falsifiable cryptographic assumptions or satisfied a weak notion of non-adaptive soundness (where the adversary has to choose the statement it proves before seeing the scheme parameters). This is joint work with David Wu.
Bio:
Brent Waters is a Professor at the University of Texas at Austin and a Distinguished Scientist at NTT Research. Waters's research interests are in the areas of cryptography computer security. His work has focused on Identity-Based Cryptography, Functional Encryption, and code obfuscation. He is noted as a founder of Functional Encryption and Attribute-Based Encryption. Waters has been the recipient of a NSF CAREER award, a Microsoft Faculty Fellow, a Sloan Research Fellowship, a Packard Science and Engineering Fellowship, a Presidential Early Career Award for Scientists and Engineers recipient; winner of the 2015 ACM Grace Murray Hopper Award, and a Simons Investigator. He received his PhD in computer science from Princeton University in 2004. From 2004-2005, he was a postdoc at Stanford University, then worked at SRI as a computer scientist.