DocumentCode
2345728
Title
Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness
Author
Pass, Rafael
Author_Institution
CSAIL, MIT
fYear
0
fDate
0-0 0
Lastpage
110
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on
Conference_Location
Prague
ISSN
1093-0159
Print_ISBN
0-7695-2596-2
Type
conf
DOI
10.1109/CCC.2006.33
Filename
1663729
Link To Document