Psi Beta Rho
Spring 2024 - Week 3
📣 Announcements
Zero Knowledge Proofs
Joshua Zhu
Proofs???
P equals NP?
WLOG let N = 1
Where’s my field’s medal?
😊
🤔
Computational Complexity Theory
P: Polynomial Time, can be solved in poly time
NP: Nondeterministic Polynomial Time, can be verified in poly time / solvable in poly time by nondeterministic machine
Interactive Proofs (IP)
Two machines: prover and verifier
Prover and verifier exchange messages, then verifier either accepts or rejects
Prover is computationally unbounded, verifier is bounded
IP Properties
Completeness: if statement is true, honest prover can convince honest verifier
Soundness: if statement is false, not even malicious prover can convince honest verifier
Ex: Graph Non-Isomorphism
Answer whether two graphs are non-isomorphic
In Co-NP, not known whether in NP
Graph Non-Isomorphism Protocol
Prover
<----------------------
H ~ G_b’
b’ ---------------------
Verifier
coin $b, permutation $𝜋
H = 𝜋(G_b)
--------------------- H
---------------------->
Check b’ = b
Repeat
Leek!
Suppose malicious verifier picks some random graph instead of well-formed input
Free isomorphism checker!
Zero Knowledge Proofs
Intuition: want to convince someone that statement is true, without revealing anything else
Maybe data is sensitive, or communicating over untrusted channel
ZKP Properties
Completeness and Soundness: same as before
Zero-Knowledge: if true, verifier learns nothing else other than that the statement is true, not even malicious verifier
More formally, there exists a conversation simulator whose outputs are computationally indistinguishable from an actual ZKP
Ex: Graph 3-Coloring
Non-Interactive ZK Proofs (NIZK)
ZK proof without the conversation!
Contradictory???
Solutions:
Ex: Schnorr’s Identification Protocol
Ex: Schnorr’s Identification Protocol
ZK-SNARKs
Stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”
Used by Zcash and other blockchains
b01lersctf: Schnore
b01lersctf: Schnore
Need to produce valid proof
Get to choose X and z but not A or c
A, c known ahead of time
No check that z ≠ 0
b01lersctf: Schnore
Use Fermat’s Little Theorem: g^(p-1) ≡ 1 mod p
Let X = A^y so that A X^c = A^(1 + yc)
Want z = 0, 1 + yc ≡ 0 mod p-1
gcd(c, p-1) = 2, doh
Let B^2 ≡ A mod p (Tonelli Shanks), now let X = B^y’
Make 2 + y’c ≡ 0 mod p-1
Flag!
Questions?
PBR Rahhh!