On the Fly Authenti ation and Signature

On the Fly Authenti ation and Signature S hemes based on Groups of Unknown Order Mar Girault 1 , Guillaume Poupard 2 , and Ja ques Stern 3 1 Fran e Tele om Resear h & Development, 42 rue des Coutures BP 6243, F-14066 Caen Cedex 4, Fran e mar .giraultfran etele om. om 2 DCSSI Crypto Lab, 51 boulevard de La Tour-Maubourg F-75700 Paris 07 SP, Fran e Guillaume.Poupardm4x.org 3 É ole normale supérieure, Département d'informatique 45 rue d'Ulm, F-75230 Paris Cedex 05, Fran e Ja ques.Sternens.fr Abstra t. In response to the urrent need for fast, se ure and heap publi -key ryp- tography, we propose an intera tive zero-knowledge identi ation s heme and a derived signature s heme that ombine provable se urity based on the problem of omputing dis rete logarithms in any group, short keys, very short transmission and minimal on- line omputation. This leads to both e ient and se ure appli ations well suited to implementation on low ost smart ards. We introdu e GPS, a S hnorr-like s heme that does not require knowledge of the order of the group nor of the group element.

• heap publi -key


• identi ation


• ation time


• appli ations


• zero-knowledge


• signature


• international organization


• ele tromagneti indu