A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity (Fundamental) (<Special Section>Cryptography and Information Security)
スポンサーリンク
概要
- 論文の詳細を見る
Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin game) [25]. 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 II with a private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomialtime with oracle access to the original prover [34]. 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.
- 一般社団法人電子情報通信学会の論文
- 2004-01-01
著者
関連論文
- Zero-Knowledge and Correlation Intractability(Information Security)
- A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity (Fundamental) (Cryptography and Information Security)
- A Formal Treatment of Non-repudiation Protocols(Information Security)
- A Note on Transformations of Interactive Proofs that Preserve the Prover's Complexity