Cryptology ePrint Archive: Report 2012/711

Unprovable Security of 2-Message Zero Knowledge

Kai-Min Chung and Edward Lui and 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$.

Category / Keywords: foundations / zero-knowledge, super-polynomial-time simulation, black-box reductions, lower bound, falsifiable assumptions, non-uniformity

Date: received 19 Dec 2012, last revised 16 Jun 2021

Contact author: mohammad at virginia edu

Available format(s): PDF | BibTeX Citation

Version: 20210616:191438 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]