Sites Inria

English version

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
  • Intervenant(s) : David XIAO (LIAFA, Université Paris Diderot)
  • Organisateur(s) : 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.

Localisation

Mots-clés : Cryptographie Séminaire Équipe-projet CASCADE Inria-Rocquencourt Hoeteck WEE

Haut de page

Suivez Inria