Unprovable Security of Two-Message Zero Knowledge
Abstract
Goldreich and Oren (JoC '94) show that only trivial languages have 2-message zero-knowledge arguments. In this note we consider weaker, super-polynomial-time simulation (SPS), notions of zero-knowledge. We present barriers to using black-box reductions for demonstrating soundness of 2-message protocols with efficient prover strategies satisfying SPS zero-knowledge. More precisely, we show that assuming the existence of poly(T(n))-hard one-way functions, the following holds For sub-exponential (or smaller) T(.), polynomial-time black-box reductions cannot be used to prove soundness of 2-message T(.)-simulatable arguments based on any polynomial- time intractability assumption. This matches known 2-message quasi-polynomial-time simulatable arguments using a quasi-polynomial-time reduction (Pass '03), and 2-message exponential-time simulatable proofs using a polynomial-time reduction (Dwork-Naor '00 Pass '03). poly(T(.))-time black-box reductions cannot be used to prove soundness of 2-message strong T(.)-simulatable (efficient prover) arguments based on any poly(T(.))-time intractability assumption; strong T(.)-simulatability means that the output of the simulator is indistinguishable also for poly(T(.))-size circuits. This matches known 3-message strong quasi-polynomial-time simulatable proofs (Blum '86, Canetti et al. '00).
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 19, 2012
- Accession Number
- ADA582579
Entities
People
- Edward Lui
- Kai-Min Chung
- Mohammad Mahmoody
- Rafael Pass
Organizations
- Cornell University