International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

Authors:
Vipul Goyal
Yuval Ishai
Mohammad Mahmoody
Amit Sahai
Download:
URL: http://eprint.iacr.org/2010/089
Search ePrint
Search Google
Abstract: Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by a PCP oracle. This strengthens the feasibility result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC '88) which requires two stateful provers. In contrast to previous zero-knowledge PCPs of Kilian, Petrank, and Tardos (STOC '97), in our protocol both the prover and the PCP oracle are efficient given an $NP$ witness. Our main technical tool is a new primitive that we call {\em interactive locking}, an efficient realization of an unconditionally secure commitment scheme in the interactive PCP model. We implement interactive locking by adapting previous constructions of {\em interactive hashing} protocols to our setting, and also provide a direct construction which uses a minimal amount of interaction and improves over our interactive hashing based constructions. Finally, we apply the above results towards showing the feasibility of basing unconditional cryptography on {\em stateless} tamper-proof hardware tokens, and obtain the following results: *) We show that if tokens can be used to encapsulate other tokens, then there exist unconditional and statistically secure (in fact, UC secure) protocols for general secure computation. *) Even if token encapsulation is not possible, there are unconditional and statistically secure commitment protocols and zero-knowledge proofs for $NP$. *) Finally, if token encapsulation is not possible, then no protocol can realize statistically secure oblivious transfer.
BibTeX
@misc{eprint-2010-22990,
  title={Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography},
  booktitle={IACR Eprint archive},
  keywords={foundations / Cryptography, Statistical Security, Zero Knowledge, Interactive Proof, Interactive PCP, Commitment Scheme, Oblivious Transfer, Interactive Hashing},
  url={http://eprint.iacr.org/2010/089},
  note={ mahmoody@gmail.com 14659 received 18 Feb 2010},
  author={Vipul Goyal and Yuval Ishai and Mohammad Mahmoody and Amit Sahai},
  year=2010
}