[Busec] BUsec this week: David Xiao (UNUSUAL TIME: Mon 3PM)

Sharon Goldberg goldbe at cs.bu.edu
Sat Jun 8 17:22:07 EDT 2013


This week, David Xiao from LIAFA in France will be visiting us and
telling us why  Languages with Zero-Knowledge PCPs are in SZK. Monday
at 3PM.  Note the unusual time, and hope to see you all there!


 BUsec Calendar:  http://www.bu.edu/cs/busec/
 BUsec Mailing list:  http://cs-mailman.bu.edu/mailman/listinfo/busec
 How to get to BU from MIT:  Try the CT2 bus or MIT's "Boston Daytime
 Shuttle" http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html

Languages with Zero-Knowledge PCP's are in SZK
David Xiao, LIAFA, France
Monday June 10, 3PM

 Probabilistically Checkable Proofs (PCPs) allow a verifier
 to check the validity of a proof by querying very few random
 positions in the proof string. Zero Knowledge (ZK) Proofs allow a
 prover to convince a verifier of a statement without revealing any
 information beyond the validity of the statement. We study for what
 class of languages it is possible to achieve both, namely to build
 ZK-PCPs, where additionally we require that the proof be generated
 efficiently.  Such ZK-PCPs could potentially be useful for building UC-secure
 protocols in the tamper-proof token model.

 We show that all languages with efficient statistical ZK-PCPs
 (i.e. where the ZK property holds against unbounded verifiers) must
 be in SZK (the class of languages with interactive statistical ZK
 proofs). We do this by reducing any ZK-PCP to an instance of the
 Conditional Entropy Approximation problem, which is known to be
 in SZK.  This implies in particular that such ZK-PCPs are unlikely to exist
 for NP-complete problems such as SAT.

This is joint work with Mohammad Mahmoody.

Sharon Goldberg
Computer Science, Boston University

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list