International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 19 December 2012

Kai-Min Chung, Edward Lui, Mohammad Mahmoody, Rafael Pass
ePrint Report ePrint Report
Goldreich and Oren (JoC\'94) show that only trivial languages have 2-message zero-knowledge arguments. In this note we consider weaker, \\emph{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:

\\begin{itemize}

\\item For sub-exponential (or smaller) $T(\\cdot)$, \\emph{polynomial-time} black-box reductions cannot be used to prove soundness of 2-message $T(\\cdot)$-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).

\\item $\\poly(T(\\cdot))$-time black-box reductions cannot be used to prove soundness of 2-message \\emph{strong} $T(\\cdot)$-simulatable (efficient prover) arguments based on any $\\poly(T(\\cdot))$-time intractability assumption; strong $T(\\cdot)$-simulatability means that the output of the simulator is indistinguishable also for $\\poly(T(\\cdot))$-size circuits. This matches known 3-message strong quasi-polynomial-time simulatable proofs (Blum\'86, Canetti et al\'00).

\\end{itemize}

Expand

Additional news items may be found on the IACR news page.