Short Signatures from the Weil Pairing.
We introduce a short signature scheme based on the Computational DiffieHellman assumption on certain elliptic and hyperelliptic curves. For standard security parameters, the signature length is about half that of a DSA signature with a similar level of security. Our short signature scheme is designed for systems where signatures are typed in by a human or are sent over a low-bandwidth channel. We survey a number of properties of our signature scheme such as signature aggregation and batch verification.
Introduction
Short digital signatures are needed in environments with strong bandwidth constraints. For ex-
ample, product registration systems often ask users to key in a signature provided on a CD label.
When a human is asked to type in a digital signature, the shortest possible signature is needed.
Similarly, due to space constraints, short signatures are needed when one prints a bar-coded digital
signature on a postage stamp [41, 37]. As a third example, consider legacy protocols that allocate
a xed short eld for non-repudiation [1, 25]. One would like to use the most secure signature that
ts in the alloted eld length.
The two most frequently used signatures schemes, RSA and DSA, produce relatively long signatures
compared to the security they provide. For example, when one uses a 1024-bit modulus,
RSA signatures are 1024 bits long. Similarly, when one uses a 1024-bit modulus, standard DSA
signatures are 320 bits long. Elliptic curve variants of DSA, such as ECDSA, are also 320 bits
long [2]. A 320-bit signature is too long to be keyed in by a human.
We propose a signature scheme whose length is approximately 170 bits and which provides
a level of security similar to that of 320-bit DSA signatures. Our signature scheme is secure
against existential forgery under a chosen-message attack (in the random oracle model) assuming
the Computational Di-e-Hellman problem (CDH) is hard on certain elliptic curves over a nite
eld. Generating a signature is a simple multiplication on the curve. Verifying the signature is done
using a bilinear pairing on the curve. Our signature scheme inherently uses properties of curves.
Consequently, there is no equivalent of our scheme in F
.
Constructing short signatures is an old problem. Several proposals show how to shorten DSA
while preserving the same level of security. Naccache and Stern [37] propose a variant of DSA
where the signature length is approximately 240 bits. Mironov [35] suggests a DSA variant with
a similar length and gives a concrete security analysis of the construction (in the random oracle
model). Another technique proposed for reducing DSA signature length is signatures with message
recovery [38, 41]. In such systems one encodes a part of the message into the signature thus
This is the full version of a paper that appeared in Asiacrypt '01 [12].
y Supported by NSF and the Packard Foundation.
shortening the total length of the message-signature pair. For long messages, one can then achieve
a DSA signature overhead of 160 bits. However, for very short messages (e.g., 64 bits) the total
length remains 320 bits. Using our signature scheme, the signature length is always on the order
of 160 bits, however short the message. When the message is not transmitted along with the
signature, DSA signatures with message recovery are just as long as standard DSA signatures. We
also note that Patarin et al. [40] construct short signatures whose security depends on the Hidden
Field Equation (HFE) problem.
Our signature scheme uses groups where the CDH problem is hard, but the Decision Di-e-
Hellman problem (DDH) is easy. The rst example of such groups was given in [27] and was
previously used in [26, 10]. We call such groups Gap Di-e-Hellman groups, or GDH groups for
short. We show how to construct a signature scheme from GDH groups; prove security of the
scheme; and show how to build GDH groups that lead to short signatures. The signature scheme
resembles the undeniable signature scheme of Chaum and Pederson [13]. Our signature scheme has
several useful properties, described in Section 5. For example, signatures generated by dierent
people on dierent messages can be aggregated into a single signature [11]. The signature also
supports standard extensions such as threshold signatures and blind signatures [9].
Notation. We use E=F q to denote an elliptic curve y
For r  1, we use E(F q r ) to denote the group of points on E in F q r . We use jE(F q r )j to denote the
number of points in E(F q r ).
Di-e-Hellman groups and bilinear maps
Before presenting the signature scheme, we rst review a few concepts related to bilinear maps and
Gap Di-e-Hellman groups. We use the following notation:
1. G 1 and G 2 are two (multiplicative) cyclic groups of prime order p;
2. g 1 is a generator of G 1 and g 2 is a generator of G
3. is an isomorphism from G 2 to G 1 , with (g 2
4. e is a bilinear map e
One can set G but we allow for the more general case where G 1 6= G 2 so that we can
take advantage of certain families of non-supersingular elliptic curves as described in Section 4.3.
The proofs of security require an e-ciently computable isomorphism
one could take to be the identity map. When G 1 6= G 2 we will need to
describe explicitly an e-ciently computable isomorphism . The map is essential for
security. To illustrate this, we give in the next section an example of a bilinear map that engenders
an insecure signature scheme precisely because does not exist.
With this setup we obtain natural generalizations of the CDH and DDH problems:
Computational co-Di-e-Hellman (co-CDH) on a
compute h a 2 G 1 .
Decision co-Di-e-Hellman (co-DDH) on a
yes if a = b and no otherwise. When the answer is yes we say that a
a ) is a
co-Di-e-Hellman tuple.
When these problems reduce to standard CDH and DDH.
Next we a dene a co-GDH gap group pair to be a pair of groups which co-DDH is
easy but co-CDH is hard. We dene the advantage of an algorithm A in solving the Computational
co-Di-e-Hellman problem on
Adv co-CDHA
a
In other words, the probability is over the uniform random choice of a from Z p and h from G 1 , and
over the coin tosses of A. We say that an algorithm A (t; )-breaks Computational co-Di-e-Hellman
on runs in time at most t, and Adv co-CDHA is at least .
Denition 2.1. Two groups are a (t; )-Gap co-Di-e-Hellman pair (co-GDH pair) if they
satisfy the following properties:
1. The group action on both G 1 and G 2 and the map from G 2 to G 1 can be computed in one
time unit.
2. The Decision co-Di-e-Hellman problem on can be solved in one time unit.
3. No algorithm (t; )-breaks Computational co-Di-e-Hellman on
When we say G 1 is a (t; )-Gap-Di-e-Hellman group (GDH group).
Note that in the above denition we are normalizing time so that all the above algorithms
take one time unit, and under this normalization there is no algorithm that (t; )-breaks CDH on
2.1 Bilinear maps
Currently, the only examples of Gap Di-e-Hellman groups arise from bilinear maps [27]. We brie
y
dene bilinear groups and show how they give GDH groups. It is possible that other constructions
for Gap Di-e-Hellman groups exist.
be two groups as above, with an additional group G T such that jG 1
jG T j. A bilinear map is a with the following properties:
1. Bilinear: for all u ab .
2. Non-degenerate: e(g
Denition 2.2. Two order-p groups are a (t; )-bilinear group pair if they satisfy the
following properties:
1. The group action on both G 1 and G 2 and the map from G 2 to G 1 can be computed in one
time unit.
2. A group G T of order p and a bilinear map e exist, and e is computable in
one time unit.
3. No algorithm (t; )-breaks Computational co-Di-e-Hellman on
Joux and Nguyen [26] showed that an e-ciently-computable bilinear map e provides an algorithm
for solving the Decision co-Di-e-Hellman problem as follows: For a tuple (g a
a
Consequently, if two groups are a (t; )-bilinear group pair, then they are also a (t=2; )-
co-GDH group pair. The converse is probably not true.
3 Signature schemes based on Gap Di-e-Hellman groups
We present a signature scheme that works in any Gap co-Di-e-Hellman group pair
prove security of the scheme and, in the next section, show how it leads to short signatures. The
scheme resembles the undeniable signature scheme proposed by Chaum and Pederson [13]. Okamoto
and Pointcheval [39] brie
y note that gap problems can give rise to signature schemes. However,
most gap problems will not lead to short signatures.
signature  is an
element of G 1 . The signature scheme comprises three algorithms, KeyGen, Sign, and Verify. It
makes use of a full-domain hash function . The security analysis views H as a
random oracle [7]. In Section 3.2 we weaken the requirement on the hash function H.
Key generation. Pick random x R
. The public key is v 2 G 2 . The
secret key is x.
Signing. Given a secret key x 2 Z p , and a message M 2 f0; 1g  , Compute
h x . The signature is  2 G 1 .
Verication. Given a public key v 2 G 2 , a message M 2 f0; 1g  , and a signature  2 G 1 , compute
verify that (g 2 ; v; h; ) is a valid co-Di-e-Hellman tuple. If so, output
valid; if not, output invalid.
A signature is a single element of G 1 . To construct short signatures, therefore, we need co-GDH
pairs where elements in G 1 have a short representation. We construct such groups in Section 4.
3.1
We prove the security of the Signature Scheme against existential forgery under a chosen-message
attacks in the random oracle model. Existential unforgeability under a chosen message attack [24]
for a signature scheme (KeyGen, Sign, and Verify) is dened using the following game between a
challenger and an adversary A:
Setup. The challenger runs algorithm KeyGen to obtain a public key PK and private key SK.
The adversary A is given PK.
Queries. Proceeding adaptively, A requests signatures with PK on at most q S messages of
his choice . The challenger responds to each query with a signature
Output. Eventually, A outputs a pair (M;) and wins the game if (1) M is not any of
We dene Adv Sig A to be the probability that A wins in the above game, taken over the coin tosses
of KeyGen and of A.
Denition 3.1. A forger A (t; q S ; q H ; )-breaks a signature scheme if A runs in time at most t; A
makes at most q S signature queries and at most q H queries to the hash function; and Adv Sig A is
at least . A signature scheme is (t; )-existentially unforgeable under an adaptive chosen-
message attack if no forger (t; q S ; q H ; )-breaks it.
The following theorem shows that the signature scheme is secure.
Theorem 3.2. Let of order p. Then the signature scheme
on against existential forgery under an adaptive chosen-message
attack (in the random oracle model) for all t and  satisfying
and c G 1
is a constant that depends on G 1 . Here e is the base of the natural logarithm.
Hence, security of the signature scheme follows from the hardness of co-CDH on
is based on the standard Computational Di-e-Hellman assumption in G 1 .
Proof of Theorem 3.2. Suppose A is a forger algorithm that (t; q )-breaks the signature
scheme. We show how to construct a t 0 -time algorithm B that solves co-CDH in
probability at least  0 . This will contradict the fact that are a
Let g 2 be a generator of G 2 . Algorithm B is given a
2 . Its
goal is to output h a 2 G 1 . Algorithm B simulates the challenger and interacts with forger A as
follows.
starts by giving A the generator g 2 and the public key u  g r
is random in Z p .
H-queries. At any time algorithm A can query the random oracle H. To respond to these queries
algorithm B maintains a list of tuples hM explained below. We refer to this list
as the H-list. The list is initially empty. When A queries the oracle H at a point M i 2 f0; 1g  ,
algorithm B responds as follows:
1. If the query M i already appears on the H-list in a tuple hM
responds with
2. Otherwise, B generates a random coin c i 2 f0; 1g so that Pr[c
3. Algorithm B picks a random b i 2 Z p .
4. Algorithm B adds the tuple hM to the H-list and responds to A by setting
Note that either way w i is uniform in G 1 and is independent of A's current view as required.
Signature queries. Let M i be a signature query issued by A. Algorithm B responds to this query
as follows:
1. Algorithm B runs the above algorithm for responding to H-queries to obtain a w
such that H(M i be the corresponding tuple on the H-list. If
reports failure and terminates.
2. We know c
Observe that
i and therefore  i is a valid signature on M i under the public key
2 . Algorithm B gives  i to algorithm A.
Output. Eventually algorithm A produces a message-signature pair (M f ;  f ) such that no signature
query was issued for M f . If there is no tuple on the H-list containing M f then B issues a
query itself for H(M f ) to ensure that such a tuple exists. We assume  f is a valid signature on
M f under the given public it is not, B reports failure and terminates. Next, algorithm B
nds the tuple hM f ; w; b; ci on the H-list. If reports failure and terminates.
Otherwise,
outputs the required h a as h a =(h r  (u) b  (g 2 ) rb ).
This completes the description of algorithm B. It remains to show that B solves the given instance
of the co-CDH problem in with probability at least  0 . To do so, we analyze the three
events needed for B to succeed:
does not abort as a result of any of A's signature queries.
generates a valid message-signature forgery (M f ;  f ).
for the tuple containing M f on the H-list.
succeeds if all of these events happen. The probability
The following claims give a lower bound for each of these terms.
1: The probability that algorithm B does not abort as a result of A's signature queries is
at least 1=e. Hence,
Proof. Without loss of generality we assume that A does not ask for the signature of the same
message twice. We prove by induction that after A makes i signature queries the probability
that B does not abort is at least (1 1=(q S . The claim is trivially true for
be A's i'th signature query and let hM be the corresponding tuple on the H-list. Then
prior to issuing the query, the bit c i is independent of A's view | the only value that could be given
to A that depends on c i is H(M i ), but the distribution on H(M i ) is the same whether c
Therefore, the probability that this query causes B to abort is at most 1=(q S 1). Using
the inductive hypothesis and the independence of c i , the probability that B does not abort after
this query is at least (1 1=(q S This proves the inductive claim. Since A makes at most
signature queries the probability that B does not abort as a result of all signature queries is at
least (1 1=(q S
2: If algorithm B does not abort as a result of A's signature queries then algorithm A's
view is identical to its view in the real attack. Hence, Pr[E
Proof. The public key given to A is from the same distribution as a public key produced by
algorithm KeyGen. Responses to H-queries are as in the real attack since each response is uniformly
and independently distributed in G 1 . All responses to signature queries are valid. Therefore, A
will produce a valid message-signature pair with probability at least . Hence, Pr[E
3: The probability that algorithm B does not abort after A outputs a valid forgery is at
least
Proof. Given that events E 1 and E 2 happened, algorithm B will abort only if A generates a forgery
which the tuple hM f ; w; b; ci on the H-list has c = 1. At the time A generates its
output it knows the value of c i for those M i for which it issued a signature query. All the remaining
are independent of A's view. Indeed, if A did not issue a signature query for M i then the
only value given to A that depends on c i is H(M i ), but the distribution on H(M i ) is the same
whether c could not have issued a signature query for M f we know that c
is independent of A's current view and therefore
Using the bounds from the claims above in equation (1) shows that B produces the correct
answer with probability at least =e(q Algorithm B's running time is the
same as A's running time plus the time is takes to respond to (q H +q S ) hash queries and q S signature
queries. Each query requires an exponentiation in G 1 which we assume takes time c G 1
. Hence, the
total running time is at most t
This completes the proof of
Theorem 3.2.
The analysis used in the proof of Theorem 3.2 resembles Coron's analysis of the Full Domain
Hash We note that Probabilisitc Full Domain Hash (PFDH) signatures
[16] have a tighter security reduction than FDH signatures. The same improvement to
the security reduction can be applied to our signature scheme. However, randomizing our signature
scheme as in PFDH would increase the length of the signature, defeating our main goal of
constructing short signatures.
The necessity of Recall that the proof of security relied on the existence of an
e-ciently computable isomorphism To show the necessity of we give an example of
a bilinear map e for which the co-CDH problem is believed to be hard on (G 1
and yet the resulting signature scheme is insecure.
Let q be a prime and let G 2 be a subgroup of Z
q of prime order p with generator g. Let G 1
be the group G addition modulo p. Dene the
as . The map is clearly bilinear since e(ax; y b ab . The co-CDH problem on
Given . The problem is believed to
be hard since an algorithm for computing co-CDH on gives an algorithm for computing
discrete log in G 2 . Hence, all the conditions of Theorem 3.2 except that there is
no known computable isomorphism . It is is easy to see that the resulting signature
scheme from this bilinear map is insecure: Given one message-signature pair, it is easy to recover
the secret key.
We comment that one can avoid using at the cost of making a stronger complexity assumption.
Without the necessary assumption for proving security is that no polynomial time algorithm can
compute h a 2 G 1 given a
a
naturally exists in all the group
are considering, there is no reason to rely on this stronger complexity assumption.
3.2 Hashing onto elliptic curves
The signature scheme needs a hash function . In the next section we use elliptic
curves to construct co-GDH groups and therefore we need a
G 1 is a subgroup of an elliptic curve. Since it is di-cult to build hash functions that hash directly
onto a subgroup of an elliptic curve we slightly relax the hashing requirement.
Let E=F q be an elliptic curve dened by y
be a point of prime order p. We wish to hash onto the subgroup G Suppose we are given
a hash function 1g. Such hash functions H 0 can be built from standard
cryptographic hash functions. The security analysis will view H 0 as a random oracle. We use the
following deterministic algorithm called MapToGroup to hash messages in f0; 1g  onto G 1 . Fix a
small parameter I = dlog 2 log 2 (1=-)e, where - is some desired bound on the failure probability.
: The algorithm denes H : f0; 1g  ! G 1 as follows:
1. Given M 2 f0; 1g  , set i 0;
2. represented as an I-bit string;
3. If f(x) is a quadratic residue in F q then do:
3a. Let y q be the two square roots of f(x). We use b 2 f0; 1g to choose between these
roots. Choose some full ordering of F q and ensure that y 1 is greater than y 0 according
to this ordering (swapping y 0 and y 1 if necessary). Set ~
to be the point
~
3b. Compute
PM . Then PM is in G 1 . Output MapToGroup H 0
stop.
4. Otherwise, increment i, and go to Step 2; if i reaches 2 I , report failure.
The failure probability can be made arbitrarily small by picking an appropriately large I. For
each i, the probability that H 0 (i k M) leads to a point on G is approximately 1=2 (where the
probability is over the choice of the random oracle H 0 ). Hence, the expected number of calls to
H 0 is approximately 2, and the probability that a given message M will be found unhashable is
Lemma 3.3. Let E=F q be an elliptic curve and let E(F q ) have order m. Let G 1 be a subgroup
of E(F q ) of order p. We assume p 2 does not divide m. Suppose the co-GDH signature scheme is
(t; )-secure in the groups used.
Then it is (t 2 I c G 1
)-secure when the hash function H is computed with MapToGroup H 0
and H 0 is a random hash function 1g.
Proof Sketch. Suppose a forger algorithm F 0 (t; )-breaks the signature scheme on
when the hash function H is computed using MapToGroup H 0 . We build an algorithm F that
)-breaks the signature scheme when H is a random oracle
Our new forger F will run F 0 as a black box. Algorithm F passes signatures queries made by
F 0 to its own signature oracle. F uses its hash oracle to simulate for F 0 the
behavior of MapToGroup H 0 . It uses an array s ij , whose entries are elements of F q  f0; 1g. The
array has q H rows and 2 I columns. On initialization, F lls s ij with uniformly-selected elements of
F q  f0; 1g.
F then runs F 0 , and keeps track (and indexes) all the unique messages M i for which F 0 requests
an H 0 hash. When F 0 asks for an H 0 hash of a message w k M i whose M i the forger F had not
previously seen (and whose w is an arbitrary I-bit string), F scans the row s ij , 0  j < 2 I . For
each seeking points in G. For the smallest j
for which s ij maps into G 1 , F replaces s ij with a dierent point dened as follows. Let
constructs a random point ~
follows:
1. Let p. Note that m=p is integer since p divides m. Furthermore, m=p has
an inverse modulo p since p 2 does not divide m and hence m=p is relatively prime to p.
2. Pick a random point
3. Set ~
Then ~
is a random point in E(F q ) such that (m=p) ~
is set so that maps to ~
in Step 3a of MapToGroup. Then MapToGroup H 0
as required.
Once this preliminary patching has been completed, F is able to answer H 0 hash queries by
F 0 for strings w k M i by simply returning s iw . The simulated H 0 which F 0 sees is statistically
indistinguishable from that in the real attack. Thus, if F 0 succeeds in breaking the signature
scheme using MapToGroup H 0 then F , in running F 0 while consulting H, succeeds with the same
likelihood, and suers only a running-time penalty from maintaining the additional information
and running the exponentiation in Step 3 of the MapToGroup algorithm. We again assume that
exponentiation in G 1 takes time c G 1
Building co-GDH groups with small representations
Using the Weil [29, pp. 243{245] and Tate [18] pairings, we obtain co-GDH groups from certain
elliptic curves. We recall some necessary facts about elliptic curves (see, e.g., [29, 44]), and then
show how to use certain curves for short signatures.
4.1 Elliptic curves and the Weil pairing
Our goal is to construct bilinear groups which lead to co-GDH groups as discussed in
Section 2.1. Let E=F q be an elliptic curve. We rst dene a useful constant called the security
multiplier of a subgroup hP i  E(F q ).
Denition 4.1. Let q be a prime power, and E=F q an elliptic curve with m points in E(F q ). Let
P in E(F q ) be a point of prime order p where m. We say that the subgroup hP i has a security
multiplier , for some integer  > 0, if the order of q in F
p is . In other words:
The security multiplier of E(F q ) is the security multiplier of the largest prime order subgroup in
E(F q ).
We describe two families of curves that provide  = 6. For standard security parameters this is
su-cient for obtaining short signatures. It is an open problem to build useful elliptic curves with
slightly higher , say
Our rst step is to dene G 1 and G 2 . We will then describe a bilinear map e
describe an isomorphism discuss the intractability of co-CDH on
Balasubramanian-Koblitz. Let E=F q be an elliptic curve and let P 2 E(F q ) be a point of
prime order p with p 6= q. Suppose the subgroup hP i has security multiplier  > 1, i.e. p - q 1.
Then, a useful result of Balasubramanian and Koblitz [3] shows that E(F q  ) contains a point Q of
order p that is linearly independent of P . We set G
Note that G 1  E(F q ) and G 2  E(F q  ).
The Weil and Tate pairings. Let E[p] be the group of points of order dividing p in E(F q  ).
Then the group E[p] is isomorphic to Z p  Z p [44] and also G 1 ; G 2  E[p]. The Weil pairing is a
q  with the following properties:
1.
2. Bilinear: for all R 1
3. Non-degenerate: if for R 2 E[p] we have e(R; R 0
4. Computable: for all R 1 the pairing e(R 1 computable in polynomial
time [34].
Note that e(R 1 only if R 1 and R 2 are linearly dependent. See [31, 10] for a denition
of the Weil pairing and a description of the algorithm for computing it. The Tate pairing [18] is
another useful bilinear map on E[p]. It has properties similar to those of the Weil pairing, but does
not necessarily satisfy Property 1 (identity).
The Weil pairing on the curve E gives a computable, non-degenerate bilinear
F
q  which enables us to solve the Decision co-Di-e-Hellman problem on the groups
the Tate pairing is non-degenerate on G 1 G 2 it can also be used to solve Decision co-Di-e-Hellman
on
The trace map. We present a computable isomorphism using the trace map, tr,
which sends points in E(F q  ) to E(F q ). Let   be the Galois maps of F q  over F q . Also,
the trace map tr : E(F q
dened by:
Fact 4.2. Let P 2 E(F q ) be a point of prime order p 6= q and let hP i have security multiplier
> 1. Let Q 2 E(F q  ) be a point of order p that is linearly independent of P . If tr(Q) 6= O then
tr is an isomorphism from hQi to hP i.
Proof. Suppose R 2 E(F q ) is a point of order p. If R is not in hP i then P and R generate E[p]
and therefore E[p]  E(F q ). It follows that e(P; R) 2 F
q has order p since otherwise e would be
degenerate on E[p]. But since  > 1 we know that p does not divide q 1 and consequently there
are no elements of order p in F
q . Hence, we must have R 2 hP i. It follows that all the points in
E(F q ) of order p are contained in hP i. Since tr(Q) 6= O, we know that tr(Q) 2 E(F q ) has order p
and therefore tr(Q) 2 hP i. Hence, tr is an isomorphism from hQi to hP i.
Hence, when tr(Q) 6= O, the trace map is an isomorphism from G 2 to G 1 and is computable in
polynomial time in  and log q as required.
Intractability of co-CDH on remaining question is the di-culty of the co-CDH
problem on necessary conditions for CDH intractability. The best known
algorithm for solving co-CDH on is to compute discrete-log in G 1 . In fact, the discrete-log
and CDH problems in G 1 are known to be computationally equivalent given some extra information
about the group G 1 [30]. Therefore, it su-ces to consider necessary conditions for making the
discrete-log problem on E(F q ) intractable.
Let hP i be a subgroup of E(F q ) of order p with security multiplier . We brie
y discuss two
standard ways for computing discrete-log in hP i.
1. MOV: Use an e-ciently computable homomorphism, as in the MOV reduction [32], to map
the discrete log problem in hP i to a discrete log problem in some extension of F q , say F q i . We
then solve the discrete log problem in F
using the Number Field Sieve algorithm [43]. The
image of hP i under this homomorphism must be a subgroup of F
q i of order p. Thus we have
which by the denition of  implies that i  . Hence, the MOV method can, at
best, reduce the discrete log problem in hP i to a discrete log problem in a subgroup of F
q  .
Therefore, to ensure that discrete log is hard in hP i we want curves where  is su-ciently
large to make discrete log in F
q  intractable.
2. Generic: Generic discrete log algorithms such as Baby-Step-Giant-Step and Pollard's Rho
method [33] have a running time proportional to p p. Therefore, we must ensure that p
is su-ciently large.
In summary, we want curves E=F q where both a generic discrete log algorithm in E(F q ) and
the Number Field Sieve in F
q  are intractable.
4.2 Co-GDH signatures from elliptic curves
We summarize the construction for co-GDH groups and adapt the signature scheme to use a group
of points on an elliptic curve.
The co-GDH groups use are dened as follows:
1. Let E=F q be an elliptic curve and let P 2 E(F q ) be a point of prime order p where (1) p 6= q,
does not divide jE(F q )j.
2. Let  > 1 be the security multiplier of hP i. By Balasubramanian and Koblitz [3] there exists
a point Q 2 E(F q  ) that is linearly independent of P . It is easy to construct such a Q in
expected polynomial time once the number of points in E(F q  ) is known. Since  > 1 we
know that Q 62 E(F q ). We ensure that tr(Q) 6= O. If replace Q by Q+ P . Then
Q+ P is of order p, it is linearly independent of P , and tr(Q
3.
4. Since P and Q are linearly independent, the Weil pairing gives a non-degenerate bilinear map
q  . It can be computed in polynomial time in  and log q. When the Tate
pairing is non-degenerate on G 1 G 2 it can also be used as a bilinear map.
5. Since tr(Q) 6= O the trace map on E(F q  ) is an isomorphism from G 2 to G 1 computable in
polynomial time in  and log q.
With these subgroups G 1 ; G 2 of the elliptic curve E=F q the signature scheme works as follows.
Recall that MapToGroup H 0 is a hash function MapToGroup built from a hash
function
q  f0; 1g as described in Section 3.2.
Key generation Pick random x R
xQ. The public key is V 2 E(F q  ).
The secret key is x.
Signing Given a secret key x 2 Z p , and a message M 2 f0; 1g  , do:
1. Compute
2.  xR 2 E(F q ), and
3. output the x-coordinate of  as the signature s on M . Then s 2 F q .
Verication Given a public key V 2 G 2 , a message M 2 f0; 1g  , and a signature s 2 F q do:
1. Find a y 2 F q such that is a point of order p in E(F q ). If no such y exists,
output invalid and stop.
2. Compute
3. Test if either e(;
If so, output valid; Otherwise, output invalid.
The signature length is dlog 2 qe. Note that during verication we accept the signature if
This is to account for the fact that the signature s 2 F q could have come
from either the point  or  in E(F q ).
Security. By Theorem 3.2 it su-ces to study the di-culty of co-CDH on best
known algorithm for solving the co-CDH problem on requires the computation of a discrete
log in G 1 or the computation of a discrete log in F
q  .
4.3 Using non-supersingular curves over elds of high characteristic
It remains to build elliptic curves with the desired security multiplier . In the next two sections we
show curves with security multiplier, by describing a family of non-supersingular
elliptic curves with This family is outlined by Miyaji et al. [36]. We call these MNT curves.
The idea is as follows: Suppose
can be veried that p divides q 6 1, but does not divide q i 1 for 0 < i < 6. So, when p is prime,
a curve E=F q with p points is likely to have security multiplier
Discriminant Signature Size DLog Security MOV Security
28894627 177 177 1062
9877443 206 206 1236

Table

1: Non-supersingular elliptic curves for co-GDH Signatures. E is a curve over the prime eld
F q and p is the largest prime dividing its order. The MOV reduction maps the curve onto the eld
. D is the discriminant of the complex multiplication eld of E=F q .
To build E=F q with p points as above we use complex multiplication [8, chapter VIII]. We brie
y
explain how to do so. Suppose we had integers another positive integer
that
is an integer prime. Then the complex multiplication method will produce an elliptic curve E=F q
with points in time O(D 2 (log q) 3 ). The value t is called the trace of the curve.
We want a curve over F q with p points where
Plugging these values into (2) we get
leads to:
For a xed 4, we need integers satisfying the equation above such that
is prime and prime (or is a small multiple of a prime). For any such solution
we can verify that we get a curve E(F q ) with security multiplier Finding integer solutions
'; y to an equation of type (3) is done by reducing it to Pell's equation, whose solution is well
known [45].

Table

some values of D that lead to suitable curves for our signature scheme. For
example, we get a curve E=F q where q is a 168-bit prime. Signatures using this curve are 168-bits
while the best algorithm for co-CDH on E(F q ) requires either (1) a generic discrete log algorithm
taking time approximately 2 83 , or (2) a discrete log in a 1008-bit nite eld of large characteristic.
4.4 A special supersingular curve
Another method for building curves with security multiplier 6 is to use a special supersingular
curve E=F 3 . Specically, we use the curve . The MOV reduction maps
the discrete log problem in E(F 3 ' ) to F
. We use two simple lemmas to describe the behavior of
these curves. (See also [47, 28].)
Lemma 4.3. The curve dened by y
The curve E dened by y
Proof. See [28, section 2].
Lemma 4.4. Let E be an elliptic curve dened by y
1 or 5. Then jE(F 3 ' )j divides 3 6' 1.
Proof. See [47].
Together, Lemmas 4.3 and 4.4 show that, for the relevant values of ', groups on the curves
multiplier  at most 6 (more specically:  j 6). Whether
the security parameter actually is 6 for a particular prime subgroup of a curve must be determined
by computation.
Automorphism of
have a useful automorphism that
make the prime-order subgroups of (as opposed to co-GDH
groups). This fact can be used to shrink the size of the public key since it makes it possible for for
the public key to live in E(F 3 ' ) as opposed to E(F 3 6' ).
The automorphism is dened as follows. For ' such that ' mod 12 is 1 or 5, compute three
elements of F 3 6' , u, r + , and r , satisfying
Now consider the following maps over F 3 6'
Lemma 4.5. Let ' mod 12 equal 1 or 5. Then  + is an automorphism of
is an automorphism of E =F 3 6' . Moreover, if P is a point of order p on
a point of order p that is linearly independent of P .
Proof. See Silverman [44, p. 326].
Let E=F 3 ' be one of E be a point of prime order p. Set G
the group generated by P . Let  : E(F 3 '
) be the automorphism of the curve from above.
Dene the modied Weil pairing ^
is the standard Weil pairing on E[p]. By Lemma 4.5 we know that (P ) is linearly independent of
e is non-degenerate. It follows that G 1 is a GDH group. This has two implications
for the signature scheme:
Security of the signature scheme is based on the di-culty of the standard Computational
Di-e-Hellman problem in G 1 (as opposed to the co-CDH problem).
Public keys are elements of G 1 and, hence, are shorter than public keys should the automorphism
not exist.
curve l Sig Size DLog Security MOV Security

Table

2: Supersingular elliptic curves for GDH signatures. Here p is the largest prime divisor of
)j. The MOV reduction maps the curve onto a eld of characteristic 3 of size 3 6' .
Useful curves. Some useful instantiations of these curves are presented in Table 2. Note that
we restrict these instantiations to those where ' is prime, to avoid Weil-descent attacks [21, 22],
except for 121. It has recently been shown that certain Weil-descent attacks are not eective
for this case [17], suggesting that it may be safe to use.
Performance. Galbraith et al. [20] and Baretto et al. [4] show that the Frobenius map on the
can be used to speed the computation of the Weil and Tate pairings on these
curves. This results in a signicant speed-up to the signature-verication algorithm. Consequently,
the signature scheme using these curves is much faster than the scheme using the curves from the
previous section.
The bad news. MOV reduces the discrete log problem on to a discrete
log problem in F
. A discrete-log algorithm due to Coppersmith [14, 43] is specically designed
to compute discrete log in small characteristic elds. Consequently, a discrete-log problem in F
is much easier than a discrete-log problem in F
where p is a prime of approximately the same size
as 3 n . To get security equivalent to DSA using a 1024-bit prime, we would have to use a curve
much larger than 1024 bits. This leads to much longer signatures, defeating
the point of using these curves. In other words, for a xed signature length, these supsersingular
curves lead to a signature with reduced security compared to the curves of the previous section.
4.5 An open problem: higher security multipliers
With the curves of Section 4.3, a security multiplier of su-cient for constructing short
signatures with security comparable to DSA using a 1024-bit prime. However, to obtain security
comparable to DSA using a 2048-bit prime with signatures of length
bits. Elliptic curves with higher , say would result in short signatures when higher security
is needed (such as 2048-bit discrete-log security).
Let q be a large prime power, say, q > 2 160 . It is currently an open problem to construct an
elliptic curve E=F q such that E(F q ) has prime order. Baretto et al. [5]
show how to build elliptic curves E such that E(F q ) has a given security multipliers . However,
the largest prime order subgroup of E(F q ) is much smaller than q. Consequently, these curves
cannot be used for secure short signatures | a generic discrete-log algorithm in E(F q ) will break
the scheme in time proportional to p p where p is the largest prime factor of jE(F q )j.
One could also build GDH groups of higher genus. Galbraith [19] constructs supersingular curves
of higher genus with a \large" security multiplier. For example, the Jacobian of the supersingular
curve a point on the Jacobian of this
curve of genus two is characterized by two values in F 2 ' (the two x-coordinates in a reduced divisor),
the length of the signature is 2' bits. Hence, we might obtain a signature of length 2' with security
of computing CDH in the nite eld F 2 12' . This factor of 6 between the length of the signature
and the degree of the nite eld is the same as in the elliptic curve case. Hence, this genus 2
curve does not improve the security of the signature, but does give more variety in curves used for
short signatures. Discrete log on the Jacobian of these curves is reducible to discrete-log in a eld
of characteristic 2 and consequently one must take Coppersmith's discrete log algorithm [14] into
account, as discussed at the end of Section 4.4.
To obtain larger security multipliers, Rubin and Silverberg [42] propose certain Abelian varieties.
Supercially, they show that signatures produced using the curve of Section 4.4 can be shortened
by 20%. The result is an n-bit signature where the pairing reduces the discrete log problem to a
nite eld of size approximately 2 7:5n . This is the only useful example we currently know of where
the multiplier is greater than 6.
Extensions
Our signatures support threshold signatures and batch verication. Surprisingly, signatures from
distinct people on distinct messages can be aggregated into a single convincing signature. We
brie
y survey these extensions here and refer to Boldyreva [9], Verheul [46], and Boneh et al. [11]
for a full description and proofs of security.
5.1 Aggregate signatures
Common environments require managing many signatures by dierent parties on distinct messages.
For example, certicate chains contain signatures on distinct certicates issued by various Certi-
cate Authorities. Our signature scheme enables us to aggregate multiple signatures by distinct
entities on distinct messages into a single short signature. Any party that has all the signatures
can aggregate signatures, and aggregation can be done incrementally: Two signatures are aggre-
gated, then a third is added to the aggregate, and so on. See [11] for more applications.
be a bilinear group pair of prime order p. Suppose n users each have a public-private
Suppose user i signs a message M i 2 f0; 1g  to obtain the signature  . The
aggregate of all these signatures is computed simply as   1  2     n 2 G 1 .
Aggregate verication: We are given all public
f0; 1g  , and the aggregate signature  2 G 1 . To verify that, for all signed
message M i , we test that
1. The messages are all distinct, and
2. e(;
If both conditions hold, we accept the aggregate signature. Otherwise, we reject.
We refer to [11] for the exact security model and the proof of security. An attacker who can
existentially forge an aggregate signature can be subverted to solve co-CDH on
that aggregate signature verication requires a bilinear map| a generic Gap Di-e-Hellman group
is apparently insu-cient. Generic Gap Di-e-Hellman groups are su-cient for verifying aggregate
signatures on the same message by dierent people, or for verifying aggregate signatures on distinct
messages by the same person.
5.2 Batch verication
Suppose n users all sign the same message M 2 f0; 1g  . We obtain n signatures  We
show that these n signatures can be veried as a batch much faster than verifying them one by
one. A similar property holds for other signature schemes [6].
be a co-GDH group pair of prime order p. Suppose user i's private key is x
and his public key is v
To verify the n signatures
as a batch we use a technique due to Bellare et al. [6]:
1. Pick random integers c n from the range [0; B] for some value B. This B controls the
error probability as discussed below.
2. Compute
3. Test that (g 2 ; V; H(M);U) is a co-DDH tuple. Accept all n signatures if so; reject otherwise.
Theorem 3.3 of [6] shows that we incorrectly accept the n signatures with probability at most
1=B. Hence, verifying the n signatures as a batch is faster than verifying them one by one. Note
that if all signers are required to prove knowledge of their private keys, then taking c
is su-cient, yielding even faster batch verication [9]. A similar batch verication procedure can
be used to verify quickly n signatures on distinct messages issued by the same public key.
5.3 Threshold signatures
Using standard secret sharing techniques [33], our signature scheme gives an immediate robust
t-out-of-n threshold signature [9]. In a threshold signature scheme, there are n parties where each
possesses a share of a private key. Each party can use its share of the private key to produce a
share of a signature on some message M . A complete signature on M can only be constructed if
at least t shares of the signature are available.
A robust t-out-of-n threshold signature scheme derives from our signature scheme as follows. A
central authority generates a public/private key pair. Let x 2 Z p be the private key and
be the public key. The central authority picks a random degree t 1 polynomial
that user i the value x its share of the
private key. The authority publishes the public key v and n values
When a signature a on a message M 2 f0; 1g  is needed each party that wishes to participate
in signature generation publishes its share of the signature as  loss of
generality, assume users participate and generate shares  . Anyone can verify that
share  i is valid by checking that (g 2 ; co-Di-e-Hellman tuple. When all t shares
are valid, the complete signature is recovered as
Y
(mod
If fewer than t users are able to generate a signature on some message M then these users can
be used to solve co-CDH on threshold scheme is robust: A participant who
contributes a bad partial signature  i will be detected immediately since (g
be a co-Di-e-Hellman tuple.
We note that there is no need for a trusted third party to generate shares of the private key.
The n users can generate shares of the private key without the help of a trusted third party using
the protocol due to Gennaro et al. [23].
6 Conclusions
We presented a short signature based on bilinear maps on elliptic curves. A signature is only one
element in a nite eld. Standard signatures based on discrete log such as DSA require two elements.
Our signatures are much shorter than all current variants of DSA for the same security. We showed
that the scheme is existentially unforgeable under a chosen message attack (in the random oracle
model) assuming the Computational Di-e-Hellman problem is hard in certain elliptic-curve groups.
More generally, the signature scheme can be instantiated on any Gap Di-e-Hellman group or co-
GDH group pair.
We presented two families of elliptic curves that are suitable for obtaining short signatures. The
rst, based on [36], is a family of non-supersingular curves over a prime nite eld. The second uses
supersingular curves over F 3 ' . Both families of curves produce n-bit signatures and the discrete log
problem on these curves is reducible to a discrete log problem in a nite eld of size approximately
2 6n . Hence, for 1024-bit security we get signatures of size
We expect that the rst family of curves (the non-supersingular curves) will be the one used for
short signatures: 171-bit signatures with 1024-bit security. As discussed at the end of Section 4.4,
the second family of curves (the supersingular curve over F 3 ' ) should not be used for short signa-
tures. The problem is that discrete log on these curves reduces to a discrete log in a nite eld of
characteristic 3 where Coppersmith's algorithm can be used.
Implementation results [20, 4] indicate that the signature scheme performs well. Signature
generation is just a simple multiplication on an elliptic curve and is faster than RSA signature
generation. Verication requires two computations of the bilinear map and is slower than RSA
signature verication.
In Section 4.5 we outlined an open problem that would enable us to get even better security
while maintaining the same length signatures. We hope future work on constructing elliptic curves
or higher genus curves will help in solving this problem.

Acknowledgments

The authors thank Steven Galbraith, Alice Silverberg, Moni Naor, Victor Shoup, Scott Renfro,
Paulo Barreto, and Doug Kuhlman for helpful discussions about this work.



--R

DSTU X9.
62 and FIPS 186-2
The Improbability That an Elliptic Curve Has Subexponential Discrete Log Problem under the Menezes-Okamoto-Vanstone Algorithm

Constructing Elliptic Curves with Prescribed Embedding Degrees.
Fast Batch Veri
The Exact Security of Digital Signatures: How to Sign with RSA and Rabin.
Elliptic Curves in Cryptography


Aggregate and Veri
Short signatures from the Weil pairing.
Wallet Databases with Observers.
Fast Evaluation of Logarithms in Fields of Charateristic Two.
On the Exact Security of Full Domain Hash.
Optimal Security Proofs for PSS and Other Signature Schemes.
The GHS-Attack in Odd Characteristic
The Tate Pairing and the Discrete Logarithm Applied to Elliptic Curve Cryptosystems.
Supersingular Curves in Cryptography.
Implementing the Tate Pairing.
A Cryptographic Application of Weil Descent.
Constructive and Destructive Facets of Weil Descent on Elliptic Curves.
Secure Distributed Key Generation for Discrete-Log Based Cryptosystems
A Digital Signature Scheme Secure against Adaptive Chosen-Message Attacks
ISO 8583: Financial Transaction Card Originated Messages
A One Round Protocol for Tripartite Di-e-Hellman
Separating Decision Di-e-Hellman from Di-e-Hellman in Cryptographic Groups
An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm.
Elliptic Functions.
Towards the Equivalence of Breaking the Di-e-Hellman Protocol and Computing Discrete Logarithms
Elliptic Curve Public Key Cryptosystems.
Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field.
Handbook of Applied Cryptography.
Short Programs for Functions on Curves.
A Short Signature as Secure as DSA.
New Explicit Conditions of Elliptic Curve Traces for FR-Reduction
Signing on a Postcard.
Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem.
The Gap Problems: A New Class of Problems for the Security of Cryptographic Primitives.

Postal Revenue Collection in the Digital Age.
Supersingular Abelian Varieties in Cryptology.
Discrete Logarithms: The E
The Arithmetic of Elliptic Curves
The Algorithmic Resolution of Diophantine Equations.

Abelian Varieties over Finite Fields.
--TR

--CTR
Meiyuan Zhao , Sean W. Smith , David M. Nicol, Aggregated path authentication for efficient BGP security, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
Gyeong Kang , Je Hong Park, On the relationship between squared pairings and plain pairings, Information Processing Letters, v.97 n.6, p.219-224, 31 March 2006
Giuseppe Ateniese , Alfredo De Santis , Anna Lisa Ferrara , Barbara Masucci, Provably-secure time-bound hierarchical key assignment schemes, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
Giuseppe Ateniese , Susan Hohenberger, Proxy re-signatures: new definitions, algorithms, and applications, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
Giuseppe Ateniese , Jan Camenisch , Breno de Medeiros, Untraceable RFID tags via insubvertible encryption, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
short signatures;digital signatures;bilinear maps;elliptic curves;pairings