4-Move Perfect ZKIP for Some Promise Problems

Kaoru KUROSAWA; Wakaha OGATA; Shigeo TSUJII

4-Move Perfect ZKIP for Some Promise Problems

Kaoru KUROSAWA, Wakaha OGATA, Shigeo TSUJII

Full Text Views

0

Cite this

Summary :

In this paper, we consider ZKIPs for promise problems. A promise problem is a pair of predicates (Q,R). A Turning machine T solves the promise problem (Q,R) if, for every x satisfying Q(x), machine T halts and it answers "yes" iff R(x). When ¬Q (x), we do not care what T does. First, we define "promised BPP" which is a promise problem version of BPP. Then, we prove that a promise problem (Q,R) has a 3-move interactive proof system which is black-box simulation zero knowledge if and only if (Q,R) ∈ promised BPP. Next, we show a "4-move" perfect ZKIPs (black-box simulation) for a promise problem of Quadratic Residuosity and that of Blum Numbers under no cryptographic assumption.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.1 pp.34-41

Publication Date: 1995/01/25

Publicized

Online ISSN

DOI

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

Category

Cite this

Copy

Kaoru KUROSAWA, Wakaha OGATA, Shigeo TSUJII, "4-Move Perfect ZKIP for Some Promise Problems" in IEICE TRANSACTIONS on Fundamentals, vol. E78-A, no. 1, pp. 34-41, January 1995, doi: .
Abstract: In this paper, we consider ZKIPs for promise problems. A promise problem is a pair of predicates (Q,R). A Turning machine T solves the promise problem (Q,R) if, for every x satisfying Q(x), machine T halts and it answers "yes" iff R(x). When ¬Q (x), we do not care what T does. First, we define "promised BPP" which is a promise problem version of BPP. Then, we prove that a promise problem (Q,R) has a 3-move interactive proof system which is black-box simulation zero knowledge if and only if (Q,R) ∈ promised BPP. Next, we show a "4-move" perfect ZKIPs (black-box simulation) for a promise problem of Quadratic Residuosity and that of Blum Numbers under no cryptographic assumption.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e78-a_1_34/_p

Copy

@ARTICLE{e78-a_1_34,
author={Kaoru KUROSAWA, Wakaha OGATA, Shigeo TSUJII, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={4-Move Perfect ZKIP for Some Promise Problems},
year={1995},
volume={E78-A},
number={1},
pages={34-41},
abstract={In this paper, we consider ZKIPs for promise problems. A promise problem is a pair of predicates (Q,R). A Turning machine T solves the promise problem (Q,R) if, for every x satisfying Q(x), machine T halts and it answers "yes" iff R(x). When ¬Q (x), we do not care what T does. First, we define "promised BPP" which is a promise problem version of BPP. Then, we prove that a promise problem (Q,R) has a 3-move interactive proof system which is black-box simulation zero knowledge if and only if (Q,R) ∈ promised BPP. Next, we show a "4-move" perfect ZKIPs (black-box simulation) for a promise problem of Quadratic Residuosity and that of Blum Numbers under no cryptographic assumption.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - 4-Move Perfect ZKIP for Some Promise Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 34
EP - 41
AU - Kaoru KUROSAWA
AU - Wakaha OGATA
AU - Shigeo TSUJII
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1995
AB - In this paper, we consider ZKIPs for promise problems. A promise problem is a pair of predicates (Q,R). A Turning machine T solves the promise problem (Q,R) if, for every x satisfying Q(x), machine T halts and it answers "yes" iff R(x). When ¬Q (x), we do not care what T does. First, we define "promised BPP" which is a promise problem version of BPP. Then, we prove that a promise problem (Q,R) has a 3-move interactive proof system which is black-box simulation zero knowledge if and only if (Q,R) ∈ promised BPP. Next, we show a "4-move" perfect ZKIPs (black-box simulation) for a promise problem of Quadratic Residuosity and that of Blum Numbers under no cryptographic assumption.
ER -