Practical and Proven Zero-Knowledge Constant Round Variants of GQ and Schnorr

Yvo G. DESMEDT; Kaoru KUROSAWA

Practical and Proven Zero-Knowledge Constant Round Variants of GQ and Schnorr

Yvo G. DESMEDT, Kaoru KUROSAWA

Full Text Views

0

Cite this

Summary :

In 1992 Burmester studied how to adapt the Guillou-Quisquater identification scheme to a proven zero-knowledge proof without significantly increasing the communication complexity and computational overhead. He proposed an almost constant round version of Guillou-Quisquater. Di Crescenzo and Persiano presented a 4-move constant round zero-knowledge interactive proof of membership for the corresponding language. A straightforward adaptation of the ideas of Bellare-Micali-Ostrovsky will also give a constant round protocol. However, these protocols significantly increase the communication and computational complexity of the scheme. In this paper we present constant round variants of the protocols of Guillou-Quisquater and Schnorr with the same (order-wise) communication and computational complexity as the original schemes. Note that in our schemes the probability that a dishonest prover will fool a honest verifier may be exponentially small, while it can only be one over a superpolynomial in Burmester's scheme. Our protocols are perfect zero-knowledge under no cryptographic assumptions.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.1 pp.69-76

Publication Date: 1999/01/25

Publicized

Online ISSN

DOI

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

Category

Cite this

Copy

Yvo G. DESMEDT, Kaoru KUROSAWA, "Practical and Proven Zero-Knowledge Constant Round Variants of GQ and Schnorr" in IEICE TRANSACTIONS on Fundamentals, vol. E82-A, no. 1, pp. 69-76, January 1999, doi: .
Abstract: In 1992 Burmester studied how to adapt the Guillou-Quisquater identification scheme to a proven zero-knowledge proof without significantly increasing the communication complexity and computational overhead. He proposed an almost constant round version of Guillou-Quisquater. Di Crescenzo and Persiano presented a 4-move constant round zero-knowledge interactive proof of membership for the corresponding language. A straightforward adaptation of the ideas of Bellare-Micali-Ostrovsky will also give a constant round protocol. However, these protocols significantly increase the communication and computational complexity of the scheme. In this paper we present constant round variants of the protocols of Guillou-Quisquater and Schnorr with the same (order-wise) communication and computational complexity as the original schemes. Note that in our schemes the probability that a dishonest prover will fool a honest verifier may be exponentially small, while it can only be one over a superpolynomial in Burmester's scheme. Our protocols are perfect zero-knowledge under no cryptographic assumptions.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_1_69/_p

Copy

@ARTICLE{e82-a_1_69,
author={Yvo G. DESMEDT, Kaoru KUROSAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Practical and Proven Zero-Knowledge Constant Round Variants of GQ and Schnorr},
year={1999},
volume={E82-A},
number={1},
pages={69-76},
abstract={In 1992 Burmester studied how to adapt the Guillou-Quisquater identification scheme to a proven zero-knowledge proof without significantly increasing the communication complexity and computational overhead. He proposed an almost constant round version of Guillou-Quisquater. Di Crescenzo and Persiano presented a 4-move constant round zero-knowledge interactive proof of membership for the corresponding language. A straightforward adaptation of the ideas of Bellare-Micali-Ostrovsky will also give a constant round protocol. However, these protocols significantly increase the communication and computational complexity of the scheme. In this paper we present constant round variants of the protocols of Guillou-Quisquater and Schnorr with the same (order-wise) communication and computational complexity as the original schemes. Note that in our schemes the probability that a dishonest prover will fool a honest verifier may be exponentially small, while it can only be one over a superpolynomial in Burmester's scheme. Our protocols are perfect zero-knowledge under no cryptographic assumptions.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Practical and Proven Zero-Knowledge Constant Round Variants of GQ and Schnorr
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 69
EP - 76
AU - Yvo G. DESMEDT
AU - Kaoru KUROSAWA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1999
AB - In 1992 Burmester studied how to adapt the Guillou-Quisquater identification scheme to a proven zero-knowledge proof without significantly increasing the communication complexity and computational overhead. He proposed an almost constant round version of Guillou-Quisquater. Di Crescenzo and Persiano presented a 4-move constant round zero-knowledge interactive proof of membership for the corresponding language. A straightforward adaptation of the ideas of Bellare-Micali-Ostrovsky will also give a constant round protocol. However, these protocols significantly increase the communication and computational complexity of the scheme. In this paper we present constant round variants of the protocols of Guillou-Quisquater and Schnorr with the same (order-wise) communication and computational complexity as the original schemes. Note that in our schemes the probability that a dishonest prover will fool a honest verifier may be exponentially small, while it can only be one over a superpolynomial in Burmester's scheme. Our protocols are perfect zero-knowledge under no cryptographic assumptions.
ER -