EFFICIENT

IDENTIFICATION
FOR

SMART

AND SIGNATURES
CARDS

’

C.P. Schnorr
Universitdt Frankfurt

1. Introduction
We present
an efficient
interactive
identification
scheme and a related
signature
scheme
that
are
based
on discrete
logarithms
and
which
are
particularly
suited for smart cards. Previous
cryptoschemes,
based on the discrete
logarithm,
have been proposed
by El Gamal
(1985), Chaum,
Evertse,
Graaf
(1988), Beth (1988) and Gunter
(1989). The new scheme comprises
the following
novel features.
(1) We propose
an efficient
algorithm
to preprocess
the exponentiation
of
random numbers.
This preprocessing
makes signature
generation
very fast. It also
improves
the
efficiency
of
the
other
discrete
log-cryptosystems.
The
preprocessing
algorithm
is
based
on
two
fundamental
principles
local
randomization and internal randomization.
(2) We use a prime modulus
p such that p-l has a prime factor q of appropriate
size (e.g. 140 bits long) and we use a base a for the discrete logarithm
such that
a’ = 1 (mod p). All logarithms
are calculated
modulo q. The length of signatures
is about 212 bits, i.e. it is less than half the length of RSA and Fiat-Shamir
signatures.
The number
of communication
bits of the identification
scheme is
less than half that of other schemes.
The new scheme minimizes
the work to be done by the smart card for
generating
a signature
or for proving
its identity.
This is important
since the
power of current
processors
for smart cards is rather limited.
Previous
signature
schemes require
many modular
multiplications
for signature
generation.
In the
new scheme signature
generation
costs about
12 modular
multiplications,
and
these multiplications
do not depend on the message/identification,
i.e. they can
be done in preprocessing
mode during the idle time of the processor.
The

security

exponentiation

Q

(Ed.):

0 Springer-Verlag

the

y c-c CZ’ (mod

european patent

G. Brassard

of

application

scheme

relies

on

p), i.e. we assume

89103290.6

from

Advances in Cryptology - CRYPT0
Berlin Heidelberg 1990

the

one-way

that discrete

property
logarithms

24.2.1969

‘89, LNCS 435, pp. 239-252,

1990.

of
with

the

240

base Q a r e difficult to compute. The security of the preprocessing is established
by information theoretic arguments.
This abstract is organised as follows. We present in section 2 a version of the
signature scheme t h a t uses exponentiation of a random integer. In section 3 we
propose a n efficient algorithm t h a t simulates this exponentiation. We study its
security i n section 4. T h e performance of the scheme is exemplified in section 5.

2. T h e identification and signature scheme

Notation. For n E H let Z, be the ring of integers modulo n. We identify Z,
with the set of integers (1,...,n)*
Ioitiation of the key authentication center (KAC). The KAC chooses

.
.
.
.

primes p a n d q such that q I p-1, q 2 2 140, p L 2 612 ,

ct E

Z, with order

q, i.e. aq

-

1 (mod p), a

91,

a one-way hash function h : Z, x Z -+ (0,...,2 -1) ,
its own private and public key.
The KAC publishes p,q,a,h a n d its public key.
t

COMMENTS. The KAC's own keys are used f o r signing the public keys issued
by the KAC. The KAC can use f o r its own signatures any public key signature
scheme, e.g. RSA, Fiat-Shamir, Rabin or the new scheme presented here. T h e
hash function h i s only used f o r signatures and is not needed f o r identification.
The function h outputs random numbers i n (0,...,2t-l]; f o r the choice of the
function h see the end of section 2. The security number t can depend on the
application intended, we consider t
72. The scheme is designed such t h a t
P

forging a signature or a n identification requires, with t = 72, about 2

7a

steps.

Registration of users. When a user comes to the KAC f o r registration the KAC
verifies its identity, generates a n identification string I (containing name,
address, ID-number etc.) a n d signs the pair (1,v) consisting of I and the user's
public key v. The user can generate himself his private key s a n d the
corresponding public key v.
The user's private a n d public key. Every user has a private key s which is a
random number i n {1,2, ...,q). The corresponding public key v is the number v =
Q

-I

(mod p).

Once the private key s has been chosen one can easily compute the
corresponding public key v. The inverse process, to compute s from v, requires
to compute the discrete logarithm with base Q of v-*, i.e. s -log, v

24 1

The following protocol is related to protocol 1 in Chaum, Evertse, Graaf (1988);
i t condenses this protocol t o a single round.
The Identification protocol
(Prover A proves its identity to verifier B)
1. Initialion. A sends t o B its identification string I and its public key v. B
checks v by verifying KAC's signature transmitted by A.
2. Preprocessing. A picks a random number r E (1,...*q- l), computes x := a
' (mod
p), and sends x to B (see section 3 f o r an efficient simulation of this

exponentiation).

3. B sends a random number e E (0 ,...,2 -1) to A.
4. A sends to B y := r + se (mod q ) .
5 . Identification t e s t . B checks t h a t x = aY V' (mod p) and accepts A's proof of
identity i f f equality holds.
t

Obviously i f A a n d B follow the protocol then B always accepts A's proof of
identity. We next consider the possibilities of cheating f o r A and B. W e call
(x,y) the proof a n d e the e x a m of the identification. The proof (x,y) (the exam
e, resp.) is called straight i f A (B, resp.) has followed the protocol, otherwise the
proof (exam, resp.) is called crooked.
A fraudulent A can cheat by guessing the correct e and sending the crooked

proof
x := ar 'V (mod p),

y := r

.

The probability of success f o r this attack is 2-t. By the following proposition
this success rate cannot be increased unless computing log,v is easy.
Proposition 2.1 Suppose there is a probabilistic algorithm A L with time bound
VLI which takes f o r input a public k e y v and withstands, with probability E >
* the identijication test f o r a straight exam. Then the discrete logarithm of v
can be computed in time O(IALI/&) and constant, positive probability.

2-'+'

Proof. This is similar to Theorem 5 in Feige, Fiat, Shamir (1987). The following
algorithm AL' computes log,v.
1. Repeat the following steps a t most 1/& times: generate x the same way as does
algorithm AL, pick a random e' in (0, ...,2 -1) and check whether A L passes
the identification test f o r (x,e'); if A L succeeds then f i x x and go to 2.
t

2. Probe 1 / ~random numbers en i n (0,...,2t-1) . If algorithm A L passes the
identification test f o r some en that is distinct from e' then go to 3 a n d
otherwise stop.
3. Choose the numbers y', y" which A L submits to the identification test i n
response to e', e". (y'-y" is the discrete logarithm of v " - ~ ' (mod P).)
4. Output (y'-y")/(e"-e') (mod q)

.

242

W e bound from below the success probability of this algorithm. T h e
algorithm finds i n step 1 a passing pair (x,e') with probability a t least
probability a t least

a,
1

i.
With

the x chosen in step 1, has the property that A L

' $ s-fraction

withstands the identification test for at least a

of all

e E

(0, ...,2 -1). For such a n x step 2 finds a passing number en that is distinct from e'
with probability a t least
t

1 - (l-s/2)'/" > 1 - 2.7-'/* > 0.3 .
This shows that the success probability of the algorithm is at least 0.3/4.

0

The verifier B is free to choose the bit string e i n step 3 of the
identification protocol, thus he can try to choose e i n order to obtain useful
information from A. The informal (but non rigorous) reason that A reveals no
information is t h a t the numbers x and y are random. The random number x
reveals no information. Furthermore i t is unlikely that the number y reveals a n y
useful information because y is superposed by the discrete logarithm of x, y
log,x + e s (mod q) , and the cryptanalyst cannot infer r = logax from x. The
scheme is not zero-knowledge because the tripe1 (x,y,e) may be a particular
5

.

solution of the equation x = aYve (mod p) due to the fact that the choice of e
may depend on x.
Minimizing the number of communication bits. We can reduce the number of
communication bits for identification. For this A sends i n step 2 h(x) (instead
of x) and B computes i n step 5

x := aYve(mod p)

and checks that h(x) = h(x).

It is not necessary that h is a one-way function because x = 'a (mod p ) is
already the result of a one-way function. We can take for h(x) the t least
significant bits of x. The total number of communication bits for h(x),e,y is 2t
+ 140 which is less than half that of other schemes. The transmission of e is not
necessary, e can be fixed to h(x). Then the pair (y,h(x)) is a signature of the
empty message w i t h respect to the following signature scheme.
Protocol for signature generation.
To sign message m using the private key s perform the following steps:
1. Preprocessing (see section 3 ) . Pick a random number r E (1. ...,q) and
compute x := ar(mod p).
t

2. Compute e := h(x,m) E (0 ,...,2 -1).
3. Compute y :a r + se (mod q) and output the signature (e,y).

Protocol for signature verification.
T o verify the signature (e,y)
compute

x = 'a

V
'

for

message

m

and

public

(mod p) and check that e = h(x,m) (signature test).

key

v

243

A signature (e,y) is considered to be valid if i t withstands the signature test.
A signature generated according to the protocol is always valid since
With t

=

72 and q

-

x = ar = ar + a e v' = a' ve (mod p)
2"'

.

the signature (e,y) is 212 bits long.

Efficiency. The work f o r 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 w i t h a modular multiplication in the RSA-scheme.

-

Signature verification consists mainly of the computation of x = a' ve
(mod P) which can be done on the average using 1.5 I + 0.25 t multiplications
modulo P where 1 = rlog2ql is the bit length of q. For this let y and e have
the binary representations
I-1

y =

i=O

yi2' , e

-

1-1

i =O

ei2

i

We compute a v i n advance and we obtain
1. i : = l , z : = l ,

x as follows

z := za ayi v * ~
(mod p)]

2. while i 2 0 do [i := i-1,

3.

.

with yi,ei E (0,l) , ei = 0 for i I t

x:- z .

This computation requires a t most I + t

I

- 1 + i=t
C yi

,

modular multiplications. If

half of the bits yi with i 2 t a r e zero, and ei = y i = 0 holds for one fourth of
the i < t , then there a r e a t most 1.5 I + 0.25 t modular multiplications.
Comparison with ElGamal signatures. An ElGamal signature (y,x) f o r the
message m and keys v,s with v = a-' (mod p) satisfies the equation am = v X xY
(mod p) and can be generated from a random number r by setting x := a' (mod
p) and by computing y from the equation
ry sx = m (mod p-1)
(1)
We replace in equation (1) x by the hash value e = h(x,m) Then we can
dispense with the right side m i n equation (1) which we make zero. We further
simplify (1) in t h a t we replace the product ry by y-r and p-1 by 9. This
transforms (1) into the new equation y = r + es (mod q ) The new signatures
are much shorter.

-

.

.

The choice of the prime q. The prime q must be at least 140 bits long i n order to
sustain a security level of 2" steps. This is because
found i n O(&)

u,v 5

r-&l

log,(x) E (1, ...,q)

can be

steps by the baby step giant step method. In order to compute
such t h a t

(a"(mod p) 10 I u 5

log,(x)

r61)

=

u

+

r&lv

we enumerate the sets Si

and S2 = {x a -rfilV (mod p)

and we search f o r a common element a" =

XQ

- rG1v

(mod p)

Io5

.

v 5

=

rJsii

244

The choice of the hash function h. We distinguish two types of attacks:
a ) Given a message m f i n d a signature f o r m,
b) chosen message a t t a c k . Sign a n unsigned message by using signatures of
messages of your choice.
In order t o thwart the attack a ) the function h(x,m) must be almost uniform
with respect t o x i n the following sense. For every message m, every e E
(0,...,2t-1)

a n d random x E Z i the probability probJh(x,m) = el must be near

to 2-t. Otherwise, i n case that for fixed m,e the event h(x,m) = e has
nonnegligible probability with respect to random x, the cryptanalyst can

-

compute x := a' re (mod p) for arbitrary 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

2' steps.
In order to thwart the chosen message attack the function h(x,m) must be
one-way in the argument m. Otherwise the cryptanalyst can choose y,e

-

arbitrarily, he computes x := a' ve (mod p) and solves e
Then he has found a signature f o r an arbitrary message m.

=

h(x,m)

f o r m.

It is not necessary t h a t the function h(x,m) is collision-free with respect to
m. Suppose the cryptanalyst finds messages m and m' such that h(x,m) = h(x,m')

-

.

f o r some x 'a (mod p) If he asks f o r a signature f o r m' then this signature is
based on a new random number x' a n d cannot simply be used to sign m. The
equality h(x,m) = h(x,m') only helps t o sign m if a signature (y,e) f o r m' is
given such that x = 'a v* (mod p) , But if h(x,m) is one-way in m then i t is
difficult to solve h(x,m) = h(x,m') f o r given x,m'.

3. Preprocessing the random number exponentiation

We describe an efficient method f o r preprocessing the random numbers r
and x := a' (mod p), t h a t are used for signature generation. This preprocessing
mode also applies to other discrete log-cryptosystems such as the schemes by
ElGamal (1985), Beth (1988) and G h t e r (1989).
The smart c a r d stores a collection of k independent random pairs (ri,xi) f o r
i=l, ...,k such t h a t xi = ari (mod p) where the numbers ri are independent
random numbers i n ( I , ...,q). Initially these pairs can be generated by the KAC.
For every signature/identification the card uses a random combination (r,x) of
these pairs a n d subsequently rejuvenates the collection of pairs by combining
randomly selected pairs. We use a random combination (r,x) in order t o release
minimum information on the pairs (ri,xi) i = I, ...,k . For each signature
generation we randomize the pairs (ri,xi) so that no useful information can be

245

collected on the long run. We give an example of a preprocessing algorithm t h a t
demonstrates the method. It uses a security parameter d, f o r all practical
purposes d a n d k c a n be f a i r l y small integers, f o r this paper we assume that 6 I
d,k .
Preprocessing algorithm
Initiation Load q,xi f o r i-1, ...,k , v := 1 ( v is the round number).
1. Pick random numbers a(0), ...,a(d-3) E {l,...,k), a(d-2) := a(d) := v-1 (mod k),
a(d-1) :- v .
2.

d

rv :=

C
i=O

ra(i) 2' (mod 9 ) ,

n
d

X,

:=

i=O

Xa(i)

(mod P)

9

(Below we give a detailed algorithm f o r this computation.)
3. Keep f o r the next signature/identification the pair r, x with
old

+ 2.rW-l(mod q), x := x,
r := r;"
4. v := v+l (mod k ) , go to 1 f o r the next round.

. xv-l
2
(mod p).

REMARKS. 1. By t h e choice of a(d-1) the preprocessing preserves the uniform
distribution on (r1, ...,rk).
2. The setting a(d) :- v-1 (mod k ) has the effect that step 2 shifts the binary
representation of rv-l f o r d positions to the left a n d subsequently adds i t t o r,.
Theorem 4.2 relies on t h e choice of a(d-1). Lemma 4.3 relies on the choice a(d),
and Theorem 4.4 relies on the choice of a(d-2), a(d-1) and a(d).
3. The preprocessing algorithm must not be public. Each smart card can have its
own secret algorithm f o r preprocessing. There are many variations of the above
technique. It is possible to take f o r (ra(i),xa(i)) with 0 I i < d-2 the key pair
(-S,V).
We describe step 2 of the preprocessing algorithm in detail. Step 2 can be done
using only 2d multiplications modulo p, d additions modulo q and d shifts.
Step 2 of t h e preprocessing algorithm.
1. u := r a p ) , 2 := Xa(d) , i := d-1
a
2. while i L 0 do [u := 2u + ra(i) (mod q) , z := z xa0) (mod p) ,
if i = d-1 then (r := u, x := z) , i := i-l]
3. r, := u , x, := z .

.

.

4. Cryptanalysls

of preprocessing

The preprocessing algorithm combines two fundamental principles local
randomization and internal randomization. The pairs (r,x) that are used f o r
signatures a r e locally random i n the sense that every k consecutive pairs a r e
independent, see Theorem 4.2. The random indices a(0), ...,a(d-3) perform a n
internal randomization. The principles of local and of internal randomization
are complementary a n d can also be used for the construction of pseudo-random

246

number generators a n d hash functions.
Notations. We denote the number a(i) of round Y as a(i,u). Let T, be the kxk
integer matrix t h a t describes the transformation of the numbers r1, ...,rk i n
round u of the preprocessing algorithm, i.e. step 2 of round u performs rT := T,

.

T

r (mod q ) where r = (rl, ...,rk) For j L 0 let r; be the number r a f t e r j
rounds. The sequence of r-values that is used f o r signatures is ri,ri, ...* r i

.

k

Lemma 4.1 I f the initial vector (rl ,...,rk) i s uniformly distributed over (1, ...,q)
d
then this distribution i s preserved throughout the preprocessing provided that 2 <
4 .

Proof. T, is the identity matrix except f o r row u. Row u is determined by the
transformation of r, i n step 2:

where det T,

-

r, := r, (det T,)

C

2'

. It

+

C

ra(i,,) 2' (mod q)

a(i,u)#J

follows from a(d-1,u)

= u

a(ip)=Y

d

and a(d,u)

u that

.

det T, is a nonzero integer a n d thus 1 I det T, < 2 < q We see t h a t T, is
invertible modulo q. Therefore T, preserves the uniform distribution on
{I*...,qIk

-

0

A similar argument proves the next theorem.

Theorem 4.2 I f the initial vector (r1, ...,rk) is uniformly distributed over {l,...,q}
then f o r all j 1 0 and f o r a l l numbers a(i,u) , 0 Ii Id-3 , u I k+j the vector
k

(ri+j,...*rz+j) i s , f o r s u f f i c i e n t l y large q , uniformly distributed over (1, ...,q )

k

.

I t is a n open problem whether the vector (r;lr...,r:k)
is uniformly
distributed f o r a l l indices 1 s i t < i z ... < ik We believe that this holds f o r a l l
but a negligible fraction of the instances f o r a(i,u) 1 5 u 5 ik .

.

Because of Theorem 4.2 the cryptanalyst can only attack a sequence of more
than k consecutive signatures/identifications. The set of the first k+l signatures
can be attacked by guessing the numbers a(0), ...,a(d-3) of the first k rounds.
Given these numbers a n d the first k + l signatures the cryptanalyst can determine
the secret key s a n d the initial numbers rl, ...,rk by solving a system of k + l
linear equations modulo q. This attack requires an exhaustive search over k
cases.

(d-2)k

Let rnyer be the number r, after u rounds of preprocessing. If q and the
numbers a(0), ...,a(d-3) f o r u rounds a r e fixed then the number myw is a
function of the i n i t i a l numbers r1, ...,rk which is linear over Z,.

247

Lemma 4.3

Pairwise distinct instances f o r the numbers

a(0),...,a(d-3)

of v

rounds generate, f o r sufficiently large q , pairwise distinct linear functions r?"
n *w

r,

(r1, ...,rk) depending on the initial numbers

TI,..

=

.,rk and q.

Proof. Let S, := T, T,-l -.. TI be the product matrix that describes the
transformation on r f o r the first v rounds of preprocessing. This is a n integer
matrix that does not depend on q. The dominant row (i.e. the row with the
maximal entry) of S, is the row v(mod k), call this row vector s,. We show how
to decipher all numbers a(i) of the first v rounds from s,. To simplify the
argument let a(i,l) f o r i=O, ...,d be pairwise distinct. Then the j-largest entry of
s, is in column a(d-j+l,l) for j-0, ...,d. (In general we can determine from the
relative size of the largest entries of s, which of the numbers a(i,l) coincide.)
This clearly holds f o r v = 1 and the induction step from v 1 to v follows
from a(d,v)
v-1 (mod k). This shows how to obtain from s,, the matrix TI.

-

-

Given the matrix TI we form the vector s, Ti' which is the dominant row of
the matrix T, T,-1 .-.Tt that corresponds to v-1 rounds starting with round
number 2. Thus we can decipher i n the same way the numbers a(i.2) for i=l,...,d
and the matrix T2 from s, Ti'. Recursively we obtain from s, all numbers a(i)
of the first Y rounds. Now the claim follows from the equation
=

n.r

s,, rT (mod q)
rU
where r = (r1, ...,rk) i s the initial r-vector.

0

k
For random i n p u t (rl ,...,rk) E (a,) two distinct linear functions over Z,
give the same output w i t h probability l/q. Therefore if the number of choices

for a(0), ...,a(d-3) over v rounds is about q then the number r";
randomised by the numbers
quasi-independent of r1, ...,rk

.

a(0), ...,a(d-3)

is completely

of v rounds, and thus r?"

is

Let a be the vector a = (a(i,v) I i=O,...,d-3, v = l ,...,k) . The number rL+1 is
determined by r l ,..., rk , q and a. We know from Theorem 4.2 that the linear
transformation (rl, ...,rk)
2

.

-

+

.

( r l , ...,rk) is invertible modulo q. Therefore we have
.

1

.

a function rk+1 = rk+l(rl ,...,rk,q,a) that is linear in rl ,...,rk over 2,. By the
next theorem distinct instances of a yield, for sufficiently large q, distinct
functions r;+1 i n r i , ...,r i

.

Theorem 4.4 Pairwise distinct instances for the numbers a(0), ...,a(d-3) o f the
first k rounds generate, f o r sufficiently large q , pairwise distinct linear functions
r;+l depending on r i , ...,r l .
Proof. We show that distinct vectors a generate, for sufficiently large q , distinct
linear functions ri+l(rI,...,rk,q,a)
where the inputs are the initial numbers

248

rl, ...,rk.

Let

s;+1

be

the

coefficient

vector

of

the

linear

function

r;+l(rI, ...,rk,q,a), i.e. r;+l (r1, ...,rk,q,a) = s;+1 r (mod q ) with r = (rl, ...,rk) . BY
the method in the proof of Lemma 4.3 we can decipher from s;+1 a l l numbers
a(i) of the first k rounds.
T

Now the claim follows from the choice a(d-2,v) = v-1 (mod k) . I t follows
by a n argument t h a t is similar b u t more involved than the one for the proof of
Lemma 4.3.
0
T h e fastest attack to the preprocessing algorithm that we a r e a w a r e of
enumerates the linear functions

.

*

*

rk+l(rl,...,rk,q,a)

that have high probability;

the probability space is the set of all vectors a. For the security level 272 i t is
necessary that t h e maximal probability f o r these linear functions is not much

. . .

larger t h a n 2-72. In order to break the preprocessing i t is sufficient to guess two

.

*

.

functions rk+l(rl, ...,rk,q,a) a n d rk+2(r2,...,rk+l,q,a) . Given these two functions
we can uncover the secret key s from the first k+2 signatures by solving a
system of linear equations.
We finally consider attacks on arbitrarily many signatures from a d i f f e r e n t
point of view. The problem t o recover the secret key s and the initial numbers
r1, ...,rk when the f i r s t n signatures are given, can be put into the following
form.
integers y1, ...,yn E (1,...,q} and el ,...,en E Z
integers s,r1. ...,rk E (l,...,~) such that there exist integers t i j , 0 I t i j <

Given
Find

k

2i (d +1)

, satisfying yi = eis +

1 t i j rj (mod

j=1

q)

i = l ,...,n

.

(4.1)

* .

The searched integers t i j are from the linear transformation

( r l , ...,r n )

(r1,...,rk)

-

, hence 0 I t i j -< 2i(d+l) If k(d-2)k > q the equation (4.1) is, f o r
i(d+l)
almost all yl,el, ...,y,,en.s,rl ,...,rk , solvable for ti2 such that 0 I t i j < 2
This makes this attack useless. However if

k and d are small the solvability of

i(d+l)

may characterize the searched numbers
equation (4.1) with 0 5 ti8 .c 2
rl, ...,rk . It is interesting to determine the complexity of finding r1, ...,rk such
that (4.1) is solvable with "small" integers tij. It seems that this problem is more
difficult than the knapsack problem since in our case all knapsack items s and
r1, ...,rk are unknown.
Conclusion.
There is a trade-off between the parameters k a n d d. It is
sufficient to have q L 214' , k = 8 and d = 6 , then k')2-'(
= 296 . It is
possible to further reduce k and d but we must have k

(d-2)k

2 2

72

.

249

5. The performance of the signature scheme

We wish to achieve a security level of 272 operations, i.e. the best known
method f o r forging a signatures/identification should require at least Z7' steps.

a n d t = 72 . We
In order t o obtain the security level 272 we choose q 2 2"'
choose f o r the preprocessing algorithm, the parameters k = 8, and d = 6. For
the new scheme the number of multiplication steps and the length of signatures
are independent of the bit length of p. Only the length of the public key
depends on p. For this we assume that p is 512 bits long. We compare the
performance of the new scheme to the Fiat-Shamir scheme (k=8, t-9) the
RSA-scheme and the GQ-scheme of Guillou and Quisquater.

#

of multiplications

new scheme
t-72

Fiat-Shamir
k-8 , t-9

RSA

GQ

216*

signature generation
(without preprocessing)

0

451

750;

preprocessing

12*

0

0

228*

45*

1 2

signature verification

0

108*

*) can ba reduced by optimiiation

Fast algorithms f o r signature verification exist for the RSA-scheme with small
exponent and f o r t h e Micali-Shamir variant of the Fiat-Shamir scheme. T h e
new scheme is most efficient f o r signature generation.
# bytes f o r the new scheme
System parameters p,q
a
public key v
private key s
signature (e,y)
preprocessing (ri,Xi) i=1, ...,8 (6, resp.)
ll

We can choose particular primes

82.5 (26, resp. see below)
64
64
18.5
26.5

660 (495, resp. see below)

q and p such that

lq-2*'01 I 240 , 1 ~ - 2 ~ ~ ~. l
The particular f o r m simplifies the arithmetic modulo q and modulo p, a n d
requires only 2 6 bytes to store p and q. We are not aware of any disadvantage of
this particular form f o r p a n d q. In total about 800 (635, resp.) bytes EEPROM
are sufficient to store p,q,v,e,y and (ri,xi) for i-1, ...,8 (6, resp.), a is not needed
f o r signature generation. About 192 bytes R A M a r e necessary to perform
modular multiplications with a 512 bit modulus p. The program for signature
generation requires less t h a n 500 bytes ROM.

250

Optimization. We give a variant of the preprocessing algorithm that uses only
k=6 pairs (ri,Xi) a n d which require on the average 12.76 modular multiplications
per round. First let k-6 a n d let (r7,xV) be the pair (-s,v).
Optimized preprocessing
1. r := r,,-l + r,, (mod q) , x :=
x, (mod p) ,
keep the pair r, x f o r the next signature/identification,
u := r + rU-1(mod q) , z := x
(mod p)
2. f o r j = 1,...,4 do
[pick with probability 7-3/29, 7/29, 1/29 resp.
2 , 1 , 0 resp. distinct random numbers a E (1,...,7) .
+

-

u := 2u +

1
ra (mod q) ,
a

z := z

2

IT x,
a

(mod p)].

3. r,, := u, x,, := z, u := v + l (mod 7), go to 1 for the next round.

The number of possible transformations per round is about [7.3 + 7 + l]' =
29'. The number of possible transformations over 6 rounds is about 29'" CCI 211*
which is sufficiently large to perform an internal randomization. The average
number of modular multiplications is 6 + 4(2.7.3 + 7) / 29 w 12.76 .

We can f u r t h e r reduce either the number of pairs (ri.xi) or the number of
modular multiplications by inserting write operations into step 2 of the
preprocessing. We can a t the end of the inner loop of step 2 decide, based on a
coin flip, whether to replace some pair (ra,x.) by (u,z). This will increase the
number of possible transformations per round. However this variant will only be
practical if write operations are sufficiently fast.
Acknowledgement I wish to thank J. Hastad for his criticism of the previous
version of the preprocessing algrithm.

References
BETH, T.: A Fiat-Shamir-like authentication protocol for the ElGamal scheme.
Proceedings of Eurocrypt' 88, Lecture Notes in Computer Science 330, (1988) pp.
77-86.
CHAUM, D., EVERTSE, J.H. and van de GRAAF, I.: An Improved protocol f o r
Demonstration Possession of Discrete Logarithms and some Generalizations.
Proceedings of Eurocrypt' 87, Lecture Notes i n Computer Science 304, (1988).
pp. 127-141.
COPPERSMITH, D., ODLYZKO, A. and
Logarithms. Algorithmica 1, (1986), pp. 1-15.

SCHROEPPEL,

R.:

Discrete

251

ELGAMAL, T.: A Public Key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms. IEEE Transactions on Information Theory 3 1 (198% pp.
469-472.

FEIGE, U., FIAT, A. a n d SHAMIR, A.: Zero knowledge proofs of identity
Proceedings of STOC 1987, pp. 210-217.
FIAT, A. and SHAMIR, A.: How to Prove Yourself: Practical Solutions of
Identification and Signature Problems. Proceedings of Crypto 1986, i n Lecture
Notes i n Computer Science (Ed. A. Odlyzko), Springer Verlag, 263, (1987) pp.
186-194.

GOLDWASSER, S., MICALI, S. and RACKOFF, C.: Knowledge Complexity of
Interactive Proof Systems. Proceedings of STOC 1985, pp. 291-304.
GONTER, C.G.: Diffie-Hellman and ElGamal protocols with one single
authentication key. Abstracts of Eurocrypt' 89, Houthalen (Belgium) April 1989.
MICALI, S. and SHAMIR, A.: An Improvement
Identification and Signature Scheme. Crypto 1988.

of

the

Fiat-Shamir

QUISQUATER, J.J. a n d GUILLOU, L.S.: A practical zero-knowledge protocol
fitted to security microprocessor minimizing both transmission and memory.
Proceedings Eurocrypt' 88. Springer Verlag, Lecture Notes in Computer Sciences,
VOI.
330, (1988), pp. 123-128.
RABIN, M.O.: Digital signatures and public-key functions as intractable a s
factorization. Technical Report MIT/LCS/TR-212 (1978).

J
I,S,V

check I , v

pick random r

x :=

y := r

Q~

pick random e

(mod p)

+ se

x := aYve(mod p)

(mod q)

check that
h(x) = h(y)

verifier

identification

prover

FIG. 1

clA9P.h
message m

J

I,v,

x :=

gr

(mod p)

e,y>

+ se

-

x :=

Q’

ve (mod p)

check that

e := h(x,m)
y := r

check I , v

e = h(x,m)

(mod q)

signature verification

signature neneration
FIG. 2