A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity

Satoshi HADA

A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity

Satoshi HADA

Full Text Views

1

Cite this

Summary :

Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin 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 private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomial-time 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 non-standard computational assumption.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.1 pp.2-9

Publication Date: 2004/01/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Fundamental

Cite this

Copy

Satoshi HADA, "A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 1, pp. 2-9, January 2004, doi: .
Abstract: Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin 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 private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomial-time 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 non-standard computational assumption.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e87-a_1_2/_p

Copy

@ARTICLE{e87-a_1_2,
author={Satoshi HADA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity},
year={2004},
volume={E87-A},
number={1},
pages={2-9},
abstract={Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin 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 private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomial-time 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 non-standard computational assumption.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2
EP - 9
AU - Satoshi HADA
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2004
AB - Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin 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 private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomial-time 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 non-standard computational assumption.
ER -