Post-Quantum Designated-Verifier zkSNARKs from Lattices
Post-Quantum Designated-Verifier zkSNARKs from Lattices
Zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) enable efficient privacy-preserving proofs of membership for general NP languages. These are important building blocks for verifiable computation and other privacy-preserving systems. In the designated-verifier model, a secret verification key is needed to verify proofs.
In this talk, the speaker starts by describing a general compiler for constructing designated-verifier zkSNARKs by combining linear PCPs with linear-only vector encryption. This compiler builds upon previous compilers by Bitansky et al. (TCC 2013) and Gennaro et al. (Eurocrypt 2013).
The speaker then introduces a concretely-efficient instantiation of this compiler using lattices. This yields a designated-verifier zkSNARK that is plausibly post-quantum secure. The construction achieves over 10x reduction in proof size compared to all previous post-quantum zkSNARKs: verifying an NP relation with up to a million gates requires a 16 KB proof. Compared to the most succinct (pre-quantum) SNARKs of Groth (Eurocrypt 2016) based on pairings, the prover complexity of the new lattice-based construction is 1.2x faster.
Based on the following works:
[ISW21] Yuval Ishai, Hang Su, and David J. Wu. 'Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices.' ACM CCS, 2021.
[BISW17] Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu. 'Lattice-Based SNARGs and Their Application to More Efficient Obfuscation.' Eurocrypt, 2017.
About the speaker
Assistant Professor, University of Texas at Austin
David Wu is an assistant professor in the Department of Computer Science at the University of Texas at Austin. Previously, David received his PhD in computer science from Stanford University in 2018 and was an assistant professor in the Department of Computer Science at the University of Virginia from 2019 to 2021. He has received the NSF CAREER Award and the Microsoft Research Faculty Fellowship. His research has been recognized with Best Young-Researcher Paper Awards at CRYPTO 2017 and CRYPTO 2018 as well as an Outstanding Paper Award at ESORICS.
Monash University values the privacy of every individual's personal information and is committed to the protection of that information from unauthorised use and disclosure except where permitted by law. For information about the handling of your personal information please see Data Protection and Privacy Procedure and the relevant Data Protection and Privacy Collection Statement that applies to you depending on the nature of your interaction with us.
If you have any questions about how Monash University is collecting and handling your personal information, please contact our Data Protection and Privacy Office at dataprotectionofficer@monash.edu.