Evaluation Report on the ECDSA signatureschemeJacques Stern

1

Introduction

This document is an evaluation of the ECDSA signature scheme. Our work is basedon the analysis of various documents [1, 32, 10, 11], which provide the specification of
the scheme, as well as on various research papers related to the scheme. Among theseresearch papers are the original work of Poincheval and Stern [33, 34] investigating thesecurity of El Gamal-like signatures, and the series of papers related to the so-called
generic model [29, 45, 27, 6]. Of particular interest to the present report is [6], whichapplies the generic model to argue towards the security of ECDSA.
The present report is organized as follows: firstly, we briefly review the cryptographic primitive on which the signature scheme relies, namely the discrete logarithm
problem on elliptic curves (ECDL), and analyze the various algorithms that are currently known to solve the problem. We specifically address the case of curves of special
form, since some of the recommended examples proposed in the standard [11] are
Koblitz curves. Next, we give formal definitions for signature schemes and recall thestrongest security notion that is now mandatory for signature schemes: security against
existential forgery under adaptive chosen-message attacks. We also provide a short history of the various signature schemes based on the discrete logarithm problem, and of
the various strategies used to support their security: the random oracle model and thegeneric model. This allows us to prove the security of the generic version of ECDSA,
against adaptive chosen-message attacks. We finally analyze the meaning of this proof,
with respect to the actual ECDSA signature scheme. In particular, we discuss whether
one can derive practical implications, notably in terms of key sizes. This is as requested
by IPA.

1

2

ECDSA and the Elliptic Curve Discrete Logarithm Problem

2.1

General setting

The discrete logarithm problem in a finite group G can be stated as follows: computex from g and y = x · g. Integer x is called the discrete logarithm of y in base g,
x = logg (y). We will restrict our attention to the case where G is a finite cyclic group
G of prime order q and g is a generator of G. In the above, we use bold letters todenote elements of G, so that no confusion arises with scalars, such as x. We write
the group operation in additive notation: x · g is simply x · g = g + . . . + g, where gis repeated x times. Examples of cryptographic interest are the subgroup of order qp−1
of (Z?p , ×) consisting of elements x in Z?p such that x q = 1 mod p, where q is a large
prime factor of p − 1, and subgroups of prime order of an elliptic curve.
ECDSA is based on the hardness of the discrete logarithm problem over an elliptic
curve. The signature scheme uses elliptic curves E over some prime field Fp , |p| = m
or elliptic curves over F2m . In the first case, possible values for m are{112, 128, 160, 192, 224, 256, 384, 521}
and, in the second case:{113, 131, 163, 193, 233, 283, 409, 571}
Once the curve E has been chosen, a base point G is chosen on E, which generates a
subgroup of order q, such that, denoting by #(E) the number of points in the curveand defining the cofactor h by h = #(E)/q, inequality h ≤ 4 holds. Examples are
given in [11].
A detailed description of ECDSA will be provided later, as well as a security argument that relates the scheme to the ECDL. Therefore, in order to estimate whether
the specific restrictions on the curve and the suggested parameters offer a wide security margin, it is useful to review the performances of the various algorithms known
for the ECDLP. We will distinguish between exponential algorithms, whose running
time depends on the size of the group and subexponential algorithms, which apply to
specific classes of weak curves.

2.2

Exponential algorithms for the ECDL

2.2.1

Pollard’s ρ-method

The best algorithm known to date for solving the DLP in any given group Gpis the
Pollard ρ-method from [36] which takes computing time equivalent to about πn/22group operations. In 1993, van Oorschot and Wiener in [49], showed how the Pollard
ρ-method can be parallelized so that, if t processors are used, then the expected
number√πn/2

of steps by each processor before a discrete logarithm is obtained is ' t . In order
to compute the discrete logarithm of Y in base G, each processor computes a kind of
random walk within elements of the form a · G + b · Y , selecting Xi+1 through one of
the three following rules
1. set Xi+1 = G + Xi
2. set Xi+1 = 2 · Xi
3. set Xi=1 = Y + Xi
Decisions on which rule to apply are made through a random-looking but deterministic
computation, using e.g. hash values. So-called distinguished points Xi are stored
together with their representation Xi = ai · G + bi · Y in a list that is common to
all processors. When a collision occurs in the list, the requested discrete logarithm
becomes known.
The progress of such algorithms is well documented. In April 2000, the solution
to the ECC2K-108 challenge from Certicom [9] led to the computation of a discrete
logarithm in a group with 2109 elements (see [21]). This is one of the largest effort everdevoted to a public-key cryptography challenge. The amount of work required to solve
the ECC2K-108 challenge was about 50 times that required to solve the 512-bit RSA
cryptosystem (see [8]) and was close to 400000 mips-years.
It is expected that such figures will grow slowly, unless unexpected discoveries
appear in the area. From the predictions in [25], one can infer that the proposed
range of parameters will presumably allow for a choice that guarantees security forthe foreseeable future, at least for the next 50 years, provided the lowest values of theparameters are gradually discarded.
2.2.2

Koblitz curves

Anomalous curves are those which contain a p-torsion point other than the infinity point
O, or, equivalently, those whose Frobenius map has trace congruent to one modulo p.
An anomalous elliptic curve over GF (2m ) is actually defined by
y 2 + xy = x3 + x2 + 1
or elsey 2 + xy = x3 + 1
The use of these curves has been
√ suggested by Koblitz in [24]. They have complex multiplication by K = Q( −7). Their Frobenius automorphism τ , defined by3τ (x, y) = (x2 , y 2 ), can be used to provide an efficient computation of pairs (k, k.G), as
shown by work of Solinas ([48]).
In recent work (see√ [17, 51]), it was shown how to improve the ρ-method by amultiplicative factor 2. This takes advantage of the fact that one can simultaneously
handle a point X and its opposite −X. Slightly better improvements can be obtained
for specific curves with automorphisms, such as anomalous curves. Instead of trying
to obtain collisions in the set of elliptic curve points, one can try to obtain collisions
in the set of equivalence classes modulo the action of the Frobenius map.√If we canachieve this, the computing time needed will be divided by something like m, which
may be significant. The technical twist that allows not to miss any collision within
an equivalence class is the ability to define a canonical element in the equivalenceclass of a point X consisting of all τ i (X), i = 0, · · · , m − 1. To define this canonicalelement, one can use a normal basis representation: each point of the curve is given
by a sequence of 2m zero-one coordinates and the action of the Frobenius map is a
shift of both coordinates. The canonical element corresponds to the binary sequence
representing the largest integer. It is essentially unique and, in all formulas above, Xi+1
should be replaced by the canonical element of its equivalence class and the discrete
logarithm should be updated using complex multiplication as appropriate. A furtheri
improvement may use a canonical element√ in the set of all points of the form ±τ (X).
This gains√ another multiplicative factor 2 in terms of computing time. The resulting
factor 2m should not be overemphasized. However, the improvement definitely showsthat unexpected weaknesses can follow from the use of very specific curves.

2.3

Subexponential attacks

As is well known, there are three classes of elliptic curves for which non trivial attacks
have been found. They are
1. the supersingular curves
2. the anomalous curves
Supersingular curves over a field Fr , with r a power of p, are defined by the condition that the trace of the Frobenius map is zero modulo p. For such curves, Menezes,
Okamoto and Vanstone (MOV) have shown how to reduce the discrete logarithm problem to the DLP in an extension field Frk of Fr , with small k. Note that, for elliptic
curves over a prime field Zp , those curves have exactly p + 1 elements and are specifically excluded by the key generation algorithm of [10], which performs the following
checkpB 6= 1 mod q
for any 1 ≤ B ≤ 20
As already stated, anomalous curves are those which contain a p-torsion point otherthan O, or, equivalently, those whose Frobenius map has trace congruent to one modulo
4p. For such curves, work of Semaev [43], Rück [38], Smart [47] and Satoh-Araki [39]has shown how to solve the p-part of the DLP in polynomial time. Note that, for elliptic
curves over a prime field Zp , those curves have exactly p elements and are specifically
excluded by the key generation algorithm of [10]. Also, note that the algorithms found
do not produce anything when p = 2. Hence, the question of the strength of the DLP
in anomalous elliptic curves over fields of characteristic 2, also called Koblitz curves
in section 2.2.2, remains wide open. Although, working with such curves essentiallymeans having a single curve available for a fixed field, which may be considered highly
undesirable, no subexponential algorithm is known for attacking the ECDLP.
The MOV reduction constructs an embedding from the curve into the multiplicative
group of a suitable extension field of Fr , and can be applied in a more general setting
than originally envisioned by the authors. However, if the basepoint is an element oforder q, q is necessarily a divisor of rk − 1. Recently, Balasubramanian and Koblitz
have shown in [2] that this condition was sufficient to carry the MOV reduction. The
key generation algorithm specifically addresses this question. In the case of curves overFp , one gets that pk = 1 mod q. From this, it follows that k is > 20, which is large
enough to turn down subexponential algorithms in the extension field. In the case of
curves over F2m , there is an analogous test
2mB 6= 1 mod q

for any 1 ≤ B ≤ 20with the same consequences.
Another reduction similar to the MOV reduction has appeared in the literature.
It is due to Frey and Rück [16] (see also [15]) and can be stated in the more generalcontext of jacobians on which the Tate pairing exists. Let m be an integer relatively
prime to r, and let µm (Fq ) be the group of roots of unity in Fr whose order divides m.
Assume that the Jacobian J(Fr ) contains a point of order m. Then there is a surjective
pairingϕm : Jm (Fr ) × J(Fr )/mJ(Fr ) → µm (Fr )which is computable in O(log r), where Jm (Fr ) is the group of m-torsion points. Thispairing, the so-called Tate pairing, can be used to relate the discrete logarithm in thegroup Jm (Fr ) to the discrete logarithm in some extension F?rk . In the case of elliptic
curves considered in the current context, the above is applicable only if the order q ofthe base point is a divisor of rk − 1. As a consequence, the curves produced by the
key generation algorithm of [10] are protected against the FR reduction, exactly due
to the same argument used for the MOV reduction.

5

3

The security of digital signature schemes

3.1

Formal framework

In modern terms (see [20]), a digital signature scheme consists of three algorithms(K, Σ, V ):• A key generation algorithm K, which, on input 1k , where k is the security parameter, outputs a pair (pk, sk) of matching public and private keys. Algorithm K is
probabilistic.
• A signing algorithm Σ, which receives a message m and the private key sk, andoutputs a signature σ = Σsk (m). The signing algorithm might be probabilistic.
• A verification algorithm V , which receives a candidate signature σ, a message mand a public key pk, and returns an answer Vpk (m, σ) testing whether σ is a valid
signature of m with respect to pk. In general, the verification algorithm need not
be probabilistic.
Attacks against signature schemes can be classified according to the goals of theadversary and to the resources that it can use. The goals are diverse:• Disclosing the private key of the signer. It is the most drastic attack. It is termed
total break.
• Constructing an efficient algorithm which is able to sign any message with significant probability of success. This is called universal forgery.
• Providing a single message/signature pair. This is called existential forgery.
In many cases the latter does not appear dangerous because the output message islikely to be meaningless. Nevertheless, a signature scheme, which is not existentiallyunforgeable, does not guarantee by itself the identity of the signer. For example, itcannot be used to certify randomly looking elements, such as keys or compressed data.
Furthermore, it cannot formally guarantee the so-called non-repudiation property, since
anyone may be able to produce a message with a valid signature.
In terms of resources, the setting can also vary. We focus on two specific attacks
against signature schemes: the no-message attacks and the known-message attacks. In
the first scenario, the attacker only knows the public key of the signer. In the second,
the attacker has access to a list of valid message/signature pairs. Again, many subcases appear, depending on how the adversary gains knowledge. The strongest is theadaptive chosen-message attack (CMA), where the attacker can require the signer tosign any message of its choice, where the queries are based upon previously obtained
answers. In this setting, one should point out that existential forgery becomes the6ability to forge a fresh message/signature pair that has not been obtained from queries
asked during the attack. There is a subtle point here: one might have the stronger
rule that the attacker can only forge the signature of message, whose signature was
not queried from the signing oracle. This is different only in a context where several
signatures may correspond to a given message. However, the resulting security levelmay be strictly weaker in this case.
When designing a signature scheme, one wishes to rule out existential forgeries, evenunder adaptive chosen-message attacks. More formally, one requires that the successprobability of any adversary A, whose running time remains below some security boundt, is negligible, where the success probability is defined by:
Succcma (A) = Pr (pk, sk) ← K(1k ), (m, σ) ← AΣsk (pk) : Vpk (m, σ) = 1 .
Probabilities are taken not only over the random coins of A but also over the random
coins that K uses. In the above, note the superscript Σsk , indicating adaptive calls tothe signing algorithm: this is consistent with the framework of relativized complexity
theory, where oracle calls are allowed and, accordingly, we will use the wording signingoracle in this setting.
To allow for concrete estimates, we denote by Succcma (t, qs ) the maximum successprobability of an adversary whose running time is bounded by t, and who is allowed
to ask at most qs queries from the signing oracle. When qs = 0, the adversary runs a
no-message attack and is also called a passive adversary. We then denote its success
def
probability by Succnma (A). In other words, Succnma (t) = Succcma (t, 0).

3.2

A short history of DL-based signature schemes

3.2.1

The El Gamal scheme

The El Gamal signature scheme [13] appeared in 1985 as the first DL-based signaturescheme. Rather than providing a full description of the scheme, we have depicted its
components on figure 1. Note that the figure splits key generation in two steps. This
stems from the fact that DL-based schemes usually set up a group G and a generator
g, that may be common to several users.
3.2.2

The Schnorr scheme

In 1986, Fiat and Shamir [14] introduced a new paradigm for deriving signatureschemes from fair zero-knowledge identification protocols [18]. This paradigm uses
hash functions to replace random queries from the verifier. In 1989, Schnorr provided
a zero-knowledge identification scheme [40], together with the corresponding signaturescheme [41]. Although this scheme is reminiscent of the El Gamal scheme, it uses a
subgroup of order q of Z?p , where p and q are two large primes such that q | p − 1. The
Schnorr scheme appears on figure 2.
7

Initialization
p a large primeg a generator of Z?p
K: Key Generation
private key
x ∈ Zp−1
public key
y = g x mod p→ (y, x)Σ: Signature of mk randomly chosen in Z?p−1
r = g k mod ps = (m − xr)/k mod p − 1→ (r, s) a signature of m
V : Verification of (m, r, s)?

check whether g m = y r rs mod p→ valid or invalid
Figure 1: The El Gamal Signature Scheme.

Initializationp, q large primes, q | p − 1
g an element of order q of Z?p
K: Key Generation
private key
0<x<q−1
public key
y = g −x mod p→ (y, x)Σ: Signature of mk randomly chosen 0 < k < qr = g k mod pe = H(m, r)
s = k + ex mod q→ (e, s) a signature of m
V : Verification of (m, r, s)?

check whether
H(m, (g s y e mod p)) = e→ valid or invalid
Figure 2: The Schnorr Signature Scheme.

8Initialization
G a cyclic group of prime order q
g a generator of G
H : {0, 1}? → {0, 1}h a hash function
f : G → Zq a reduction function
K: Key Generation
private key
0<x<qpublic key
y =x·g→ (y, x)Σ: Signature of mk randomly chosen 0 < k < qr=k·g
r = f (r)if r = 0 abort and start again
e = H(m)s = k −1 (e + xr) mod q
if s = 0 abort and start again→ (r, s) a signature of m
V : Verification of (m, r, s)
check whether 0 < r, s < q and r = f (r0 )where e = H(m) and r0 = es−1 · g + rs−1 · y→ valid or invalid
Figure 3: The Generic DSA

3.2.3

DSA, ECDSA and their variants

In 1994, a digital signature standard DSA was proposed, whose flavour was a mixture of
El Gamal and Schnorr. Rather than describing the original DSA [30, 32], we follow [5],and propose the description of a generic DSA (see Figure 3), which operates in any
cyclic group G of prime order q.
In the DSA, the reduction function f takes as input an integer modulo p and outputs
f (r) = r mod q. In the elliptic curve version [1, 32, 10, 11], the function is defined ina more intricate manner, which we now describe. An elliptic curve point r is given
by two coordinates (x, y), which take values in the base field. For elliptic curves overprime fields, one simply sets f (r) = x mod q. For curves over F2m , x is a sequenceof m bits and f (r) is obtained by first turning x into an integer < 2m , by a standard
conversion routine.

9

3.3

The random oracle model

Ideally, one would like to design a signature scheme which has provable security, basedon the sole assumption that the discrete logarithm or its elliptic curve variant ECDL
is hard. Unfortunately, no such scheme is currently known that allows such a proof.
The next step is to hope for a proof carried in a non-standard computational model,
as proposed by Bellare and Rogaway [3], following an earlier suggestion by Fiat andShamir [14]. In this model, called the random oracle model, concrete objects such thathash functions are treated as random objects. This allows to carry through the usual
reduction arguments to the context of relativized computations, where the hash function is treated as an oracle returning a random answer for each new query. A reduction
still uses an adversary as a subroutine of a program that contradicts a mathematicalassumption, such as the assumption that ECDL is hard However, probabilities aretaken not only over coin tosses but also over the random oracle.
Of course, the significance of proofs carried in the random oracle is debatable.
Firstly, hash functions are deterministic and therefore do not return random answers.
Along those lines, Canetti et al. [7] gave an example of a signature scheme which issecure in the random oracle model, but insecure under any instantiation of the random
oracle. Secondly, proofs in the random oracle model cannot easily receive a quantitativeinterpretation. One would like to derive concrete estimates - in terms of key sizes from the proof: if a reduction is efficient, the security “loss” is small and the existenceof an efficient adversary leads to an algorithm for solving the underlying mathematicalproblem, which is almost as efficient. Thus, key sizes that outreach the performancesof the known algorithms to break the underlying problem, can be used for the scheme
as well.
Despite these restrictions, the random oracle model has proved extremely usefulto analyze many encryption and signature schemes. It clearly provides an overall
guarantee that a scheme is not flawed, based on the intuition that an attacker would
be forced to use the hash function in a non generic way. In the area of signature schemes
based on the discrete logarithm problem, the security of the Schnorr signature scheme,
based on the assumption that the hash function H behaves like a random oracle, waslong considered a folklore result. A formal treatment along with concrete estimatesappeared in [33, 34]. The same authors also proved the security against existential
forgeries of a slight variant of the El Gamal scheme, under adaptive chosen-message
attacks. The variant simply replaces the message m by H(m, r), where r = g k mod p,
is computed as shown on figure 1. The proof was using the random oracle model, andwas carried in the probabilistic framework developped in section 3.1. It turned out that
this was an essential ingredient of the proof. Indeed, Bleichenbacher [4] showed thatspecific weak choices of g allowed universal forgery, both for the El Gamal scheme andfor the variant. As a practical consequence, it is extremely important that users receive
the guarantee that g has been chosen randomly. To offer such guarantee, standards
10such as [32] have developped a methodology, allowing to produce this parameter in arandom and verifiable manner, again by means of hash functions.
Turning to DSA-like schemes, we mention that the generic DSA has been provensecure by techniques similar to [33, 34], under the assumption that both f and H
behave like random oracles [35]. The assumptions were slightly relaxed in [5], wheresecurity was obtained, taking f as a random oracle, while only requiring that H iscollision-resistant. On the other hand, no formal security proof, carried in the random
oracle model, has ever been provided for either DSA or ECDSA. This is in contrast
with the Korean variant of DSA, KCDSA [23], whose security has been establishedusing random oracle techniques [5].

3.4

Generic Algorithms

Recently, several authors have proposed to use yet another model to argue in favourof the security of cryptographic schemes, that could not be tackled by the random
oracle model. This is the so-called black-box group model, or generic model [42, 6, 27].
In particular, paper [6] considered the security of ECDSA in this model. Genericalgorithms had been earlier introduced by Nechaev and Shoup [29, 45], to encompass
group algorithms that do not exploit any special property of the encodings of groupelements other than the property that each group element is encoded by a uniquestring. Typically, algorithms like Pollard’s ρ algorithm [36] fall under the scope of thisformalism while index-calculus methods do not.
Recall that any Abelian finite group Γ is isomorphic to a product of cyclic groups ofthe form (Zpk , +), where p is a prime. Such groups will be called standard groups. An
encoding of a standard group Γ is an injective map from Γ into a set of bit-strings S. We
give some examples: consider the multiplicative group of invertible elements modulo
some prime p. This group is cyclic and isomorphic to the standard additive group
Γ = Zp−1 . Given a generator g, an encoding σ is obtained by computing the binary
representation σ(x) of g x mod p. The same construction applies when one considersa multiplicative subgroup of prime order q. Similarly, let E be the group of points
of some non-singular elliptic curve over a finite field F, then E is either isomorphic
to a (standard) cyclic group Γ or else is isomorphic to a product of two cyclic groups
Zd1 × Zd2 . In the first case, given a generator g of E, an encoding is obtained bycomputing σ(x) = x · g, where x · g denotes the scalar multiplication of g by the
integer x and providing coordinates for σ(x). The same construction applies when E isreplaced by one of its subgroups of prime order q. Note that the encoding set appears
much larger than the group size, but compact encodings using only one coordinate
and a sign bit ±1 exist and for such encodings, the image of σ is included in thebinary expansions of integers < tq for some small integer t, provided that q is closeenough to the size of the underlying field F. This is exactly what is recommended for
cryptographic applications [22, 10].
11

A generic algorithm A over a standard Abelian group Γ is a probabilistic algorithm
that takes as input an encoding list L = {σ(x1 ), · · · , σ(xk )}, where each xi is in Γ.
While it executes, the algorithm may consult an oracle for further encodings. Oracle
calls consist of triples {i, j, }, where i and j are indices of the encoding list L and  is±. The oracle returns the string σ(xi ± xj ), according to the value of  and this bitstring is appended to the list L, unless it was already present. In other words, A cannot
access an element of Γ directly but only through its name σ(x) and the oracle provides
names for the sum or difference of two elements addressed by their respective names.
Note however that A may access the list L at any time. In many cases, A takes as
input a pair {σ(1), σ(x)}. Probabilities related to such algorithms are computed withrespect to the internal coin tosses of A as well as the random choices of σ and x.
In [6], the adversary is furthermore allowed to include additional elements zi0 in theencoding list L, without calling the oracle. This is consistent with the fact that compact
encodings for elliptic curves, as described above, are such that almost all bit-strings
encode elliptic curve elements. However, this definitely enlarges the class of genericalgorithm, compared to [29, 45]. One can keep the number of additional elements
smaller than twice the number of queries, since additional elements not appearing ina further query can be deleted and since each query involves at most two additional
elements.
Generic algorithms have been introduced in [29, 45], to provide lower bounds for aclass of algorithms that attempt to solve the discrete logarithm problem in a genericway. The following theorem adapts the result from [45] to the extended model considered in [6].
Theorem 1 Let Γ be a standard cyclic group of prime order q. Let A be a genericalgorithm over Γ that makes at most n queries to the oracle. The probability that A
returns x on input {σ(1), σ(x)} is less than 1/q + 5 × (n + 1)2 /q.
Before proving the theorem, we state the following lemma, where q is still a prime
number,Pi=jand where an affine polynomial is an element P of Zq [X1 , . . . , Xj ] of the form
a0 + i=1 ai Xi , with all its coefficients random variables.
Lemma 1 Let P be a non-zero affine polynomial in Zq [X1 , . . . , Xj ], then1
[P (x1 , . . . , xj ) = 0] ≤ .
x1 ,...,xj ∈ZqqP
Proof. We write P = a0 + i=j
i=1 ai Xi , and condition on each fixed sequence ai . For suchsequence, we let k be the largest index such that ak 6= 0. The existence of k follows
from the hypothesis that P is non-zero. Clearly,
Pr

pk =

Pr [Pk (x1 , . . . , xk ) = 0]

x1 ,...,xk12

= Pr[xk = −Pk−1 (x1 , . . . , xk−1 )/ak ]
1
≤
.
q
t
u
Proof.(of theorem 1). Basically, we would like to identify the probabilistic space consisting of σ and x with the space S n+2 × Γ × Γ2n , where S is the set of bit-string
encodings. Given a tuple {z1 , · · · , zn+2 , x, x1 , . . . , x2n } in this space, z1 and z2 are usedas σ(1) and σ(x), the successive zi are used in sequence to answer the oracle queries andthe xi ∈ Γ serve as pre-images of the additional elements zi0 included by the adversary
into the encoding list L. However, this interpretation may yield inconsistencies as it
does not take care of possible collisions.
We give another interpretation of the encoding σ. This interpretation is based on
defining from the tuple {z1 , · · · , zn+2 }, a sequence of affine polynomials Fi (X, X1 , . . . , X2n ),with coefficients modulo q, depending on the execution of A:• Polynomials F1 and F2 are set to F1 = 1 and F2 = X, respectively. Thus
L = {F1 , F2 }.
• When the adversary puts an additional k-th element zk0 in the encoding list,
polynomial Fn+k+2 is defined as Xk , and added to L.
• At the `-th query {i, j, }, polynomial F` is defined as Fi ± Fj , where the sign ±is chosen according to . If F` is already listed as a previous polynomial Fh ∈ L,then F` is marked and A is fed with the answer corresponding to h. Otherwise,z` is returned by the oracle and F` is added to L.
Once A has come to a stop, variable X is set to x, and the Xk s are set to xk . In otherwords, σ is set at random, subject to the conditions z` = σ(F` (x, x1 , . . . , x2n )), ` =1, · · · , n + 2 and zk0 = σ(xk ), k = 1, · · · , 2n. It is easy to check that the behavior of thealgorithm that is driven by the polynomials Fi is exactly similar to the behavior of theregular algorithm, granted that elements in the sequence (z1 , · · · , zn+2 ) are all distinct,
and that no polynomial Fi − Fj vanishes at (x, x1 , . . . , x2n ), where i, j range over the
3n + 2 indices of polynomials in L. We call a sequence {z1 , · · · , zn+2 , x, x1 , . . . , x2n }which satisfies both requirements a safe sequence. We bound the probability of unsafe
sequences as follows, assuming n small enough, n2 < q:
• Bad sequences of random elements {z1 , z2 , . . . , zn+2 }, which are not all distinct
appear with probability
!

k=n+1
k=n+1
Y 
X k
k
≤1− 1−
p = 1−
1−
q
q
k=1
k=1
≤

(n + 1)(n + 2).
2q13

• From lemma 1, we can bound the probability that Fi −Fj vanishes at (x, x1 , . . . , x2n )by 1/q. Since there are at most 3n+2
such polynomials, we infer that, once2
{z1 , · · · , zn+2 } have been set and are distinct, the set of (x, x1 , . . . , x2n ) such that3n+2{z1 , · · · , zn+2 , x, x1 , . . . , x2n } is not safe has probability bounded by/q =2(3n + 2)(3n + 1)/2q.
Finally, the probability of unsafe sequences is at most(n + 1)(n + 2) (3n + 2)(3n + 1)
5(n + 1)2
+
≤
.
2q
2q
q
As explained, an encoding σ can be defined from a safe sequence, such that:
σ(Fi (x, x1 , . . . , x2n )) = zi , for all unmarked Fi , and 1 ≤ i ≤ n + 2,
σ(xk ) = zk0 , for k = 1, . . . , 2n.
This correspondence preserves probabilities. However, it does not completely cover the
sample space {σ, x} since executions such that Fi (x, x1 , . . . , x2n ) = Fj (x, x1 , . . . , x2n ),for some indices i, j, such that Fi and Fj are not identical are omitted. From the above,2
we see that we have actually discarded at set of probability ≤ 5(n+1). To concludeq
the proof, we simply note that the output of a computation corresponding to a safesequence {z1 , · · · , zn+2 , x, x1 , . . . , x2n } does not depend on x. Hence it is equal to x
with probability 1/q.
tu

4

The security of the generic DSA

In this section, we prove, in the generic model, the security of the generic DSA signaturescheme proposed in section 3.2.3. We follow [6], but we adopt a different style of proof,
inspired by Shoup [46]. Referring to figure 3, we clarify our use of encodings. The basepoint g of the group G is identified with the canonical generator 1 of Zq and therefore
labelled by σ(1). Similarly, the public key y is labelled by σ(x), where x is the private
key. When an element r is requested, at signature generation, it is obtained as σ(k),where k is randomly chosen. Finally, the reduction function f directly operates on theset of encodings S.
Contrary to the earlier approach of [42], we do not model the hash function as arandom oracle. Rather, along the lines first investigated in [5], we use specific propertiesof the hash function, such as collision-freeness or uniformity. Similarly, we need specificproperties of the reduction function. Before providing the proof, we briefly set up
notations that allow to handle such properties in a quantitative manner.

14

4.1

A framework for the hash function and reduction function

4.1.1

One-Wayness

Let H be a hash function H : {0, 1}∗ → {0, 1}h . An (ε, t)-inverter for H is an algorithm
able to invert H with probability greater than ε, and with running time bounded byt. Probabilities are taken over a random element b ∈R {0, 1}h :Succow (A) = Pr[b ∈R {0, 1}h , a ← A(b) : H(a) = b] ≥ ε.
Denote by Succow (H, t) the maximal success probability for inverting H over all adversaries whose running time is bounded by t. Hash function H is (ε, t)-one-way if
Succow (H, t) is upper-bounded by ε.
Let q be a prime number. Identifying elements of {0, 1}h with integers < 2h , onedef
can define H 0 : {0, 1}∗ → {0, . . . q − 1} by H 0 (m) = H(m) mod q. The definition holds
whether q is < 2h or ≥ 2h .
When q is << 2h , then inverting H 0 is easier than inverting H. Assume now that qhis such that 2θ < q ≤ 2h , for some small constant θ > 1. Using modular reduction, an
inverter for H 0 , with success probability ε0 easily translates into an inverter for H, with0
success probability ε ≥ εθ . A similar argument holds if 2h < q < θ2h . Thus, provided
2h and q are of the same order of magnitude, inverting H and H 0 is equally difficult.
On the other hand, when 2h << q, then any inverter for H 0 , has success probabilityh≤ 2q .
4.1.2

Uniformity

Let H be as above and M be a distribution on a set of messages. Hash function
H is (δ, t)-uniform on M, if the distribution {H(M)} is δ-indistinguishable from theuniform distribution. More precisely, no distinguisher D, with running time bounded
by t, can get an advantage greater than δ, where the advantage of D is the difference
between the probabilities that D outputs one, with inputs taken from each distribution.
4.1.3

Collision-ResistanceLet H be as above. A (γ, t)-collision-finder for H is an algorithm A, running in timebounded by t, and able to find a collision with probability greater than γ:
Succcol (A) = Pr[(a0 , a1 ) ← A : H(a0 ) = H(a1 )] ≥ γ.
Denote by Succcol (H, t) the maximal success probability for finding a collision, takenover all adversaries whose running time is bounded by t. Hash function H is (γ, t)collision-resistant if Succcol (H, t) is upper-bounded by γ.

15

4.1.4

Almost-Invertibility

Let f be a reduction function f : S → Zq . An almost-inverse g of f is a probabilistic
algorithm g, possibly outputting Fail, such that(i)Pr [g(b) ∈ S ∧ f (g(b)) = b] ≥ 1/3b∈R Zq

Function f is (δ, t)-almost-invertible, with almost-inverse g, if furthermore:Dg = {g(b) | b ∈R Zq ∧ g(b) ∈ S}(ii) Dg ≈δ U, whereU = {a | a ∈R S}.
In the second item, notation Dg ≈δ U means that no distinguisher with running timebounded by t can get an advantage greater than δ.

4.2

Security against passive adversaries

In this section we prove the security of the generic DSA against passive adversaries, i.e.
adversaries which try to forge a message/signature pair without querying the signingoracle.
Theorem 2 Let Γ be a standard cyclic group of prime order q. Let S be a set ofbit-string encodings. Let H : {0, 1}∗ → {0, 1}h be a hash function and f : S → Zq bea reduction function with almost-inverse g. Let A be a generic algorithm over Γ, thatmakes at most n queries to the group-oracle. Assume that A, on input {σ(1), σ(x)},returns a message m and a valid generic DSA signature of m, with probability ε =Succnma (A), within running time t. Then there exist adversaries BH , Bg , operating
within time bound t0 , and such that BH is attempting to invert H 0 = H mod q withsuccess probability εH , and Bg is playing a distinguishing game for g, with advantage
εg , whereε ≤ 3nεH + 3nεg +5(n + 1)2,q

t0 ≤ t + τ.
with τ the running time of g.
In order to prove this result, we define a sequence Game1 , Game2 , etc of modified
attack games starting from the actual game Game0 . Each of the games operates on
the same underlying probability space: the public and private key of the scheme, thecoin tosses of the adversary A, the random encoding σ. Only the rules defining how
the view is computed differ from game to game. To go from one game to another, we
repeatedly use the following lemma from [46]:16Lemma 2 Let E1 , E2 and F be events defined on a probabilistic spacePr[E1 ∧ ¬F] = Pr[E2 ∧ ¬F] =⇒ |Pr[E1 ] − Pr[E2 ]| ≤ Pr[F].
Proof. The proof follows from easy computations:|Pr[E1 ] − Pr[E2 ]| = |Pr[E1 ∧ ¬F] + Pr[E1 ∧ F] − Pr[E2 ∧ ¬F] − Pr[E2 ∧ F]|= |Pr[E1 ∧ F] − Pr[E2 ∧ F]| = |Pr[E1 | F] · Pr[F] − Pr[E2 | F] · Pr[F]|≤ |Pr[E1 | F] − Pr[E2 | F]| · Pr[F] ≤ Pr[F]ut
Proof.(of theorem 2). We use the probabilistic model developed in section 3.4. Let A bea generic attacker able to forge a pair consisting of a message m and a valid signature(r, s). We assume that, once these outputs have been issued, A goes on checking
the signature: this means requesting the encoding of es−1 + xrs−1 mod q, where e =H(m), and checking that its image under f is r. The request can be performed by
mimicking the usual double-and-add algorithm, calling the generic encoding at eachgroup operation. However, to keep things simple, we ignore the number of additionalrequests to the group-oracle. The extra check allows to estimate the probability thatthe output signature is valid. As explained, we start with the game coming from theactual attack, and modify it step by step until we reach a final game, whose successprobability has an upper-bound obviously related to inverting the hash function.
Game0 : An encoding σ is chosen and a key pair (pk, sk) is generated using K(1k ).
Adversary A is fed with pk and, querying the generic encoding, outputs a message
m and a signature (r, s). We denote by S0 the event Vpk (M, (r, s)) = 1 and use asimilar notation Si in any Gamei below. By definition, we have Pr[S0 ] = ε.
Game1 : We slightly modify this game, by using the interpretation of the encoding proposed in section 3.4: this uses a random sequence {z1 , · · · , zn+2 , x, x1 , . . . , x2n }.
As shown in section 3.4, the new game only differs from the old on unsafe sequences:5(n + 1)2.
| Pr[S1 ] − Pr[S0 ] | ≤q
Game2 : In this game, we choose at random an index κ between 1 and n + 2. We knowthat Fn+2 is es−1 + rs−1 X, since it appears as the final step of the verifying algorithm. We then discard executions where Fκ is not the first occurrence of Fn+2 .
Since the additional random value κ is chosen independently of the execution of
Game1 , and since it hits an occurrence of Fn+2 with probability ≥ 1/n, we get
Pr[S2 ] ≥ P r[S1 ] ×
17

1
.
n

Game3 : In this game, we make an additional test on κ. Let Fκ = bκ X + aκ . We pick at
random ẽ ∈R Zq , and compute cκ ← g(bκ a−1
κ ẽ mod q), where g is the probabilistic
inverse of f . If the computation of g returns Fail, we abort the game. We let GBadthe probability that this happens. From the randomness of ẽ and the fact that g
is an almost-inverse of f , we get Pr[¬GBad] ≥ 1/3. Now, the new experiment is
independent from the execution of Game2 . Thus:
Pr[S3 ] = Pr[S2 ] × Pr[¬GBad]1≥ Pr[S2 ] × .
3
Game4 : Here, we further modify the previous game by letting cκ replace zκ . Since ẽ isuniformly distributed, the input to g is uniformly distributed as well. Using thealmost-invertibility of f , we bound the difference between the success probabilitiesof the two games by δg : | Pr[S4 ] − Pr[S3 ] | ≤ δg .
We finally upper-bound Pr[S4 ]. We observe that that, while checking the signature,
the final request of the adversary is the encoding of es−1 + xrs−1 mod q. The answer in0−1
Game4 is cκ = g(bκ a−1
κ ẽ mod q), and the image r under f of this answer is bκ aκ ẽ mod q.
Since aκ is es−1 mod q, and bκ is rs−1 mod q, we get that r0 = r if and only if ẽ =e mod q, which means that a pre-image of ẽ has been obtained. Therefore, Pr[S4 ] ≤def
εH = Succow (H 0 , t0 ), where H 0 (m) = H(m) mod q. Summing up inequalities, we get:
Pr[S0 ] ≤≤≤≤Pr[S1 ] + 5 × (n + 1)2 /q ≤ n Pr[S2 ] + 5 × (n + 1)2 /q
3n × Pr[S3 ] + 5 × (n + 1)2 /q
3n × (Pr[S4 ] + δg ) + 5 × (n + 1)2 /q
3nεH + 3nδg + 5 × (n + 1)2 /q.
t
u

4.3

Active Adversaries

In this section we extend the previous result to active adversaries, which have accessto the signing oracle. First of all, we clarify our notion of existential forgery: a forgery,that provides a second signature of a message for which the adversary has alreadyobtained one from the signing oracle, is duly accepted. This means that we cover thestronger security notion, based on a relaxed definition of existential forgery.
A couple of lemmas will be needed. We first show how one can perfectly simulate
the distribution of valid signatures. We define a simulator S. The simulator, picks
elements u ∈R S, and s ∈R Zq , and outputs the pair (r, s), with r = f (u).

18Lemma 3 For any message m, the output distribution of S is perfectly indistinguishable from the output distribution of Σsk (m).
Proof. We have to compare two distributions: the original distribution D0 generatedby Σ on a fixed message m, and the distribution D1 produced by S.
D0 = {(r, s) | x ∈R Zq ; k ∈R Z?q ; σ ∈R ZSq ; r = f (σ(k)); s = k −1 (H(m) + xr) mod q}
D1 = {(r, s) | u ∈R S; s ∈R Zq ; r = f (u)}That they coincide is shown by the following equalities:
D0 = {(r, s) | x ∈R Zq ; k ∈R Z?q ; σ ∈R ZSq ; r = f (σ(k)); s = k −1 (H(m) + xr) mod q}= {(r, s) | x ∈R Zq ; k ∈R Z?q ; u ∈R Zq ; r = f (u); s = k −1 (H(m) + xr) mod q}= {(r, s) | s ∈R Zq ; u ∈R Zq ; r = f (u)} = D1 .
tu
We now state an easy lemma from elementary probability theory.
Lemma 4 Let S be a binomial distribution, which is the sum of k = 5 ln n Bernoulli
trials with probability for success ≥ 1/3. Then, the probability that S = 0 is at most1.
n2
Proof. The probability that S = 0 is upper-bounded by 5 ln n
2
1= exp (−5 ln n ln(3/2)) < exp (−2 ln n) = 2 .
3ntuTheorem 3 Let Γ be a standard cyclic group of prime order q. Let S be a set ofbit-string encodings. Let H : {0, 1}∗ → {0, 1}h be a hash function and f : S → Zq
be a reduction function with almost-inverse g. Let A be a generic algorithm over Γ,that makes at most qs queries to the signing oracle and n queries to the group-oracle,
respectively. Assume that A, on input {σ(1), σ(x)}, returns a message m and a valid
generic DSA signature (r, s) of m, with probability ε = Succcma (A), within running
time t. Then there exist adversaries BH , CH , Dg , operating within time bound t0 , andsuch that BH is attempting to invert H 0 = H mod q with success probability εH , CH is
attempting to find collisions for H 0 = H mod q with success probability γH , and Dg is
playing a distinguishing game for g, with advantage δg , where5(n + 1)(n + qs + 1),
q
≤ t + n × (5τg ln n + τH ),ε ≤ 2γH + 2n(δg + εH ) +t0

with τg the running time of g and τH the running time for H.
19

Proof. Let A be a generic attacker able to forge a pair consisting of a message m anda valid signature (r, s). As for the passive case, we assume that, once these outputs
have been issued, A goes on checking the signature by requesting the encoding of
es−1 + xrs−1 mod q, where e = H(m), and checking that its image under f is r. We
assume furthermore, that, after each query mj to the signing oracle, the adversary
immediately performs a similar request to check the validity of the answer. To keep
things simple, we do not perform any book-keeping of the additional requests and keepn to denote the overall number of queries to the group oracle. We now play games as
before:Game0 : An encoding σ is chosen and a key pair (pk, sk) is generated using K(1k ).
Adversary A is fed with pk and, querying the generic encoding and the signingoracle, outputs a message m and a signature (r, s). We denote by S0 the event
Vpk (M, (r, s)) = 1 and use a similar notation Si in any Gamei below. By definition,
we have Pr[S0 ] = ε.
Game1 : We slightly modify this game, by using the interpretation of the encoding proposed in section 3.4: this uses a random sequence {z1 , · · · , zn+2 , x, x1 , . . . , x2n }.
As shown in section 3.4, the new game only differs from the old on unsafe sequences:5(n + 1)2
| Pr[S1 ] − Pr[S0 ] | ≤.
q
Game2 : In this game, we perform additional random tests, without modifying the simulation of the generic oracle: a test is performed at each index `, such that thecorresponding affine polynomial appears for the first time (or is unmarked following the terminology of section 3.4). Let F` = b` X + a` . We pick at randome˜` ∈R Zq , and compute c` ← g(b` a−1` e˜` mod q) until the computation of g returns an answer different from Fail. However, we stop and abort the game after
5 ln n trials. This game differs from the previous one if c` remains undefined after
5 ln n attempts. Since e˜` is uniformly distributed, and since the successive trials
are mutually independent, we may use lemma 4 and bound the corresponding
probability by n12 . This provides the overall bound 1/n, when ` varies. Taking
into account the fact that the experiments are independent from the executionof Game1 , we get
1
Pr[S2 ] ≥ (1 − ) Pr[S1 ].
n
Game3 : Here, we further modify the previous game by letting c` replace z` , for eachindex ` such that F` is unmarked. Note that we have f (z` ) = b` a−1` e˜` mod q.
Since the e˜` s are uniformly distributed, the inputs to g are uniformly distributed
as well. Applying the so-called hybrid technique, which amounts to using n
20

times the almost-invertibility of g, we bound the difference between the successprobabilities of the two games by nδg : | Pr[S4 ] − Pr[S3 ] | ≤ nδg .
Game4 : In this game, we simulate the signing oracle. For any query mj to the signingoracle, one computes ej = H(mj ), and issues a random signature (rj , sj ), using
the simulation of lemma 3. Recall that the simulation picks sj at random andcomputes rj as f (uj ), where uj is randomly drawn from S. By lemma 3, thissimulation is perfect. Observe that, while checking the signature, the adversary
requests, at some later time, the encoding of ej sj −1 + xrj sj −1 mod q. We let` the first index corresponding to such query, F` = b` X + a` . We modify z` ,replacing its earlier value by uj and define e˜` as ej = H(mj ). Observe that westill have f (z` ) = b` a−1` e˜` mod q. This game only differs from the previous one if−1polynomial ej sj +Xrj sj −1 collides with a previous one. Due to the randomnessof sj , we obtain:nqs| Pr[S4 ] − Pr[S3 ] | ≤.
q
We note that the final simulation runs in time t0 ≤ t + n × (5τg ln n + τH ) and we
finally upper-bound Pr[S4 ]. We observe that, while checking the signature, the final
request of the adversary, with index n + 2, is the encoding of es−1 + xrs−1 mod q,
where e = H(m). We let ` be the first occurrence of Fn+2 . If the signature is valid,
the following equalities hold:
es−1
rs−1
f (z` )
r====a` mod qb` mod qb` a−1` e˜` mod qf (z` )

From these equalities, it easily follows that r = f (z` ) = re−1 e˜` mod q, which in turnimplies e = e˜` mod q. We distinguish two cases:• If z` has been created according to the rule of Game3 , then a pre-image m of somerandomly chosen element e˜` among the n possible ones has been found.
• If z` has been created according to the rule of Game4 , then e˜` is the image under
H of a message mj queried from the signing oracle. Furthermore, we have:
ej s−1= a` mod qjrj s−1= b` mod qjComparing to the above equalities, we get that s = sj mod q and r = rj mod q.
Note that mj cannot be equal to m, since otherwise the output forged signature
would coincide with an earlier signature (rj , sj ) of the same message m. Thus, adefcollision has been found for H 0 , where H 0 (m) = H(m) mod q.
21

The probability that an algorithm running in time t0 finds a preimage under H 0 of anelement among n is at most nεH . From this, we obtain that: Pr[S4 ] ≤ nεH + γH .
Summing up inequalities, we get:(n + 1)2
Pr[S0 ] ≤ Pr[S1 ] + 5 ×q
−1(n + 1)21≤
1−
Pr[S2 ] + 5 ×≤ 2 Pr[S2 ] + 5 × (n + 1)2 /qnq≤ 2 × (Pr[S3 ] + nδg ) + 5 × (n + 1)2 /q
nqs≤ 2 Pr[S4 ] + 2nδg + +2
+ 5 × (n + 1)2 /qq≤ 2γH + 2n(δg + εH ) + 5 × (n + 1 + qs )(n + 1)/q.
tu

5

The practical security of ECDSAIn this section, we analyze the security of the ECDSA signature scheme in view of theprevious proofs. This involves a discussion on the significance of the generic model,
both as a general paradigm, and in connection with its use to argue in favour of the
security of ECDSA.

5.1

The generic model as a security paradigm

As noted in section 3.3, the significance of proofs carried in the random oracle is amatter of controversy, and it is further debatable whether or not security estimatesobtained in the random oracle model can be used to derive key sizes. However, it isgenerally acknowledged that a security proof in the random oracle model provides anoverall guarantee that a scheme is not flawed, based on the intuition that an attacker
would be forced to use the hash function in a non generic way.
The generic model was proposed to provide lower bounds for a class of algorithms
that attempt to solve the discrete logarithm problem in a generic way. This gives
a restricted, albeit meaningful indication of the hardness of the discrete logarithms
in general groups. Of course, the idea of further using the generic model to argue
in favour of the security of specific schemes is appealing. However, we find it rather
unconvincing, at a methodological level, for reasons that we now develop.
Firstly, it departs from the usual approach of provable security, which reduces a
cryptographic scheme to a hard problem. Proofs in the generic model are absolute, as
seen from the statements of theorems 2 and 3. Accordingly, they do not measure theloss that a cryptographic construct might bring per se.
22

Secondly, hash functions are meant to be random. They are crafted so that statistical attacks of the type considered in conventional cryptanalysis cannot be mounted. On
the other hand, groups used in public key cryptography, have an underlying algebraic
structure, where randomness does not play any role.

5.2

The case of ECDSAIn [6], it is argued that theorems 2 and 3 are meaningful in the context of ECDSA,
while they are not in the context of DSA. We claim this is simply wrong. In orderto support our claim, we review the meaning of each of the hypotheses on which thetheorems rely.
5.2.1

The hash function and reduction function

Theorems 2 and 3 require the hash function H 0 to be sufficiently one-way and collisiondef
resistant, where H 0 (m) = H(m) mod q. Currently, the only supported hash funstion
H for ECDSA is SHA-1. This function has been designed to be one-way and collisionresistant. When the size q of the group is much smaller than 2h , where h = 160 is the
bit-size of outputs of SHA-1, then it becomes easier to invert H 0 or create collisions.
When q is of the same order of magnitude as 2h , then inverting H 0 and inverting H
is essentially equivalent and the same is true for collision finding. Finally, when q ismuch larger than 2h , inverting H 0 is hard anyhow, whereas collision finding remains
at the same computational level of hardness. In conclusion, it makes sense to assume
that H 0 is one-way and collision resistant, as soon as q is at least of the order 2h . Wenote that, contrary to [6], we have avoided to use the uniformity of H. We believe thisis a better approach.
The reduction function for ECDSA [1], takes the first coordinate of a curve element
and reduces it modulo q: r, f (r) = xr mod q. In case of binary fields, one first has
to turn xr into an integer < 2m , by a standard conversion routine. Note that, whenx is given in the base field, either it is not the first coordinate of a curve element, orelse two points of the curve have first coordinate x. Those two points r1 and r2 aresymmetric: r1 = −r2 . Furthermore, the second coordinate of each of the two points iseasily computed. This allows to sample the curve by defining a probabilistic inverse gof f at b as follows:
1. pick at random x in the base field such that x = b mod q,
2. output at random one of the two curve elements with first coordinate x or Fail if
there is none.
By Hasse’s Theorem, the number of elements of E is√
#E = p + 1 + t, where | t | ≤ 2 p.
23

√
p+1−2 pTherefore, the probability that g succeeds is lower-bounded by, which is ≥ 1/3.
pThis is in the setting of prime fields, but a similar result holds for binary fields. In
conclusion, the assumption on the reduction function makes sense.

5.3

The encoding function

We claim that the encoding function cannot be viewed as generic. To support theclaim, we observe that ECDSA is not immune to existential forgery in the stronger
security model that we have considered. Indeed, from a signature (r, s) of a messagem, one can derive a second one, namely (r, −s). Referring to figure 3, we see that thevalues of r0 that appear in the verification of both signatures are symmetric, so that
their image by f is the same. If the generic model was an appropriate framework,
then this would contradict theorem 3. Of course, it is presumably possible to define
a notion of symmetric generic encoding, where encodings of ±r are indentical and to
search for a security result of some form, in the symmetric generic model. This looks
quite twisted.

6

Conclusion

We have investigated the security of the ECDSA primitive and its relation to theelliptic curve discrete logarithm problem. Based on our analysis, we believe that therange of parameters offered by the standard can provide security for a number of years,
provided the lowest figures are gradually discarded, taking into account the progress ofcomputing power. The use of Koblitz curves, albeit suspicious, does not provide any
significant shortcut for the adversary.
We also believe that the security proof that the generic DSA withstands existential
forgery against adaptive chosen-message attacks, is mathematically sound. We haveindeed provided a security proof in Shoup’s style [46], different from the proof earlier
published in [6]. However, we have doubts on the actual significance of this proof.
Furthermore, we have shown that ECDSA does not withstand chosen-message attacks,
where forgeries that output a second signature of a message previously signed areallowed. The generic DSA provably withstands such forgeries. This seems to indicatethat the generic model is not appropriate. In conclusion, we regret that we cannot
recommend ECDSA without reservations.

24

References[1] American National Standards Institute. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm. ANSI
X9.62-1998, January 1999.
[2] R. Balasubramanian and N. Koblitz. The improbability than an elliptic curve
has subexponential discrete log problem under the Menezes-Okamoto-Vanstonealgorithm, J. Cryptology, 111, 1998, 141–145.
[3] M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for
Designing Efficient Protocols. In Proc. of the 1st CCS, pages 62–73, ACM Press,
New York, 1993.
[4] D. Bleichenbacher. Generating El Gamal Signatures without Knowing the SecretKey. In Eurocrypt ’96, LNCS 1070, pages 10–18, Springer-Verlag, Berlin, 1996.
[5] E. Brickell, D. Pointcheval, S. Vaudenay, and M. Yung. Design Validations for
Discrete Logarithm Based Signature Schemes. In PKC ’2000, LNCS 1751, pages
276–292, Springer-Verlag, Berlin, 2000.
[6] D. R. L. Brown. The Exact Security of ECDSA, January 2001. Available fromhttp://grouper.ieee.org/groups/1363/.
[7] R. Canetti, O. Goldreich, and S. Halevi. The Random Oracles Methodology,
Revisited. In Proc. of the 30th STOC, pages 209–218, ACM Press, New York,
1998.
[8] S. Cavallar, B. Dodson, A. K. Lenstra, W. Lioen, P. L. Montgomery, B. Murphy,
H. te Riele, K. Aardal, J. Gilchrist, G. Guillerm, P. C. Leyland, J. Marchand, F.
Morain, A. Muffett, C. Putnam, C. Putnam, P. Zimmermann. Factorization of a
512-Bit RSA Modulus. Eurocrypt’2000, LNCS 1807,(2000), 1–18, Springer-Verlag,
Berlin, 2000.
[9] Certicom. Information on the Certicom ECC challenge,
http://www.certicom.com/research/ecc challenge.html[10] Certicom. Standards for efficient cryptography, SEC1: elliptic curve cryptography,
sept, 20, 2000.
[11] Certicom. Standards for efficient cryptography, SEC2: Recommended elliptic
curve parameters, sept, 20, 2000.
[12] W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions
on Information Theory, IT–22(6):644–654, November 1976.
25

[13] T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms. IEEE Transactions on Information Theory, IT–31(4):469–
472, July 1985.
[14] A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions of Identificationand Signature Problems. In Crypto ’86, LNCS 263, pages 186–194, SpringerVerlag, Berlin, 1987.
[15] G. Frey, M. Müller, and H. G. Rück. The Tate-Pairing and the Discrete Logarithm
Applied to Elliptic Curve Cryptosystems. IEEE Transactions on Information
Theory, 45:1717–1719, 1999.
[16] G. Frey and H. G. Rück. A Remark Concerning m-Divisibility and the Discrete
Logarithm in the Divisor Class Group of Curves. Mathematics of Computation,
62:865–874, 1994.
[17] R. Gallant, R. Lambert and S.A. Vanstone. Improving the parallelized Pollard
lambda search on binary anomalous elliptic curves. Mathematics of Computation,
69, (2000), 1699–1705.
[18] S. Goldwasser, S. Micali, and C. Rackoff. The Knowledge Complexity of Interactive
Proof Systems. In Proc. of the 17th STOC, pages 291–304, ACM Press, New York,1985.
[19] S. Goldwasser, S. Micali, and R. Rivest. A “Paradoxical” Solution to the Signature
Problem. In Proc. of the 25th FOCS, pages 441–448, IEEE, New York, 1984.
[20] S. Goldwasser, S. Micali, and R. Rivest. A Digital Signature Scheme Secure
Against Adaptative Chosen-Message Attacks. SIAM Journal of Computing,17(2):281–308, April 1988.
[21] R. Harley, D. Doligez, D. de Rauglaudre, X. Leroy. Elliptic Curve Discrete Logarithms: ECC2K-108,
http://cristal.inria.fr/~harley/ecdl7/[22] IEEE P1363. Standard Specifications for Public Key Cryptography, August 1998.
Available from http://grouper.ieee.org/groups/1363/.
[23] KCDSA Task Force Team. The Korean Certificate-based Digital Signature Algorithm. Submission to IEEE P1363a, August 1998.
Available from http://grouper.ieee.org/groups/1363/.
[24] N. Koblitz. CM-curve with good cryptographic properties. In Crypto ’92,LNCS
576, pages 279–287, Springer-Verlag, Berlin, 1993.
26

[25] A.K. Lenstra and E. Verheul. Selecting cryptographic key sizes. PKC’2000, LNCS
1751,(2000), 446–465, Springer-Verlag, Berlin, 2000.
[26] J. Manger. A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption
Padding (OAEP) as Standardized in PKCS #1. In Crypto ’2001, LNCS 2139,
pages 230–238, Springer-Verlag, Berlin, 2001.
[27] D. Naccache, D. Pointcheval, and J. Stern. Twin Signatures: an Alternative tothe Hash-and-Sign Paradigm. In Proc. of the 8th CCS, ACM Press, New York,
2001.
[28] D. Naccache and J. Stern. Signing on a Postcard. In Financial Cryptography’2000, LNCS. Springer-Verlag, Berlin, 2000.
[29] V. I. Nechaev. Complexity of a Determinate Algorithm for the Discrete Logarithm.
Mathematical Notes, 55(2):165–172, 1994.
[30] NIST. Digital Signature Standard (DSS). Federal Information Processing Standards PUBlication 186, November 1994.
[31] NIST. Secure Hash Standard (SHS). Federal Information Processing Standards
PUBlication 180–1, April 1995.
[32] NIST. Digital Signature Standard (DSS). Federal Information Processing Standards PUBlication 186–2, January 2000.
[33] D. Pointcheval and J. Stern. Security Proofs for Signature Schemes. In Eurocrypt’96, LNCS 1070, pages 387–398, Springer-Verlag, Berlin, 1996.
[34] D. Pointcheval and J. Stern. Security Arguments for Digital Signatures and Blind
Signatures. Journal of Cryptology, 13(3):361–396, 2000.
[35] D. Pointcheval and S. Vaudenay. On Provable Security for Digital Signature Algorithms. Technical Report LIENS-96-17, LIENS, October 1996. Available fromhttp://www.di.ens.fr/users/pointche/pub.html.
[36] J. M. Pollard. Monte Carlo Methods for Index Computation (mod p). Mathematics
of Computation, 32(143):918–924, July 1978.
[37] R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures
and Public Key Cryptosystems. Communications of the ACM, 21(2):120–126,
February 1978.
[38] H.G. Rück. On the discrete logarithm in the divisor class group of curves. Preprint,
1997.
27

[39] T. Satoh, K. Araki. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, 1997, to appear in Commentarii Math. Univ.
St Pauli.
[40] C. P. Schnorr. Efficient Identification and Signatures for Smart Cards. In Crypto’89, LNCS 435, pages 235–251, Springer-Verlag, Berlin, 1990.
[41] C. P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161–174, 1991.
[42] C. P. Schnorr and M. Jakobsson. Security of Signed ElGamal Encryption. In
Asiacrypt ’2000, LNCS 1976, pages 458–469, Springer-Verlag, Berlin, 2000.
[43] I.A. Semaev. Evaluation of discrete logarithms in a group of p-torsion points ofan elliptic curve of characteristic p. Math. Comp., 67, 1998, 353–356.
[44] D. Shanks. Class Number, a Theory of Factorization, and Genera. In Proceedingsof the Symposium on Pure Mathematics, volume 20, pages 415–440. AMS, 1971.
[45] V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In
Eurocrypt ’97, LNCS 1233, pages 256–266, Springer-Verlag, Berlin, 1997.
[46] V. Shoup. OAEP Reconsidered. In Crypto ’2001, LNCS 2139, pages 239–259,
Springer-Verlag, Berlin, 2001. Also appeared in the Cryptology ePrint Archive
2000/060. November 2000. Available from http://eprint.iacr.org/.
[47] N.P. Smart. The discrete logarithm problem on elliptic curves of trace one. J.
Cryptology, 12, 1999, 141–151.
[48] J.A. Solinas. An improved algorithm for arithmetic on a family of elliptic curves.
In Crypto ’97, LNCS 1294, pages 357–371, Springer-Verlag, Berlin, 1997.
[49] P.C. van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic
applications, J. Cryptology, 12, 1999, 1–28.
[50] S. Vaudenay. Hidden Collisions on DSS. In Crypto ’96, LNCS 1109, pages 83–88,
Springer-Verlag, Berlin, 1996.
[51] M. J. Wiener and R.J. Zuccherato. Fast attacks on elliptic curve cryptosystems,
SAC’98, LNCS 1556, 190–200, Springer-Verlag, Berlin, 1999.

28