Title :
Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness
Author_Institution :
CSAIL, MIT
Abstract :
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
Keywords :
computational complexity; cryptography; NP-complete problem; NP-hardness; complexity theory; constant-round zero-knowledge proofs; cryptography; one-way function; parallel repetition; polynomial hierarchy; Complexity theory; Computational complexity; Cryptography; Heart; NP-complete problem; Polynomials;
Conference_Titel :
Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on
Conference_Location :
Prague
Print_ISBN :
0-7695-2596-2
DOI :
10.1109/CCC.2006.33