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

Sharon Goldberg goldbe at cs.bu.edu
Wed Jun 5 17:08:24 EDT 2013


Next week, David Xiao from LIAFA in France will be visiting us and
giving a talk on Languages with Zero-Knowledge PCPs, on 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

More information about the Busec mailing list