For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Practical and Proven Zero-Knowledge Constant Round Variants of GQ and Schnorr
Yvo G. DESMEDT Kaoru KUROSAWA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/01/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
zero-knowledge, constant round, low complexity, GQ, Schnorr,
Full Text: PDF>>
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.