You are looking at a specific version 20121219:163415 of this paper. See the latest version.

Paper 2012/711

Unprovable Security of Two-Message Zero Knowledge

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

Abstract

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}

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
zero-knowledgesuper-polynomial-time simulationblack-box lower boundfalsifiable assumptionsnon-uniform
Contact author(s)
chung @ cs cornell 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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.