LRI, Orsay
4pm Tuesday, 9th November, 2010
Room 4.31/33, Informatics Forum
Cryptography is one of the most successful contributions of theoretical computer science. It underlies much of modern telecommunication networks, providing secrecy and authentication on channels that are intrinsically insecure. One goal of theoretical cryptographers is to base the hardness of breaking cryptosystems on minimal assumptions. We already know that P different from NP is necessary to build secure cryptography. Ideally one would be able to show that this assumption is also sufficient, namely that if P does not equal NP, then one can build secure cryptosystems.
In this talk, we give results indicating that basing cryptography on NP-hardness is not possible, and that cryptographic hardness is "significantly harder" than NP-hardness. First we prove that if there exists a black-box reduction that bases one-way functions on NP-hardness, then coNP has 2-prover interactive proofs with honest prover complexity BPP^NP. This would improve on the best known honest prover complexity for coNP, which currently stands at P^#P (lund et al. '90). We also discuss the connection between this and the long-standing open question of whether SAT has instance checkers (Blum-Kannan'92).
Second, we study the possibility of basing constant-round statistically hiding commitments (SHC) on NP-hardness. Such SHC arise naturally in the study of collision-resistant hash functions as well as zero knowledge. We prove that if there exists a k-adaptive black-box reduction that bases constant-round SHC on NP-hardness, then coNP has (single-prover) interactive proofs with honest prover complexity BPP^NP and round complexity k. As with the first result, this would improve the best known prover complexity for coNP, and for small values of k it would also improve the round complexity.
Based on joint work with Iftach Haitner, Thomas Holenstein, and Mohammad Mahmoody.