Cryptology ePrint Archive: Report 2010/089

Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

Vipul Goyal and Yuval Ishai and Mohammad Mahmoody and Amit Sahai

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.

Category / Keywords: foundations / Cryptography, Statistical Security, Zero Knowledge, Interactive Proof, Interactive PCP, Commitment Scheme, Oblivious Transfer, Interactive Hashing

Date: received 18 Feb 2010

Contact author: mahmoody at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20100222:130924 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]