# 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

- Introduction
- Zero-Knowledge Proofs
- Zero-Knowledge Succinct Non-interactive Arguments of Knowledge
- Overview
- Quadratic Span Programs (QSPs)
- Example of the QSPs
- zk-SNARKs and the QSPs

- Conclusions

### Deliverables

### References

- 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.

Daichi Mae

Rochester Institute of Technology

dm6249@rit.edu