Monday, March 1, 2010
4:00pm

5130 Upson Hall

Abstract:

Can we base the security of cryptographic primitives on the worst-case hardness of NP? This fundamental question dates back to the seminal paper by Diffie and Hellman in 1976. We present new evidence that the answer to this question is negative in various scenarios (considering the known techniques in cryptography and complexity).

We show that basing collision resistant hashing on the worst-case hardness of NP through a black-box reduction implies an interactive proof system for co-NP with the prover in BPP^NP. More generally we show how to access almost all the entropy of a constant round interactive algorithm with the help of a BPP^NP prover.

We also show that basing one-way functions (or even average-case hardness of NP) on the worst-case hardness of NP through a black-box reduction implies that NP languages have (non-uniform) program checkers. The latter is equivalent to the existence of two-prover proof systems for co-NP with the provers in BPP^NP.

All known (even multi-prover) proof systems for co-NP require provers with #P complexity.

Based on joint works with:

Iftach Haitner, Thomas Holenstein and David Xiao.