Abstract
Proof without knowledge disclosure, also known as "zero-knowledge" proof, is a protocol between a prover, who holds a secret satisfying a certain property, and a verifier. At the end of the exchange, the verifier is almost certain that the prover knows the secret in question, but has learned nothing else about its value. Zero-knowledgeproofs have many applications, particularly in the context of blockchains, for example to assert facts about private data (e.g., guaranteeing that an electronic vote is well formed, without revealing the vote); authorize actions while preserving the anonymity of the actor; and delegate computations while guaranteeing that the result is correct.
We began this lecture by studying Sigma protocols, a zero-knowledgeprotocol design pattern in three interactions: pledge, challenge and response. We then set out the security properties of these protocols (completeness, special correctness and non-disclosure) and illustrated them using Schnorr's protocol (knowledge of a discrete logarithm) and its generalization, Maurer's protocol (knowledge of an antecedent by a morphism). Finally, we showed how to transform an interactive Sigma protocol into a non-interactive one using the Fiat-Shamir heuristic.
The lecture continued with a generic construction of "zk-SNARKs": succinct (small), non-interactivezero-knowledgeproofs of the knowledge of a value satisfying a property. The use of constrained arithmetic circuits enables a large number of properties to be expressed concisely. We have seen how these constrained circuits can be represented in the form of polynomial equations known as QAPs (Quadratic Arithmetic Programs). After a long detour through the proof of divisibility properties of polynomials and the homomorphic, encrypted and authenticated evaluation of polynomials, we described the Pinocchio protocol (Parno et al., 2016), which constructs zk-SNARK proofs for arbitrary QAP properties.
