CSCI-762 - Advanced Cryptography

Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK)

Daichi Mae, Computer Science MS (Home Page)

Abstract

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

Deliverables

References

  1. C. Reitwie├čner. zkSNARKs in a Nutshell. ethereum.org, December 2016.
  2. J. Groth. Short Pairing-Based Non-Interactive Zero-Knowledge Arguments. Advances in Cryptology - ASIACRYPT 2010, pages 321-340, October 2010.
  3. H. Lipmaa. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. TCC 2012: Theory of Cryptography, pages 169-189, 2012.
  4. 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.
  5. 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.
  6. B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: Nearly Practical Verifiable Computation. Communications of the ACM, 59(2):103-112, February 2016.
  7. 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.
  8. 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.
  9. 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.

Daichi Mae
Rochester Institute of Technology
dm6249@rit.edu