Paper 2012/711

Unprovable Security of 2-Message Zero Knowledge

Kai-Min Chung, Edward Lui, Mohammad Mahmoody, and Rafael Pass

Abstract

Goldreich and Oren (JoC'94) show that only languages in BPP have 2-message zero-knowledge arguments. In this paper we consider weaker, super-polynomial 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, if $poly(T(n))$-hard one-way functions exist for a super-polynomial $T(n)$, the following holds about 2-message efficient prover arguments over statements of length $n$. 1. Black-box reductions cannot prove soundness of 2-message $T(n)$-simulatable arguments based on any polynomial-time intractability assumption, unless the assumption can be broken in polynomial time. This complements 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). 2. Back-box reductions cannot prove soundness of 2-message strong $T(n)$-simulatable arguments, even if the reduction and the challenger both can run in $poly(T(n))$-time, unless the assumption can be broken in $poly(T(n))$ time. Strong $T(\cdot)$-simulatability means that the output of the simulator is indistinguishable also for $poly(T(\cdot))$-size circuits, with a $negl(T(\cdot))$ indistinguishability gap. This complements known 3-message strong quasi-polynomial-time simulatable proofs (Blum'86, Canetti et~al'~00), or 2-message quasi-polynomial-time simulatable arguments (Khurana-Sahai'17, Kalai-Khurana-Sahai'18) satisfying a relaxed notion of strong simulation where the distinguisher's size can be large, but the distinguishing gap is negligible in $n$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
zero-knowledgesuper-polynomial-time simulationblack-box reductionslower boundfalsifiable assumptionsnon-uniformity
Contact author(s)
mohammad @ virginia edu
History
2021-06-16: revised
2012-12-19: received
See all versions
Short URL
https://ia.cr/2012/711
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/711,
      author = {Kai-Min Chung and Edward Lui and Mohammad Mahmoody and Rafael Pass},
      title = {Unprovable Security of 2-Message Zero Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2012/711},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/711}},
      url = {https://eprint.iacr.org/2012/711}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.