LFCS Seminar: David Xiao
Cryptography and NPhardness
What 


When 
Nov 09, 2010 from 04:00 PM to 05:00 PM 
Where  4.31/4.33 
Add event to calendar 
vCal iCal 
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 NPhardness is not possible, and that cryptographic hardness is "significantly harder" than NPhardness. First we prove that if there exists a blackbox reduction that bases oneway functions on NPhardness, then coNP has 2prover 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 longstanding open question of whether SAT has instance checkers (BlumKannan'92).
Second, we study the possibility of basing constantround statistically hiding commitments (SHC) on NPhardness. Such SHC arise naturally in the study of collisionresistant hash functions as well as zero knowledge. We prove that if there exists a kadaptive blackbox reduction that bases constantround SHC on NPhardness, then coNP has (singleprover) 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 as well.
Based on joint work with Iftach Haitner, Thomas Holenstein, and Mohammad Mahmoody.