GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks

Authors: M. Bellare and A. Palacio

Abstract: The Guillou-Quisquater (GQ) and Schnorr identification schemes are amongst the most efficient and best-known Fiat-Shamir follow-ons, but the question of whether they can be proven secure against impersonation under active attack has remained open. This paper provides such a proof for GQ based on the assumed security of RSA under one more inversion, an extension of the usual one-wayness assumption that was introduced by Bellare, Namprempre, Pointcheval and Semanko. It also provides such a proof for the Schnorr scheme based on a corresponding discrete-log related assumption. These are the first security proofs for these schemes under assumptions related to the underlying one-way functions. Both results extend to establish security against impersonation under concurrent attack.

Ref: Extended abstract in Advances in Cryptology - CRYPTO 2002 Proceedings, Lecture Notes in Computer Science Vol. 2442, M. Yung ed, Springer-Verlag, 2002. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).