Foundations and Trends® in Privacy and Security >
Vol 4 > Issue 2–4

By
**Justin Thaler**, Georgetown University, USA, jt1157@georgetown.edu

Justin Thaler (2022), "Proofs, Arguments, and Zero-Knowledge", Foundations and Trends® in Privacy and Security: Vol. 4: No. 2–4, pp 117-660. http://dx.doi.org/10.1561/3300000030

© 2022 J. Thaler

Download article
**In this article:**

Interactive proofs (IPs) and arguments are cryptographic protocols that enable an untrusted prover to provide a guarantee that it performed a requested computation correctly. Introduced in the 1980s, IPs and arguments represented a major conceptual expansion of what constitutes a “proof” that a statement is true.

Traditionally, a proof is a static object that can be easily checked step-by-step for correctness. In contrast, IPs allow for interaction between prover and verifier, as well as a tiny but nonzero probability that an invalid proof passes verification. Arguments (but not IPs) even permit there to be “proofs” of false statements, so long as those “proofs” require exorbitant computational power to find. To an extent, these notions mimic in-person interactions that mathematicians use to convince each other that a claim is true, without going through the painstaking process of writing out and checking a traditional static proof.

Celebrated theoretical results from the 1980s and 1990s such as **IP** = **PSPACE** and **MIP** = **NEXP** showed that, in principle, surprisingly complicated statements can be verified efficiently. What is more, any argument can in principle be transformed into one that is *zero-knowledge*, which means that proofs reveal no information other than their own validity. Zero-knowledge arguments have a myriad of applications in cryptography.

Within the last decade, general-purpose zero-knowledge arguments have made the jump from theory to practice. This has opened new doors in the design of cryptographic systems, and generated additional insights into the power of IPs and arguments (zero-knowledge or otherwise). There are now no fewer than five promising approaches to designing efficient, general-purpose zero-knowledge arguments. This survey covers these approaches in a unified manner, emphasizing commonalities between them.

564 pp. $99.00

Buy book (pb)
564 pp. $290.00

Buy E-book (.pdf)
1. Introduction

2. The Power of Randomness: Fingerprinting and Freivalds’ Algorithm

3. Definitions and Technical Preliminaries

4. Interactive Proofs

5. Publicly Verifiable, Non-Interactive Arguments via Fiat-Shamir

6. Front Ends: Turning Computer Programs Into Circuits

7. A First Succinct Argument for Circuit Satisfiability, from Interactive Proofs

8. MIPs and Succinct Arguments

9. PCPs and Succinct Arguments

10. Interactive Oracle Proofs

11. Zero-Knowledge Proofs and Arguments

12. ∑-Protocols and Commitments from Hardness of Discrete Logarithm

13. Zero-Knowledge via Commit-And-Prove and Masking Polynomials

14. Polynomial Commitments from Hardness of Discrete Logarithm

15. Polynomial Commitments from Pairings

16. Wrap-Up of Polynomial Commitments

17. Linear PCPs and Succinct Arguments

18. SNARK Composition and Recursion

19. Bird’s Eye View of Practical Arguments

Acknowledgements

References

This monograph is about verifiable computing (VC). VC refers to cryptographic protocols called interactive proofs (IPs) and arguments that enable a prover to provide a guarantee to a verifier that the prover performed a requested computation correctly. This monograph covers different notions of mathematical proofs and their applications in computer science and cryptography. Informally, what we mean by a proof is anything that convinces someone that a statement is true, and a “proof system” is any procedure that decides what is and is not a convincing proof.

Introduced in the 1980s, IPs and arguments represented a major conceptual expansion of what constitutes a “proof” that a statement is true. Traditionally, a proof is a static object that can be easily checked step-by-step for correctness. In contrast, IPs allow for interaction between prover and verifier, as well as a tiny but nonzero probability that an invalid proof passes verification. Arguments (but not IPs) even permit there to be “proofs” of false statements, so long as those “proofs” require exorbitant computational power to find. To an extent, these notions mimic in-person interactions that mathematicians use to convince each other that a claim is true, without going through the painstaking process of writing out and checking a traditional static proof.

Celebrated theoretical results from the 1980s and 1990s, such as IP = PSPACE and MIP = NEXP showed that, in principle, surprisingly complicated statements can be verified efficiently. What is more, any argument can in principle be transformed into one that is zero-knowledge, which means that proofs reveal no information other than their own validity. Zero-knowledge arguments have a myriad of applications in cryptography.

Within the last decade, general-purpose zero-knowledge arguments have made the jump from theory to practice. This has opened new doors in the design of cryptographic systems, and generated additional insights into the power of IPs and arguments (zero-knowledge or otherwise). There are now no fewer than five promising approaches to designing efficient, general-purpose zero-knowledge arguments. This monograph covers these approaches in a unified manner, emphasizing commonalities between them.