• 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