Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On Schnorr’s preprocessing for digital signature schemes
| |
|
On Schnorr’s preprocessing for digital signature schemes
Peter de Rooij1, 2 
| (1) |
PTT Research, P.O. Box 421, 2260 AK Leidschendam, The Netherlands |
| (2) |
Present address: Europay International, Chaussée de Tervuren 198A, 1410 Waterloo, Belgium |
Received: 29 April 1993 Revised: 15 September 1995
Communicated by Ivan B. Damg»rd
Abstract Schnorr’s identification and signature schemes [10], [11] are efficient, discrete log-based protocols. Moreover, preprocessing
algorithms are proposed that significantly speed up the computations of the prover (resp. signer). Therefore, this preprocessing
greatly enhances the suitability for implementation on a smart card. The preprocessing algorithms can be used for other (discrete
log-based) signature schemes as well.
The security of the preprocessing depends on a parameterk; the required storage is linear ink. In [10] and [11] the valuek=8 is suggested, for which the level of security is conjectured to be 272 [11].
In this paper an attack on these preprocessing algorithms is presented. This attack retrieves the secret key in about ( k!) 2 steps, using in the order of
consecutive signatures or transcripts of identifications. For k=8, this amounts to about 2 31 steps and 700 signatures.
This attack is applicable to Brickell-McCurley, ElGamal, and DSS signatures as well, if the same preprocessing algorithm is
used.
Key words Cryptology - Cryptanalysis - Identification - Digital signature - ElGamal - DSS - Preprocessing - Smart card
Part of the results of this paper were presented at Eurocrypt '91 [9].
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|