
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity
Satoshi HADA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E87A
No.1
pp.29 Publication Date: 2004/01/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Fundamental Keyword: interactive proof systems, ArthurMerlin games, zeroknowledge, decisional DiffieHellman problem,
Full Text: PDF>>
Summary:
Goldwasser and Sipser proved that every interactive proof system can be transformed into a publiccoin one (a.k.a. an ArthurMerlin game). Unfortunately, the applicability of their transformation to cryptography is limited because it does not preserve the computational complexity of the prover's strategy. Vadhan showed that this deficiency is inherent by constructing a promise problem Π with a privatecoin interactive proof that cannot be transformed into an ArthurMerlin game such that the new prover can be implemented in polynomialtime with oracle access to the original prover. However, the transformation formulated by Vadhan has a restriction, i.e., it does not allow the new prover and verifier to look at common input. This restriction is essential for the proof of Vadhan's negative result. This paper considers an unrestricted transformation where both the new prover and verifier are allowed to access and analyze common input. We show that an analogous negative result holds even in this unrestricted case under a nonstandard computational assumption.

