Efficient Signature Generation by Smart Cards∗
C.P. Schnorr
Fachbereich Mathematik / Informatik
Universität Frankfurt
March 1991

1

Introduction.

Public key signature schemes are necessary for the access control to communication networks and for proving the authenticity of sensitive messages
such as electronic fund transfers. Since the invention of the RSA–schemeby Rivest, Shamir and Adleman (1978) research has focused on improving
the efficiency of these schemes. In this paper we present an efficient algorithm for generating public key signatures which is particularly suited forinteractions between smart cards and terminals.
The new signature scheme minimizes the message dependent amount ofcomputation the smart card has to perform to generate a signature. Thisis important since the computational power of current processors for smart
cards is rather limited. Previous signature schemes require many modular
multiplications for signature generation. In the new scheme the main work
for signature generation does not depend on the message and can be done
during the idle time of the processor. The message dependent part of signature generation consists of multiplying a 140 bit integer with a 72 bit
integer.
∗

european patent application 89103290.6 from 24.2.1989

1

Our signature scheme relies on the interactive protocol of Chaum, Evertse,
Graaf (1988) that proves possession of a discrete logarithm. It combines various ideas from the schemes by ElGamal (1985) and Fiat–Shamir (1986). It
is derived from an underlying interactive authentication scheme by replacing
the verifier’s challenge by a hash value. The novel features of our scheme canbe incorporated into the Beth authentication scheme and into the key distribution scheme by Günther (1989). The new scheme comprises the following
novel features:(1) Most of the computational effort for signature generation is done in a
preprocessing stage that is independent of the message and can be done
during the idle time of the processor. The preprocessing consists ofthe exponentiation of a random number modulo a large prime. Given
this exponentiated residue a signature can be generated very fast, it
requires only the multiplication of a 72 bit integer with a 140 bit
integer. The idea of preprocessing signatures is similar in spirit to
the concept of on–line/off-line signatures that has been independently
proposed by Even, Goldreich and Micali (1989).
(2) We use a prime modulus p with p − 1 having a prime factor q
of appropriated size (e.g. 140 bits long) and we use a base α forthe discrete logarithm such that αq = 1 (mod p) . All logarithms
are calculated modulo q. The length of signatures is about 212 bits,
it is less than half of the length of RSA signatures. The number ofcommunication bits of the authentication scheme is less than half ofthat of other schemes.
(3) We propose an efficient algorithm for simulating the exponentiationof random numbers. This algorithm is independent of the rest of thepaper. If proven to be secure our algorithm reduces the amount ofcomputation for generating random exponentiated residues by using
additional memory for storing some statistically independent exponentiated residues.
The security of the scheme relies on the one–way property of the exponentiation y 7→ αy (mod p). We therefore have to assume that discrete
logarithms with base α are difficult to compute.
The paper is organized as follows. We present in section 2 a versionof the signature scheme and of the underlying authentication scheme that2

uses exponentiation of a random integer. The performance of the scheme isexemplified in section 3. In section 4 we propose an efficient algorithm thatsimulates the exponentiation of a random number.

2

The Authentication And Signature Scheme.

Notation.
For n ∈ IN let ZZn be the ring of integers modulo n. We
identify ZZn with the set of integers {1, . . . , n}.
Initiation of the key authentication center (KAC).
chooses

The KAC• primes p and q such that q | p − 1, q ≥ 2140 , p ≥ 2512 ,• α ∈ ZZp with order q, i.e. αq = 1 (mod p), α 6= 1,• a one–way hash function h : ZZq × ZZ → {0, . . . 2t − 1},• its own private and public key.
The KAC publishes p, q, α, h and its public key.
The security complexity 2t .
We wish to choose the parameters p, q
so that forging a signature or an authentication requires by known methods
about 2t steps. For this we choose q ≥ 22t and p such that 2t is about√ln p ln ln p

. The security number t may depend on the application intended.
e
For signatures we consider in particular t = 72 rather that t = 64, since
264 steps may be insufficient in view of the rapid technological progress incomputing power and speed. For p ≥ 2512 and q ≥ 2140 the discrete
logarithm problem requires at least 272 steps by known algorithms. (Itmay soon be necessary to increase the lower bound p ≥ 2512 due to thecurrent progress in computing discrete logarithms.) The restriction that theorder of α is a prime much smaller than p does provide no advantage
in any of the known discrete logarithm algorithms provided that q ≥ 2140 .
The prime q is necessary in order to avoid an index calculus attack and asquare root attack (see section 2). A lower security level may be sufficient
for authentication in particular if the prover is requested to respond fast, say
within a few seconds. A security complexity 240 for authentication requires
to choose t ≥ 40, p ≥ 2256 and q ≥ 280 .
3

Registration of users, signatures by the KAC. When a user comesto the KAC for registration the KAC verifies its identity, generates an identification number I (containing name, address, ID–number etc.) and generates
a signature S for the pair (I, v) consisting of I and the user’s public key
v. In our scheme as well as in the RSA–scheme each user may produce byhimself his own private key s and the corresponding public key v. It
is necessary to complete the corresponding public information (I, v) by asignature S of a trusted authority, the KAC. The verification of a signatureor an authentification with the public key v must also contain a verificationof the public key v. This verification can either be done on–line by reading(I, v) from a public file or off–line by verifiying KAC’s signature S for(I, v) using the public key of the KAC. In an interaction between two smart
cards the verification of v is always off–line.
The KAC can use for its own signatures any secure public key signaturescheme whatsoever. For instance the KAC can use our scheme which yields
short signatures that can be verified using about 228 modular multiplications. Alternatively the KAC can base its signature S for (I, v) on theidentity S 2 = h(j, I, v) (mod N ) where N is a public RSA–modulus, h a
one–way hash function and j a small integer. Only the KAC can generatesuch a signature S using the secret factorization of N . The verification ofthis signature S requires only one modular squaring. — This is the sameamount of computation that is necessary for the verification of the public
key in the identity based Fiat–Shamir scheme.
The user’s private und public key.
A user generates by himself aprivate key s which is a random number in {1, 2, . . . , q}. The corresponding
public key v is the number v = α−s (mod p).
Once the private key s has been chosen one can easily compute thecorresponding public key v. The inverse process, to compute s fromv, requires to compute the discrete logarithm with base α of v −1 , i.e.
s = −logα v.
The following authentication protocol is essentially equal to protocol 1 in
Chaum, Evertse, Graaf (1988). Their protocol 1 is the particular case t = 0
and q = p − 1 of the protocol below which for its part is a parallel variant
for t sequential rounds of their protocol 1. Chaum et alii prove that their4

protocol 1 is zero–knowledge, i.e. it does not reveal any information on thesecret s. The parallel variant of the Chaum et alii protocol is not known tobe zero–knowledge.
The authentication protocol.
(Prover A proves its identity to verifier B)
1. Preprocessing (see section 4).
A picks a random numberr ∈ {1, . . . , q − 1}, and computes x := αr (modp) .
2. Initiation. A sends to B its identication string I, its public key v, the
KAC’s signature S for (I, v), and x.
3. B verifies the signaturee ∈ {0, . . . , 2t − 1} to A.

S

and

sends

a

randomnumber

4. A sends to B y := r + se (mod q).
5. Verification. B verifies (I, v) either by checking the signature S or
by verifying (I, v) on–line. B checks that x = αy v e (mod p).
Obviously if A und B follow the protocol then B always accepts A’s proofof identity. We next consider the possibilities of cheating for A and B. We
ecall (x, y) the proof and e the exam of the authentication. Let Ae (B,e resp.) may deviate from theresp.) denote a fraudulent A (B, resp.). Ae (B,e canprotocol in computing x, y (e, resp.). Ae does not know the secret s. B
spy upon A’s method of authentication.

A fraudulent Ae can cheat by guessing the correct e and sending with anarbitrary r ∈ ZZq the crooked proof
x := αr v e (mod p),y := r .

The probability of success for this attack is 2−t .
By the following theorem this success rate cannot be increased unlesscomputing logα v is easy. For this let Ae be any probabilistic, interactive
algorithm (Turing machine) that is given the fixed values p, q, α. Let RA5

e Let the success bit S
denote the internal random bit string of A.
Ã,v (RA, e)

be 1 if Ae succeeds with v, RA, e and 0 otherwise. The success rate SÃ,v of
Ae for v is the average of SÃ,v (RA, e), where RA, e are chosen at randomwith uniform distribution. We assume that the time TÃ,v (RA, e) of Ae withv, RA, e is independent of RA and e, i.e.

TÃ,v (RA, e) = TÃ,v . This is

no restriction since limiting the time to twice the average running time forsuccessful pairs (RA, e) decreases the success rate at most by a factor 2.
Theorem 2.1
e v)
(A,

There is a probabilistic algorithm AL which on input

computes logα v. If the success rate SÃ,v of Ae with v is greaterthan 2−t+1 then AL runs in expected time O(TÃ,v / SÃ,v ) where TA,v
e isthe time of Ae on input v.
Proof.
The argument extends Theorem 5 in Feige, Fiat, Shamir (1987).
We assume that the time TÃ,v also covers the time required for B.
Algorithm AL with input v.
e RA, v), i.e. compute x the
1. Pick RA at random. Compute x = x(A,same way as does algorithm Ae using the coin tossing sequence RA.
e RA, v, e) the
Pick a random e ∈ {0, . . . , 2t − 1}. Compute y := y(A,e If S (RA, e) = 1 then fix RA, retain
same way as algorithm A.
Ã,vx, y, e and go to 2. Otherwise repeat step 1 using an independent RA.
2. Let u be the number of probes (i.e. passes of step 1) in the computation of RA, x, y, e. Probe up to 4u random e ∈ {0, . . . , 2t −1} whetherSÃ,v (RA, e) = 1. If some 1 occurs with e 6= e then compute the corresponding y = y(Ae , RA , e , v ) and output logα v := y−ye−e (mod q).
Time analysis.

Let SÃ,v > 2−t+1 . We arrange for fixed Ae and v the

success bits SÃ,v (RA, e) in a matrix with rows RA and columns e. A
row RA is called heavy if the fraction of 1–entries is at least SÃ,v / 2. At
6

least half of the 1–entries are in heavy rows since the number of 1–entries in
non–heavy rows is at most SÃ,v · #rows · #columns / 2. Thus the row RA
that succeeds in step 1 is heavy with probability at least 1/2. A heavy row
has at least two 1–entries.
We abbreviate ε = SÃ,v . The probability that step 1 probes i ε−1
random RA without finding an 1–entry is at most (1 − ε)i/ε < 2.7−i . Thus
the average number of probes for the loop of step 1 is∞X≤i ε−i 2.7−i+1 = O(ε−1 ) .

i=1

We have with probability at least 1/2 that u ≥ ε−1 /2. The row RA is
heavy with probability at least 1/2. If these two cases happen then step 2
finds a successful e with probability ≥ 1 − (1 − ε/2)2/ε > 1 − 2.7−1 ,and we have e 6= e with probability ≥ 1/2. Thus AL terminates after one
iteration of steps 1 and 2 with probability
11(1 − 2.7−1 )4
2≥> 0.07.

The probability that AL performs exactly i iterations is at most 0.93i−1 .
Alltogether we see that the average number of probes for AL is at most
Ã

O 5ε

−1

∞
X

!
i−1

0.93

t

= O(ε−1 ).

i=0This proves the claim.

Q.E.D.

The above proof shows that two authentications with the same x anddistinct challenges e, e together reveal the secret s.
The argument above can be extended to show that the authentication
protocol is a proof of knowledge, in the sense of Feige, Fiat, Shamir (1987),
showing that user A knows s = logα v.

7

The verifier B is free to choose the bit string e in step 3 of the authentication protocol, thus he can choose e in order to spy upon A’s method
for authentication. The informal (but non rigorous) reason that A reveals
no information is that the numbers x and y are random. The random
number x reveals no information. It is unlikely that the number y reveals
any useful information because y is superposed by the discrete logarithmof x, y = logα x + es (mod q) and the cryptanalyst cannot infer r = logα xfrom x. The scheme is not zero–knowledge because the triple (x, y, e) may
be a particular solution of the equation x = αy v e (mod p) due to the factthat the choice of e may depend on x.
Minimizing the number of communication bits. Using a hash function h we can reduce the amount of communication for authentication. A
can send in step 2 the t bit string h(x) = h(x, 0) instead of x and B
computes in step 5 x := αy v e (mod p) and checks that h(x) = h(x). It
is not necessary that h is a one–way function because x = αr (mod p)
is already the result of a one–way function. To achieve the security level2t the bit string h(x) must be at least t bits long. No particular attack is
known for the function h(x) consisting of the t least significant bits of x.
The number of communication bits is 2t + 140 plus the bits for (I, v) and
S. The pair (y, h(x)) is a signature of the empty message with respect tothe following signature scheme.
Protocol for signature generation.
To sign message m with the private key s perform the following steps:
1. Preprocessing (see section 3). Pick a random number r ∈ {1, . . . , q}
and compute x := αr (mod p).
2. Compute e := h(x, m) ∈ {0, . . . , 2t − 1}.
3. Compute y := r + se (mod q) and output the signature (e, y).
Protocol for signature verification.
To verify the signature (e, y) for message m with public key v computex = αy v e (mod p) and check that e = h(x, m) .

8

A signature (e, y) is accepted if it withstands verification. A signature
generated according to the protocol is always accepted since we havex = αr = αr+se v e = αy v e (mod p) .
With t = 72 and q ≈ 2140 the signature (e, y) is 212 bits long.
Efficiency.
The work for signature generation consists mainly of the
preprocessing (see section 3) and the computation of se (mod q) where
the numbers s and e are about 140 and t = 72 bits long. The latter
multiplication is negligible compared to a modular multiplication in the
RSA–scheme.
Signature verification consists mainly of the computation of x =αy v e (mod p) which can be done on the average using 1.5` + 0.25t multiplications modulo p where ` = dlog2 qe is the bit length of q. For this lety and e have the binary representations
y=

`−1
X

yi 2 i ,

i=0

e=

`−1
X

ei 2 iwith yi , ei ∈ {0, 1} ,ei = 0for i ≥ t .

i=0

We compute αv in advance and we obtain x as follows
1. z := 1 ,2. z := z 2 αyi v ei (mod p) for i = ` − 1, . . . , 1 ,3. x := z .
PThis computation requires at most ` + t − 1 + `i=t yi modular multiplications. If half of the bits yi with i ≥ t are zero, and ei = yi = 0 holds
for one fourth of the i < t, then there are at most ` + 0.5(` − t) + 0.75t =1.5` + 0.25t modular multiplications.
Coexistence of the authentication and the signature scheme.
Some precaution has to be taken if the authentication and the signaturescheme are both used with the same α and p. In this case it is incorrect
to transmit the entire witness x in the authentication protocol. This isbecause the verifier may pose as exam e the hashing h(x, m) of witness
x with any message m. Then the proof of identity (x, y) yields a signature for message m. This attack can be thwarted by transmitting in theauthentication protocol instead of x a hash value (e.g. 72 bits) of x.
9The choice of the prime q.
The prime q must be at least 140
bits long in order to sustain a security level of 272 steps. This is because√
logα (x) ∈ {1, . . . , q} can be found in O( q) steps by the baby step giant√
step method. In order to compute u, v ≤ d qe such that logα (x) = u +©
√√ ªd qev we enumerate the sets S1 = αu (mod p) | 0 ≤ u ≤ d qe and S2 =n√√ oxα−d qev (mod p) | 0 ≤ v ≤ d qe and we search for a common element√

αu = xα−d qev (mod p). The generation of S1 and S2 takes 271 modular
multiplications. Sorting and merging S1 and S2 requires more than 272
steps.
More general groups.
It is possible to implement the above signature
and authentication scheme using a finite group G other than the subgroup
ZZ∗p of units in ZZp . We can use any finite group with an efficient multiplication algorithm and having the property that the discrete logarithm isinfeasible to compute. In the general case we have α ∈ G and the order qof α must have some prime factor that is larger than 2140 . In case that theorder q is publicly known the modification of our basic scheme is straightforward. If we are only given an upper bound M for q then we choose in
the preprocessing phase a random number r in the interval {1, . . . , M } andwe dispense with the reduction modulo q in the protocols for authenticationand signature generation. Examples of suitable groups are e.g. class groups
and elliptic curves E(K) over a finite field K.
The choice of the hash function
attacks:h.

We distinguish two types ofa) Given a message m find a signature for m.
b) Chosen message attack. Sign an unsigned message m of your choice.
We call a function h one–way if for all but a negligible fraction of theoutput values it is infeasible to invert h. The function h is called collision–
free if it is infeasible to generate two inputs with matching outputs.
Attack a) requires to solve the multivariate congruenceh(αy v e (mod p), m) = e
10

in y and e. No method has been found to solve such a congruence since
this type of congruence came up in connection with the ElGamal scheme. In
order to thwart the attack a) the function h(x, m) must be almost uniformwith respect to x in the following sense. For every message m, everye ∈ {0, . . . , 2t − 1} and random x ∈ ZZ∗p the probability probx [h(x, m) = e]must be close to 2−t . Otherwise, in case that for fixed m, e the event
h(x, m) = e has nonnegligible probability with respect to random number
x, the cryptanalyst can compute x := αy v e (mod p) for random y–values
until the equality e = h(x, m) holds. The equality yields a signature (y, e)
for message m. If h(x, m) is uniformly distributed with respect to random
x then this attack requires about 2t steps.
Attack b) can be launched if we are given many pairs (yi , ei ) so thatthe functions h(xi , ·) with xi = αyi v ei (modp) all coincide. Given (yi , ei )for i = 1, . . . , 2t/2 the cryptanalyst can generate messages mj for j =1, . . . , 2t/2 and check whether there exist i, j such that h(xi , mj ) = ei . In
this case he has found a signature (yi , ei ) for message mj . The probabilityof success is about 2t/2 2t/2 2−t = 1. Given the pairs (yi , ei ) the work
load for the attack is about 2t/2 log (t/2) steps. For this the cryptanalyst
sorts the sets S1 = {ei for i = 1, . . . , 2t/2 } and S2 = {h(xi , mj ) for
j = 1, . . . , 2t/2 } and searches for a joint element by merging the sets S1 andS2 . It is important that by assumption h(xi , mj ) does not depend on i. In
order to thwart this attack the function h(x, m) must depend on at least
140 bits of the number x.
In order to thwart the chosen message attack the function h(x, m) must,for all but a negligible fraction of x, be one–way in the argument m.
Otherwise the cryptanalyst can choose y, e arbitrarily, he computes x :=αy v e (mod p) and solves e = h(x, m) for m. This yields a signature formessage m.
It seems not necessary that the function h(x, m) is collision–free withrespect to m. Suppose the cryptanalyst finds messages m and m0 suchthat h(x, m) = h(x, m0 ) for some x = αy (mod p). If he asks for a signature
for m0 then this signature is based on an arbitrary random number x0 and11cannot simply be used to sign m. The equality h(x, m) = h(x, m0 ) only
helps to sign m if a signature (y, e) for m0 is given using this particularx, i.e. x = αy v e (mod p). But if h(x, m) is one–way in m then it isdifficult to solve h(x, m) = h(x, m0 ) for given x, m0 .
By the same reason the analyst cannot simply attack using a weak x,
where h(x, m) is not one–way in m. For this attack he needs to know avalid signature with x. Since the signature protocol generates x as theresult of a one–way function it seems to be sufficient that the fraction of
weak x is negligible. Even though a negligible fraction of weak x does
not seem to hurt the scheme we strongly recommend to use a hash–function
h(x, m) that is one–way in m for each fixed x.
Comparison with ElGamal signatures. An ElGamal signature (y, x)
for the message m and keys v, s with v = α−s (mod p) satisfies theequation αm = v x xy (mod p) and can be generated from a random number
r by setting x := αr (mod p) and by computing y from the equationry − sx = m (mod p − 1) .

(1)

We replace in equation (1) x by the hash value e = h(x, m). Then we caneliminate the right side m in equation (1). We further simplify (1) throughreplacing the product ry by y − r and p − 1 by q. This transforms (1)into the new equation y = r + es (mod q). The new signatures are much
shorter.
Relationship to the Beth authentication scheme. Beth (1988) proposes an authentication scheme in which the user’s private key y is part of
the KAC’s ElGamal–signature (x, y) for the user’s identification number
I. The KAC produces the signature (x, y) when it registers a legitimate
user. Let s, v be the KAC’s private and public ElGamal keys. We havev = α−s (mod p) and αI = v x xy (mod p). Now x and y are taken for theuser’s public and private keys. In order to authenticate himself to a third
party it is sufficient that the user proves knowledge of y. Knowledge ofy means knowledge of the KAC’s signature for the identification number
I. Only the KAC can produce this signature. According to the ElGamal
protocol, y is a well defined discrete logarithm, y = logx (αI v −x ). In the12Beth scheme a user proves knowledge of y using the parallel variant ofprotocol 1 in Chaum, Evertse, Graaf (1988).
The construction of Beth saves a separate signature by the KAC for theuser’s public key. It also saves a separate transmission of this signature in
the authentication protocol as well as its separate verification. The penalty for this two fold. The user must reveal its secret key to the KAC. The
authentication test is less efficient, the verifier has to perform three exponentiations. Beth does not consider signatures related to his authentication
scheme. He works with GF (q), in particular with GF (2n ) instead with
ZZp .
Girault (1990) has proposed a variant of our scheme that is identity based
and which does not reveal the user’s secret key to the KAC.

3The Performance of the Signature Scheme.

We wish to achieve a security level of 272 operations, i.e. the best known
method for forging a signature/authentication should require at least 272
steps. In order to obtain the security level 272 we choose q ≥ 2140 , t = 72
and p ≥ 2512 . The number of multiplication steps and the length of themessage dependent part of signatures are independent of the bit length ofp. Only the length of the public key depends on p. We compare the performance of the new scheme to the Fiat–Shamir scheme (k = 9, t = 8) the
RSA–scheme and the GQ–scheme of Guillou and Quisquater.

# of multiplications

new schemet = 720

Fiat–Shamirk = 9, t = 8
44∗

RSA

GQ

750∗#

180∗

preprocessing

210∗∗

0

0

0

signature verification+

228∗

44∗

>2

108∗

signature generation(without preprocessing)∗)Can be reduced by optimization. Standard optimizations either use
exponents with small Hamming weight or use short addition chains.
13

∗∗ )

Can be greatly reduced using the preprocessing algorithm of section 4
provided that this algorithm is secure.

#)Computing modulo each prime factor of the RSA–modulus reduces thesemodular multiplications to multiplications with twice shorter numbers.

+)This does not include the verification of the pair (I, v) consisting of theuser’s public key v and identification string I.

Fast algorithms for signature verification exist for the RSA–scheme withsmall exponent and for the Micali–Shamir variant of the Fiat–Shamir
scheme. The new scheme is most efficient for signature generation. Recently
Ong and Schnorr (1990) have proposed another variant of the Fiat–Shamir
scheme. For this variant signatures can be generated using about 13 modular multiplications.
# bytes for the new schemepqpublic key v
private key s

64 (32, resp. see below)
17.5
64
17.5

Given the prime q we can choose the prime p so that
2255 < 2512 − p < 2256 .
The particular form of p simplifies the arithmetic modulo p and allows
to store p with only 32 bytes. The particular form of p does provide
no advantage in any of the known discrete logarithm algorithms. This also
holds for the number field sieve algorithm by A.K. Lenstra, H.W. Lenstra,
Manasse and Pollard (1990), see Gordon (1990) and for the cubic sievealgorithm by Coppersmith, Odlyzko and Schroeppel (1986).
# bytes for complete signatures.
If the KAC also uses the newsignature scheme then its signature S for (I, v) is also of the form (e, y)
and is 26.5 bytes long. Then a complete signature consisting of I, v, S, e, yis only about 127 bytes long:14

identification string I

10

bytes

public key v

64

bytes

the KAC’s signature S

26.5

bytes

message dependent partof signature (e, y)

26.5

bytes

127

bytes

Signatures for the new scheme are much shorter than for other schemes.
Fiat–Shamir signatures with k = 9, t = 8 are 531 bytes long. A signature
consists of I (10 bytes) e1,1 , . . . , e9,8 ∈ {0, 1} (9 bytes) and y1 , . . . , y8 ∈ ZZN(8 · 64 = 512 bytes). Signatures in the RSA scheme are 202 bytes long. A
signature consists of I (10 bytes) the users modulus (64 bytes) the KAC’s
signature of the users modulus (64 bytes) and the message dependent partof the signature (64 bytes).
The number of communication bytes for authentication.
We consider the parameters k = 5, t = 4 with security level 2−20 .
I

10

bytes

v

64

bytes

S

26.5

bytes

x(h(x))

64

e

2.5

bytes

y

17.5

bytes

(9)

84.5

(129.5)

bytes

bytes

The amount of communication for the new scheme is much less thanfor the Fiat–Shamir authentication scheme. We compare to the Fiat–
Shamir scheme with k = 5, t = 4 and security level 2−20 . The Fiat–
Shamir authentication requires to exchange 524.5 (304.5) bytes of information. This information consists of I (10 bytes) y1 , . . . , y4 ∈ ZZN (256 bytes),15

e1,1 , . . . , e4,5 ∈ {0, 1} (2.5 bytes) x1 , . . . , x4 ∈ ZZN (4 · 64 = 256 bytes). Usinghash values h(x1 ), . . . , h(x4 ) the latter part of the communication reduces
to 4 · 9 = 36 bytes.

4

Preprocessing the random number exponentiation.

The preprocessing for authentication/signature generation consists of an
exponentiation r 7→ αr (modp) of a random number r ∈ {1, . . . , q}. If q
is 140 bits long this exponentiation can be done using 210 multiplications
modulo p. The exponentiation of random numbers constitutes the core ofother crypto schemes as well, as e.g. the schemes of El–Gamal (1985), Beth(1988) and G”unther (1989). In this section we propose a very efficientalgorithm that simulates the exponentiation of a random number modulo p.
If proven to be secure this algorithm can be used in the preprocessing phaseof our scheme and in the other crypto schemes as well.
The smart card stores a collection of k independent random pairs (ri , xi )for i = 1, . . . , k such that xi = αri (mod p) where the numbers ri are
independent random numbers in {1, . . . , q}. Initially these pairs can begenerated by the KAC. For every signature/authentication the card uses a
random combination (r, x) of these pairs and subsequently rejuvenates thecollection of pairs by combining randomly selected pairs. We use a random
combination (r, x) in order to release minimum information on the pairs(ri , xi ) i = 1, . . . , k. For each signature generation we randomize the pairs(ri , xi ) so that no useful information can be collected on the long run.
It is not necessary to publish the preprocessing algorithm. Each smart
card can have its own secret algorithm for preprocessing. Even though the
preprocessing algorithm may be private it is important to know whether acryptographically secure preprocessing algorithm exists. For this we propose
a specific example algorithm and give some evidence that it is secure even if
the algorithm is public. The algorithm performs an internal randomization
using a random permutation of the numbers 1, . . . , k. After a few rounds ofpreprocessing the new pairs (r1 , x1 ), . . . , (rk , xk ) will be quasi–independent
from the present pairs.

16

Preprocessing algorithm.
Initiation. Load ri , xi for i = 1, . . . , k, ν := 1

(ν is the round number).

1. Pick a random permutation a of {1, . . . , k}.
2. r := rν + 2rν−1 (mod q), x := xν x2ν−1 (mod p), u := r, z := x(here ν − 1 ∈ {1, . . . , k} is the residue of ν − 1(modk)).
Keep r, x for the next signature.
3. FOR i = k, . . . , 1 DO [u := ra(i) + 2u (mod q), z := xa(i) z 2 (mod p)]
4. rν := u, xν := z, ν := ν + 1 (mod k), go to 1 for the next round.
To simplify subsequent discussions we denote a(k+1) = ν and a(k+2) =ν − 1 (mod k). Then one round of preprocessing performs
rν :=

k+2
X

i−1

ra(i) 2(mod q),

xν :=

i=1

k+2
Y

i−1

x2a(i) (mod p) .

i=1

REMARKS.
1) One round of preprocessing takes only 2k + 2 multiplications modulo
p, k + 1 additions modulo q and k + 1 shifts.
2) In practical applications the numbers a(1), . . . , a(k) are generated
by a pseudo–random number generator. This does not weaken thecryptographic security provided that the random generator is perfect.
3) It has been shown in Schnorr (1990) that if the initial numbers(r1 , . . . , rk ) are uniformly distributed over {1, . . . , q} then the uniform
distribution of (r1 , . . . , rk ) is preserved throughout the preprocessing and that any k consecutive r–values, to be used for k consecutive
signatures, are also uniformly distributed.
4) The above preprocessing algorithm has been proposed in Schnorr(1990) with k = 8 and with arbitrary numbers a(1), . . . , a(d) ∈{1, . . . , k} and d ≤ k. De Rooij (1991) has pointed out that thispreprocessing is vulnerable if it is possible to choose in round ν allnumbers a(1), . . . , a(k) to be either ν or (ν − 1) mod k. His attack is
17

thwarted by the requirement that the numbers a(1), . . . , a(k) form a
permutation of 1, . . . , k.
5) No attack is known that constructs the secret key s from signaturesgenerated with the above preprocessing algorithm and which uses lessthan 272 steps in case that k = 8.
Acknowledgement. I wish to thank J. Hastad, S. Micali and J. Pollard
for their comments and the unknown referees for their suggestions.

References.
Beth, T.: Efficient Zero–Knowledge Identification Scheme for Smart
Cards. Advances in Cryptology - EUROCRYPT’88, Lecture Notes in
Computer Science 330 (1988), pp. 77–86.
Brickell, E.F. and McCurley, K.S.:
An Interactive Identification
Scheme Based on Discrete Logarithms and Factoring. Advances in
Cryptology – EUROCRYPT’90, Lecture Notes in Computer Science
473 (1991), pp. 63 – 71.
Chaum, D., Evertse, J.H. and van de Graaf, J.: An Improved Protocol for Demonstrating Possession of Discrete Logarithms and some
Generalizations. Advances in Cryptology - EUROCRYPT’87, Lecture
Notes in Computer Science 304 (1988), pp. 127–141.
Coppersmith, D., Odlyzko, A. and Schroeppel, R.: Discrete Logarithms in GF (p). Algorithmica 1 (1986), pp. 1–15.
ElGamal, T.: A Public Key Cryptosystem and a Signature Scheme Basedon Discrete Logarithms. IEEE Transactions on Information Theory
31 (1985), pp. 469–472.
Feige, U., Fiat, A. and Shamir, A.: Zero–Knowledge Proofs of Identity. Proceedings of STOC 1987, pp. 210–217, and J. Cryptology 1(1988), pp. 77–95.
Fiat, A. and Shamir, A.: How to Prove Yourself: Practical Solutions of
Identification and Signature Problems. Advances in Cryptology CRYPTO’86, Lecture Notes in Computer Science 263 (1987), pp.
186–194.
18

Girault, M. : An Identity–Based Identification Scheme Based on Discrete
Logarithms. Advances in Cryptology - EUROCRYPT’90, Lecture
Notes in Computer Science 473 (1991), pp. 481 – 486.
Goldwasser, S., Micali, S. and Rackoff, C.: Knowledge Complexityof Interactive Proof Systems. Proceedings of STOC 1985, pp. 291–
304.
Gordon, D. : Discrete logarithms in GF (p) using the number field sieve.
TR. Sandia Laboratories (1990).
Guillou, L.S. and Quisquater, J.J.: A Practical Zero–Knowledge Protocol fitted to Security Microprocessor minimizing both Transmission
and Memory. Advances in Cryptology - EUROCRYPT’88, Lecture
Notes in Computer Sciences, 330 (1988), pp. 123–128.
Günther, C.G.: An Identity–Based Key–Exchange Protocol. Advancesin Cryptology - EUROCRYPT’89, Lecture Notes in Computer Science
434 (1990), pp. 29–37.
Lenstra, A.K., Lenstra, H.W.,Jr., Manasse, M.S. and Pollard,
J.M.: The Number Field Sieve. Proceedings of STOC 1990.
Ong, H. and Schnorr, C.P.: Fast Signature Generation with a Fiat
Shamir–like Scheme. Advances in Cryptology - EUROCRYPT’90,
Lecture Notes in Computer Science, 473 (1991), pp. 432 – 440.
Rabin, M.O.: Digital Signatures and Public–Key Functions as intractableas Factorization. Technical Report MIT/LCS/TR–212 (1978).
Rivest, R., Shamir, A. and Adleman, L.: A Method for Obtaining
digital Signatures and Public Key Cryptosystems. Comm. ACM
21 (1978), pp.120–126.
de Rooij, P.J.N. : On the Security of the Schnorr Scheme using Preprocessing. Proceedings EUROCRYPT’91.
Schnorr, C.P. : Efficient Identification and Signatures for Smart Cards.
Advances in Cryptology - CRYPTO’89. Lecture Notes in Computer
Science 435, (1990), pp. 239 – 252.

19

References.
Beth, T.: Efficient Zero–Knowledge Identification Scheme for Smart
Cards. Advances in Cryptology - EUROCRYPT’88, Lecture Notes in
Computer Science 330 (1988), pp. 77–86.
Brickell, E.F. and McCurley, K.S.:
An Interactive Identification
Scheme Based on Discrete Logarithms and Factoring. Advances in
Cryptology – EUROCRYPT’90, Lecture Notes in Computer Science
473 (1991), pp. 63 – 71.
Chaum, D., Evertse, J.H. and van de Graaf, J.: An Improved Protocol for Demonstrating Possession of Discrete Logarithms and some
Generalizations. Advances in Cryptology - EUROCRYPT’87, Lecture
Notes in Computer Science 304 (1988), pp. 127–141.
Coppersmith, D., Odlyzko, A. and Schroeppel, R.: Discrete Logarithms in GF (p). Algorithmica 1 (1986), pp. 1–15.
ElGamal, T.: A Public Key Cryptosystem and a Signature Scheme Basedon Discrete Logarithms. IEEE Transactions on Information Theory
31 (1985), pp. 469–472.
Feige, U., Fiat, A. and Shamir, A.: Zero–Knowledge Proofs of Identity. Proceedings of STOC 1987, pp. 210–217, and J. Cryptology 1(1988), pp. 77–95.
Fiat, A. and Shamir, A.: How to Prove Yourself: Practical Solutions of
Identification and Signature Problems. Advances in Cryptology CRYPTO’86, Lecture Notes in Computer Science 263 (1987), pp.
186–194.
Girault, M. : An Identity–Based Identification Scheme Based on Discrete
Logarithms. Advances in Cryptology - EUROCRYPT’90, Lecture
Notes in Computer Science 473 (1991), pp. 481 – 486.
Goldwasser, S., Micali, S. and Rackoff, C.: Knowledge Complexityof Interactive Proof Systems. Proceedings of STOC 1985, pp. 291–
304.
Gordon, D. : Discrete logarithms in GF (p) using the number field sieve.
TR. Sandia Laboratories (1990).
20

Guillou, L.S. and Quisquater, J.J.: A Practical Zero–Knowledge Protocol fitted to Security Microprocessor minimizing both Transmission
and Memory. Advances in Cryptology - EUROCRYPT’88, Lecture
Notes in Computer Sciences, 330 (1988), pp. 123–128.
Günther, C.G.: An Identity–Based Key–Exchange Protocol. Advancesin Cryptology - EUROCRYPT’89, Lecture Notes in Computer Science
434 (1990), pp. 29–37.
Lenstra, A.K., Lenstra, H.W.,Jr., Manasse, M.S. and Pollard,
J.M.: The Number Field Sieve. Proceedings of STOC 1990.
Ong, H. and Schnorr, C.P.: Fast Signature Generation with a Fiat
Shamir–like Scheme. Advances in Cryptology - EUROCRYPT’90,
Lecture Notes in Computer Science, 473 (1991), pp. 432 – 440.
Rabin, M.O.: Digital Signatures and Public–Key Functions as intractableas Factorization. Technical Report MIT/LCS/TR–212 (1978).
Rivest, R., Shamir, A. and Adleman, L.: A Method for Obtaining
digital Signatures and Public Key Cryptosystems. Comm. ACM
21 (1978), pp.120–126.
de Rooij, P.J.N. : On the Security of the Schnorr Scheme using Preprocessing. Proceedings EUROCRYPT’91.
Schnorr, C.P. : Efficient Identification and Signatures for Smart Cards.
Advances in Cryptology - CRYPTO’89. Lecture Notes in Computer
Science 435, (1990), pp. 239 – 252.

21

α, q, p, h.
I, s, v, (S)&I, v, (S)−−−−→check I, v, (S)

h(x)
−−−−→
e
←−−−−

pick random e

y
−−−−→

x := αy v e (mod p)

pick random r
x := αr (mod p)

y := r + se (mod q)

check that h(x) = h(x)proververifier
Figure 1: authentication
α, q, p, hmessage m.

I, s, v, (S)&I, v, (S)−−−−→check I, v, (S)

e, y
−−−−→

x := αy v e (mod p)

pick random r
x := αr (mod p)
e := h(x, m)
y := r + se (mod q)

check that e = h(x, m)
signature generation

signature verification

Figure 2: signature generation and verification
22