[Q&A] Zero-Knowledge Proofs
General questions
- How to explain ZK proofs to a 7 year old?
- Are there lower bounds on the size and interaction of a ZK proof with a given soundness error?
- Can we do zero-knowledge proofs for BPP statements? (short answer: just send the witness!)
- What is the difference between ZK proofs and ZK proofs of knowledge? (short answer: in ZK proof of knowledge, an extractor can recover the witness)
- Why is computational ZK the most general notion of zero-knowledge?
- How to choose the security parameter for a ZK proof?
- Are there lower bounds on the round complexity and communication of ZK proofs? (and also: how far are existing ZK proofs from these bounds)
- How do common reference strings help in ZK proofs? (short answer: they help reducing round complexity)
- What are the links between ZK proofs and homomorphic encryption? (short answer: there are many links.)
Understanding ZK proofs
- Why is “sending a hash of the witness” not a valid ZK proof of knowledge of the witness? (also includes a walkthrough of why Schnorr’s proof is a honest-verifier ZK proof)
- Why is the Diffie-Hellman key-exchange protocol not a proof of knowledge of a discrete logarithm? (also includes a discussion about knowledge-of-exponent assumptions, and public-coin versus private coin proofs)
Building ZK proofs
- How to prove that a committed value is the square of the other?
- How to prove that a committed number belongs to a certain range?
- What are the different techniques to build a range proof?
- Where did the four square decomposition technique originate?
- How to prove that a number is not within a range?
- How to prove knowledge of a witness for a DDH tuple?
- Is it possible to prove knowledge of an AES key without showing it? (short answer: yes)
- How to prove correctness of a long computation with a short proof?
- Can we replace pairings by homomorphic encryption in SNARGs/SNARKs? (short answer: yes, but it becomes designated-verifier)
- How to prove soundness of $\Sigma$-protocols in unknown-order groups?
Others
- Is it possible to randomize a non-interactive ZK proof? (short answer: yes)
- What are the security issues of making ZK proofs non-interactive with Fiat-Shamir? (short answer: transferability, computational soundness)
- How to verify a signature on an encrypted message?
- Why is Schnorr’s proof not an argument? (short answer: recovering the discrete log in unbounded time does not contradict soundness)
- Why is a transparent setup desirable for SNARKs?
- Do NIZKs imply simulation-sound NIZKs? (short answer: yes)
- Are there post-quantum SNARGs?