Accession Number:

ADA582579

Title:

Unprovable Security of Two-Message Zero Knowledge

Descriptive Note:

Technical paper

Corporate Author:

CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE

Report Date:

2012-12-19

Pagination or Media Count:

12.0

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 polyTn-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. polyT.-time black-box reductions cannot be used to prove soundness of 2-message strong T.-simulatable efficient prover arguments based on any polyT.-time intractability assumption strong T.-simulatability means that the output of the simulator is indistinguishable also for polyT.-size circuits. This matches known 3-message strong quasi-polynomial-time simulatable proofs Blum 86, Canetti et al. 00.

Descriptors:

Subject Categories:

  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE