IEICE TRANSACTIONS on Fundamentals
Constant Round Perfect ZKIP of Computational Ability
Summary :
In this paper, we show that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in BPP, and that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or of knowledge), then there exists a probabilistic polynomial time algorithm that on input x ∈ {0, 1}*, outputs y such that (x, y)∈R with overwhelming probability if x ∈dom R, and outputs "⊥" with probability 1 if x
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.7 pp.1225-1233
- Publication Date
- 1993/07/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Information Security and Cryptography
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
Toshiya ITOH, Kouichi SAKURAI, "Constant Round Perfect ZKIP of Computational Ability" in IEICE TRANSACTIONS on Fundamentals,
vol. E76-A, no. 7, pp. 1225-1233, July 1993, doi: .
Abstract: In this paper, we show that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in BPP, and that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or of knowledge), then there exists a probabilistic polynomial time algorithm that on input x ∈ {0, 1}*, outputs y such that (x, y)∈R with overwhelming probability if x ∈dom R, and outputs "⊥" with probability 1 if x
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_7_1225/_p
Copy
@ARTICLE{e76-a_7_1225,
author={Toshiya ITOH, Kouichi SAKURAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Constant Round Perfect ZKIP of Computational Ability},
year={1993},
volume={E76-A},
number={7},
pages={1225-1233},
abstract={In this paper, we show that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in BPP, and that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or of knowledge), then there exists a probabilistic polynomial time algorithm that on input x ∈ {0, 1}*, outputs y such that (x, y)∈R with overwhelming probability if x ∈dom R, and outputs "⊥" with probability 1 if x
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Constant Round Perfect ZKIP of Computational Ability
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1225
EP - 1233
AU - Toshiya ITOH
AU - Kouichi SAKURAI
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 1993
AB - In this paper, we show that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in BPP, and that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or of knowledge), then there exists a probabilistic polynomial time algorithm that on input x ∈ {0, 1}*, outputs y such that (x, y)∈R with overwhelming probability if x ∈dom R, and outputs "⊥" with probability 1 if x
ER -
English
