loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st Annual IEEE Conference on Computational Complexity (CCC'06)
Parallel Repetition of Zero-Knowledge Proofs and the Possibility of Basing Cryptography on NP-Hardness
Prague, Czech Republic
July 16-July 20
ISBN: 0-7695-2596-2
Rafael Pass, CSAIL, MIT
Two long-standing open problems exist on the fringe of Complexity Theory and Cryptography: 1. Does there exist a reduction from an NP-Complete Problem to a one-way function? 2. Do parallelized versions of classical constant-round zero-knowledge proofs for NP conceal every "hard" bit of the witness to the statement proved? We show that, unless the Polynomial-Hierarchy collapses, black-box reductions cannot be used to provide positive answers to both questions.
Citation:
Rafael Pass, "Parallel Repetition of Zero-Knowledge Proofs and the Possibility of Basing Cryptography on NP-Hardness," ccc, pp.96-110, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.