DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
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.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE
