IEICE TRANSACTIONS on Fundamentals
A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 -
English
