The Complexity of Zero Knowledge
Harvard University A Successful MarriageComplexity Theory:
Which problems are “computationally hard”
Design protocols that are “computationally hard” to break.hard problems,
adversarial view Two Areas of InteractionPseudorandomness: generating objects that “look random” despite being constructed with little or no randomness.
Cryptography: many unpredictable bits from short key
Complexity: power of randomized algs (RP vs. P, RL vs. L)
Zero-knowledge proofs: interactive proofs that reveal nothing other than validity of assertion being proven
Cryptography: central in study of crypto protocols
Complexity: augments NP $ “efficiently verifiable proofs”
[B82,...]Def of ZK, IP [GMR85]IP=PSPACE [LFKN90,S90]NPµZK [GMW86]NP-completeness
[C71,L73,K72]Secure Computation [Yao86,GMW87, BGW88,CCD88]Multiprover ZK [BGKW88]MIP=NEXP PCP Theorem [BFL91...ALMSS92]Polylog-eff ZK Args [K92,M94]Random Oracle Model [FS86,BR93,CGH98]Concurrency [F90,DNS98]Diagonalization [T36] Non-BB Simulation [B01]? This TalkComplexity-theoretic study of zero-knowledge proofs:
Characterize the expressiveness of ZK.
Prove general theorems about ZK.
Minimize or eliminate complexity assumptions.
ZK Complexity ClassesSZKPSZKACZKPCZKAZero Knowledgestatisticalcomputationalstatistical (“proofs”)computational (“arguments”)SoundnessVerifier learns nothingProver cannot convince Verifier of false statements[GMR85][BCC86] Conditional Results on ZKSZKPSZKACZKPCZKAZero Knowledgestatisticalcomputationalstatistical (“proofs”)computational (“arguments”)Soundness Complexity assumptions ) understand CZKP, SZKA, CZKA very well ...