Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: David Xiao

LFCS Seminar: David Xiao

— filed under:

Cryptography and NP-hardness

What
  • LFCS Seminar
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 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 as well.
 
Based on joint work with Iftach Haitner, Thomas Holenstein, and Mohammad Mahmoody.

Document Actions