Séminaire des équipes-projets
Languages with Zero-Knowledge PCP's are in SZK
- Date : 15/11/2012
- Lieu : École Normale Supérieure, Amphi Evariste Galois - NIR
- Intervenants : David XIAO (LIAFA, Université Paris Diderot)
- Organisateurs : 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.
Ecole Normale Supérieure
45, rue d'Ulm - Paris 5ème
- Horaire : 10h30
- Entrée libre