Inria
Inria.fr
Inria Channel
Séminaire des équipes-projets
Languages with Zero-Knowledge PCP's are in SZK
- Date : 15/11/2012
- Place : École Normale Supérieure, Amphi Evariste Galois - NIR
- Guests : David XIAO (LIAFA, Université Paris Diderot)
- Organisers : Cascade
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.
Location
Keywords: Cryptographie Séminaire Équipe-projet CASCADE Inria-Rocquencourt Hoeteck WEE
Practical info
- Schedule : 10h30
- Free entry
