Constant Round Perfect ZKIP of Computational Ability

Toshiya ITOH; Kouichi SAKURAI

Constant Round Perfect ZKIP of Computational Ability

Toshiya ITOH, Kouichi SAKURAI

Full Text Views

0

Cite this

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 dom R.

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

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 dom R.
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 dom R.},
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 dom R.
ER -