In 1992 Burmester studied how to adapt the Guillou-Quisquateridentification scheme to a proven zero- knowledge proof withoutsignificantly increasing the communica- tion complexity andcomputational overhead. He proposed an al- most constant roundversion of Guillou-Quisquater. Di Crescenzo and Persiano presented a4-move constant round zero-knowledge interactive proof of membershipfor the corresponding language. A straightforward adaptation of theideas of Bellare-Micali- Ostrovsky will also give a constant roundprotocol. However, these protocols significantly increase thecommunication and computational complexity of the scheme. In thispaper we present constant round variants of the protocols ofGuillou-Quisquater and Schnorr with the same (order-wise)communication and com- putational complexity as the original schemes.Note that in our schemes the probability that a dishonest prover willfool a hon- est verifier may be exponentially small, while it canonly be one over a superpolynomial in Burmester's scheme. Ourprotocols are perfect zero-knowledge under no cryptographicassumptions.
展开▼
