CSCI-762 - Advanced Cryptography
Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK)
Daichi Mae, Computer Science MS (Home Page)
zk-SNARKs, which stands for zero-knowledge Succinct Non-interactive
ARgument of Knowledge, allow one party to non-interactively convey a very
short proof that they have certain knowledge to another party without
revealing any information about the knowledge. zk-SNARKs were introduced
to overcome the communication overhead of interactive zero-knowledge proofs that often can be the bottleneck of a system. Today they are often used
for cryptocurrencies such as Zcash and Ethereum in order to protect users'
privacy. However, the underpinning mathematical concepts behind zk-SNARKs
are rather difficult to understand. This paper provides a crash course of
the relevant mathematical concepts such as zero-knowledge proofs and the Quadratic Span Programs with examples.
Preliminary Outline of Paper
- Zero-Knowledge Proofs
- Zero-Knowledge Succinct Non-interactive Arguments of Knowledge
- Quadratic Span Programs (QSPs)
- Example of the QSPs
- zk-SNARKs and the QSPs
- C. Reitwießner. zkSNARKs in a Nutshell. ethereum.org, December 2016.
- J. Groth. Short Pairing-Based Non-Interactive Zero-Knowledge Arguments. Advances in Cryptology - ASIACRYPT 2010, pages 321-340, October 2010.
- H. Lipmaa. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. TCC 2012: Theory of Cryptography, pages 169-189, 2012.
- N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, and O. Paneth. Erratum: Succinct Non-Interactive Arguments via Linear Interactive Proofs. TCC 2013: Theory of Cryptography, pages E1-E1, 2013.
- R. Gennaro, C. Gentry, B. Parno, and M. Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. Advances in Cryptology - EUROCRYPT 2013, pages 626-645, 2013.
- B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: Nearly Practical Verifiable Computation. Communications of the ACM, 59(2):103-112, February 2016.
- E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza. Snarks for C: Verifying Program Executions Succinctly and in Zero Knowledge. Advances in Cryptology - CRYPTO 2013, pages 90-108, 2013.
- H. Lipmaa. Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes. Advances in Cryptology - ASIACRYPT 2013, pages 41-60, February 2013.
- E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza. Succinct Non-Interactive Zero Knowledge for a Von Neumann Architecture. USENIX Security 2014, pages 781-796, December 2013.
Rochester Institute of Technology