. 9
( 10)


prime order r, e : G1 — G1 ’ G3 is a bilinear map and H2 : G3 ’ {0, 1}n is
a hash function.
In Gentry™s CBE scheme, an entity A™s private key consists of two com-
ponents. The ¬rst component [sC ]PA (i) is time-dependent and is issued as
a certi¬cate to A on a regular basis by a CA. Here sC is the CA™s private
key and PA (i) ∈ G1 is derived from hashing certain parameters, including
A™s public key [sA ]P and the current time interval i. The second component
[sA ]PA is chosen by A and kept private. Here, PA ∈ G1 is derived from A™s
identifying data. So A™s private key is the sum [sC ]PA (i) + [sA ]PA , a time-
dependent value that is only available to A if A is certi¬ed in the current time
interval. Now, to encrypt a message M for A, an entity selects t at random
from Z— and sets:

C = [t]P, M • H2 (ˆ([sC ]P, PA (i))t · e([sA ]P, PA )t ) .
e ˆ
Notice that [sC ]P is available to encrypting parties as a public parameter of
the CA, while PA (i), PA can be computed from A™s public information and
[sA ]P is A™s public key. Decryption by A is straightforward if A has [sC ]PA (i).
For if C = U, V , then A can compute:
e(U, [sC ]PA (i) + [sA ]PA ) = e([t]P, [sC ]PA (i)) · e([t]P, [sA ]PA )
ˆ ˆ ˆ
= e([sC ]P, PA (i)) · e([sA ]P, PA )t .
ˆ ˆ
Notice that the private key [sC ]PA (i) + [sA ]PA used here can be regarded
as a two-party aggregate signature in the scheme of [40]. The second private
component [sC ]PA (i) acts as an implicit certi¬cate for relying parties, one
that a relying party can be assured is only available to A provided that A™s
certi¬cate has been issued for the current time period by the CA. The security
of CBE depends critically on the CA binding the correct public key into A™s

implicit certi¬cate in each time period. Thus (quite naturally), the initial
registration of users and their public keys must take place over an authentic
channel and be bootstrapped from some other basis for trust between A and
the CA.
This approach can signi¬cantly simplify revocation in PKIs. For notice
that there is no need to make any status checks on A™s public key before
encrypting a message for A. So there is no requirement for either Certi¬cate
Revocation Lists or an on-line certi¬cate status checking protocol. However,
the basic CBE approach of [146] does have a major drawback: the CA needs
to issue new values [sC ]PA (i) to every user in the scheme in every time pe-
riod. A granularity of one hour per time period is suggested in [146]; this
substantially adds to the computation and communication that take place
at the CA for a PKI with even a small user base. The basic CBE approach
can be regarded as e¬ectively trading simpli¬ed revocation for an increased
workload at the CA. A number of enhancements to the basic CBE approach
are also presented in [146]. These reduce the work that must be carried out
by the CA.
A security model for CBE is also developed in [146], and Gentry goes
on to show that the CBE scheme described above, but modi¬ed using the
Fujisaki“Okamoto technique [128], meets the de¬nition of security for the
scheme, provided that the BDH problem is hard. It is clear that similar ideas
to Gentry™s can be applied to produce certi¬cate-based signature schemes. A
scheme of this type was developed in [192].
Al-Riyami and Paterson [9] proposed another new model for supporting
the use of public-key cryptography which they named certi¬cateless public-
key cryptography (CL-PKC). Independently, Chen et al. [73] proposed sim-
ilar ideas in the context of signatures and group signatures. The key feature
of the model of [9] is that it eliminates the need for certi¬cates, hence the
(somewhat clumsy) adjective “certi¬cateless.”
Pairings are used to construct concrete CL-PKC schemes in [9]. As in
[146], an entity A™s private key is composed in two stages. Firstly, an identity-
dependent partial private key [s]QA = [s]H1 (IDA ) is received over a con¬den-
tial and authentic channel from a trusted authority (called a key generation
centre, KGC).18 Secondly, A combines the partial private key [s]QA with a
secret xA to produce his private key SA = [xA s]QA . The corresponding pub-
lic key is the pair XA , YA = [xA ]P, [xA ]Q0 , where Q0 = [s]P is a public
parameter of the system. The certi¬cateless encryption (CL-PKE) scheme of
[9] is obtained by adapting the IBE scheme of Boneh and Franklin [39] and
operates as follows in its basic form. To encrypt a message for A, an entity

This partial private key [s]H1 (IDA ) is identical to the private key in the IBE scheme
of Boneh and Franklin. It can also be regarded as a BLS signature by the TA on A™s
identity, and hence as a form of certi¬cation, though one that does not involve A™s public

¬rst checks that the equality
e(XA , Q0 ) = e(YA , P )
ˆ ˆ
holds, then selects t at random from Z— and sets:

C = [t]P, M • H2 (ˆ(QA , YA )t ) .
It is easy to see that, to decrypt C = U, V , A can use his private key
SA = [xA s]QA and compute M = V • H2 (ˆ(SA , U )).
Notice that, in this encryption scheme, A™s public key need not be sup-
ported by a certi¬cate. Instead, an entity A who wishes to rely on A™s public
key is assured that, if the KGC has done its job properly, only A who is in
possession of the correct partial private key and user-generated secret could
perform the decryption. Because there are no certi¬cates, Al-Riymai and
Paterson [9] were forced to consider a security model in which the adversary
is allowed to replace the public keys of entities at will. The security of the
scheme then rests on the attacker not knowing the partial private keys. Secu-
rity against the KGC is also modelled in [9], by considering an adversary who
knows the master secret s for the scheme, but who is trusted not to replace
the public keys of entities. The security of the encryption scheme in [9] rests
on the hardness of a new problem generalising the BDH problem:
Generalized Bilinear Di¬e“Hellman Problem (GBDH Problem):
Given P , P1 = [a]P , P2 = [b]P and P3 = [c]P in G1 with a, b and c selected
uniformly at random from Z— , output a pair

e(P, Q)abc
Q, ˆ
where Q ∈ G1 .
Al-Riyami and Paterson [9] also present certi¬cateless signature, key ex-
change and hierarchical schemes. These are obtained by adapting schemes of
[164, 312, 147]. CL-PKC supports the temporal re-ordering of public and
private key generation in the same way that ID-PKC does, thus it can be
used to support work¬‚ows of the type discussed in Section X.7.1.2.
CL-PKC combines elements from ID-PKC and traditional PKI. On the
one hand, the schemes are no longer identity-based: they involve the use of
A™s public key, which is no longer simply derived from A™s identity. On the
other hand, CL-PKC avoids the key escrow inherent in ID-PKC by having
user-speci¬c private information involved in the key generation process. CL-
PKC does not need certi¬cates to generate trust in public keys; instead, this
trust is produced in an implicit way. This would appear to make CL-PKC
ideal for systems where escrow is unacceptable but where the full weight of
PKI is untenable.
There is a close relationship between the ideas in [146] and [9]. It is
possible to convert CL-PKE scheme into a CBE scheme: if A™s identity in
the CL-PKE scheme is extended to include a time period along with the
public key, then the CL-PKE scheme e¬ectively becomes a CBE scheme. On

the other hand, if one omits certain ¬elds from the certi¬cates in a CBE
scheme, one obtains an encryption scheme that is functionally similar to a
CL-PKE scheme. Di¬erences do remain: in the strength and scope of the two
security models developed in [146] and [9], as well as in the technical details
of the schemes™ realizations.

X.7.3. Applications and Implementations. In this section we provide
brief notes on recent work putting pairings into practice or using pairings in
the broader context of information security.
A number of authors have examined how pairings can be put to use to en-
hance network security. Kempf et al. [197] described a lightweight protocol
for securing certain aspects of IPv6. The protocol adds identity-based signa-
tures to router and neighbour advertisements, with identities being based on
IP addresses. Khalili et al. [198] combined identity-based techniques with
threshold cryptography to build a key distribution mechanism suitable for
use in ad hoc networks.
Appenzeller and Lynn [10] proposed using the NIKDS of Sakai et al. [284]
to produce identity-based keys for securing IP packets between hosts. Their
approach adds security while avoiding the introduction of state at the network
layer, and so provides an attractive alternative to IPSec. However, it can
only be used by pairs of entities who share a common TA. On the other hand,
Smetters and Durfee [315] proposed a system in which each DNS domain runs
its own IBE scheme and is responsible for distributing private keys to each
of its hosts (or e-mail users). Inter-domain IPSec key exchanges and e-mail
security are enabled by extending DNS to give a mechanism for distributing
IBE scheme parameters. In [315], a protocol of [70] is used to provide an
alternative to IKE (IPSec Key Exchange) for inter-domain exchanges while
the NIKDS of Sakai et al. [284] can be used to set up IKE in pre-shared key
mode for intra-domain communications. The protocol resulting in the latter
case in [315] is similar to a protocol proven secure in [47].
Dalton [94] described the particular computing and trust challenges faced
in the UK™s National Health Service and studied the applicability of identity-
based techniques in that environment.
Waters et al. [345] modi¬ed the IBE scheme of Boneh and Franklin
[39] to provide a solution to the problem of searching through an encrypted,
sensitive audit log. In the scheme of [345], a machine attaches a set of
IBE-encrypted tags to each entry in its log, each tag corresponding to a
single keyword W . The “identity” used in the encryption to produce a tag
is the string W , while the plaintext encrypted is the symmetric key that
was used to encrypt the entry in the log (plus some redundancy allowing
the plaintext to be recognized). The TA for the IBE system acts as an
audit escrow agent: when an entity requests the capability to obtain log
entries containing a particular keyword, the TA may provide the private key
[s]H1 (W ) matching that keyword. Now the testing entity can simply try to

decrypt each tag for the log entry. When the correct tag is decrypted, a key
allowing the entry to be decrypted results. A more theoretical and formal
approach to the related problem of searchable public-key encryption (SPKE)
can be found in [37]. One of the three constructions for an SPKE scheme
in [37] is based on pairings, speci¬cally, it is again an adaptation of the IBE
scheme of Boneh and Franklin.
Currently, we know of at least one company, Voltage Security, that is ac-
tively developing and marketing identity-based security systems. Their prod-
ucts include secure e-mail and ¬le encryption applications. An early identity-
based secure e-mail demonstrator, implementing Boneh and Franklin™s IBE
scheme, is still available from
at the time of writing. Routines for Weil and Tate pairing computations are
built into a number of software libraries, including Magma.

X.8. Concluding Remarks
We have seen in this chapter how pairings have been used to build some
entirely new cryptographic schemes and to ¬nd more e¬cient instantiations
of existing primitives. Although we have not been exhaustive in our coverage,
we trust that the breathless pace of research in the area is apparent. What
might the future hold for this subject, and what are the most important
questions yet to be tackled?
The techniques and ideas used in pairing-based cryptography are very
new, so it is hard to envisage where they will be taken next. The applications
in topics like intrusion-resilient encryption and cryptographic work¬‚ows are
so surprising (at least to the author) that accurately predicting an answer to
the ¬rst question seems fraught. One might expect the rate of publication of
new pairing-based schemes to slow a little and a period of consolidation to
occur. On a more theoretical note, the subject is rife with random oracles and
ine¬cient reductions. Removing these whilst keeping the full strength of the
security models and obtaining practical schemes should keep cryptographers
We suggest that much more work above and below the purely crypto-
graphic level is needed.
As Section X.7.3 illustrates, techniques from pairing-based cryptography
are beginning to have an e¬ect on other domains of information security.
Attempts at commercialization will provide a true test of the applicability
of what on paper seem like very neat ideas. Identity-based cryptography is
certainly interesting, but it still has much to prove when measured against
traditional PKIs. One topic we have not addressed here is that of intellectual
property and patents. This may become a major factor in the take-up of the
technology, in the same way that it was for elliptic curve cryptography in the
last decade and public-key cryptography before that.

Below the cryptographic level, more work on the fundamental question of
understanding the hardness of the BDH problem (and the associated deci-
sional problem) seems essential. While the relationships to the CDH problem
and other problems in related groups are well understood, this is of course
not the whole story. Pairings also give new relevance to “old” problems,
for example, evaluating the performance of discrete logarithm algorithms in
¬elds of small characteristic for concrete parameters. One might also worry
about relying too much on the extremely narrow class of supersingular curves
for constructing pairings. This is akin to the days before point counting for
curves of cryptographic sizes became routine, when CM curves were suggested
as a way of proceeding. It is interesting to note that recent constructions for
curves with prescribed embedding degrees (as described in Chapter IX) also
rely on CM methods, while it is known that the embedding degree of a random
curve of a particular size will be very high. The challenge to computational
number theorists is evident.

[ECC] I.F. Blake, G. Seroussi and N.P. Smart. Elliptic Curves in Cryptography. Cambridge
University Press, 1999.
[EP] IACR e-print archive. Available from http://eprint.iacr.org/.
[A-1] L. Adleman and M.-D. Huang, editors. ANTS-1: Algorithmic Number Theory.
Springer-Verlag, LNCS 877, 1994.
[A-2] H. Cohen, editor. ANTS-2: Algorithmic Number Theory. Springer-Verlag, LNCS
1122, 1996.
[A-3] J.P. Buhler, editor. ANTS-3: Algorithmic Number Theory. Springer-Verlag, LNCS
1423, 1998.
[A-4] W. Bosma, editor. ANTS-4: Algorithmic Number Theory. Springer-Verlag, LNCS
1838, 2000.
[A-5] C. Fieker and D.R. Kohel, editors. ANTS-5: Algorithmic Number Theory. Springer-
Verlag, LNCS 2369, 2002.
[A-6] D. Buell, editor. ANTS-6: Algorithmic Number Theory. Springer-Verlag, LNCS
3076, 2004.
[A98] K. Ohta and D. Pei, editors. Advances in Cryptology “ ASIACRYPT ™98. Springer-
Verlag, LNCS 1514, 1998.
[A99] K.Y. Lam, E. Okamoto and C. Xing, editors. Advances in Cryptology “ ASI-
ACRYPT ™99. Springer-Verlag, LNCS 1716, 1999.
[A00] T. Okamoto, editor. Advances in Cryptology “ ASIACRYPT 2000. Springer-Verlag,
LNCS 1976, 2000.
[A01] C. Boyd, editor. Advances in Cryptology “ ASIACRYPT 2001. Springer-Verlag,
LNCS 2248, 2001.
[A02] Y. Zheng, editor. Advances in Cryptology “ ASIACRYPT 2002. Springer-Verlag,
LNCS 2501, 2002.
[A03] C.S. Laih, editor. Advances in Cryptology “ ASIACRYPT 2003. Springer-Verlag,
LNCS 2894, 2003.
[C84] G.R. Blakley and D. Chaum, editors. Advances in Cryptology “ CRYPTO ™84.
Springer-Verlag, LNCS 196, 1985.
[C89] G. Brassard, editor. Advances in Cryptology “ CRYPTO ™89. Springer-Verlag,
LNCS 435, 1990.
[C91] J. Feigenbaum, editor. Advances in Cryptology “ CRYPTO ™91. Springer-Verlag,
LNCS 576, 1992.
[C92] E.F. Brickell, editor. Advances in Cryptology “ CRYPTO ™92. Springer-Verlag,
LNCS 740, 1993.
[C93] D. Stinson, editor. Advances in Cryptology “ CRYPTO ™93. Springer-Verlag, LNCS
773, 1993.
[C96] N. Koblitz, editor. Advances in Cryptology “ CRYPTO ™96. Springer-Verlag, LNCS
1109, 1996.
[C97] B.S. Kaliski Jr., editor. Advances in Cryptology “ CRYPTO ™97. Springer-Verlag,
LNCS 1294, 1997.


[C98] H. Krawczyk, editor. Advances in Cryptology “ CRYPTO ™98. Springer-Verlag,
LNCS 1462, 1998.
[C99] M. Wiener, editor. Advances in Cryptology “ CRYPTO ™99. Springer-Verlag, LNCS
1666, 1999.
[C00] M. Bellare, editor. Advances in Cryptology “ CRYPTO 2000. Springer-Verlag,
LNCS 1880, 2000.
[C01] J. Kilian, editor. Advances in Cryptology “ CRYPTO 2001. Springer-Verlag, LNCS
2139, 2001.
[C02] M. Yung, editor. Advances in Cryptology “ CRYPTO 2002. Springer-Verlag, LNCS
2442, 2002.
[C03] D. Boneh, editor. Advances in Cryptology “ CRYPTO 2003. Springer-Verlag, LNCS
2729, 2003.
[CH99] C.K. Ko¸ and C. Paar, editors. Cryptographic Hardware and Embedded Systems “
¸ c
CHES ™99. Springer-Verlag, LNCS 1717, 1999.
[CH00] C.K. Ko¸ and C. Paar, editors. Cryptographic Hardware and Embedded Systems “
¸ c
CHES 2000. Springer-Verlag, LNCS 1965, 2000.
[CH01] C.K. Ko¸, D. Naccache and C. Paar, editors. Cryptographic Hardware and Embed-
¸ c
ded Systems “ CHES 2001. Springer-Verlag, LNCS 2162, 2001.
[CH02] B.S. Kaliski Jr., C.K. Ko¸ and C. Paar, editors. Cryptographic Hardware and Em-
¸ c
bedded Systems “ CHES 2002. Springer-Verlag, LNCS 2523, 2003.
[CH03] C.D. Walter, C.K. Ko¸ and C. Paar, editors. Cryptographic Hardware and Embed-
¸ c
ded Systems “ CHES 2003. Springer-Verlag, LNCS 2779, 2003.
[E90] I.B. Damg˚ ard, editor. Advances in Cryptology “ EUROCRYPT ™90. Springer-
Verlag, LNCS 473, 1990.
[E94] A. De Santis, editor. Advances in Cryptology “ EUROCRYPT ™94. Springer-Verlag,
LNCS 950, 1994.
[E97] W. Fumy, editor. Advances in Cryptology “ EUROCRYPT ™97. Springer-Verlag,
LNCS 1233, 1997.
[E00] B. Preneel, editor. Advances in Cryptology “ EUROCRYPT 2000. Springer-Verlag,
LNCS 1807, 2000.
[E01] B. P¬tzmann, editor. Advances in Cryptology “ EUROCRYPT 2001. Springer-
Verlag, LNCS 2045, 2001.
[E02] L. Knudsen, editor. Advances in Cryptology “ EUROCRYPT 2002. Springer-Verlag,
LNCS 2332, 2002.
[E03] E. Biham, editor. Advances in Cryptology “ EUROCRYPT 2003. Springer-Verlag,
LNCS 2656, 2003.
[E04] C. Cachin and J. Camenisch, editors. Advances in Cryptology “ EURO-
CRYPT 2004. Springer-Verlag, LNCS 3027, 2003.
[P01] K. Kim, editor. Public Key Cryptography “ PKC 2001. Springer-Verlag, LNCS 1992,
[P02] D. Naccache and P. Paillier, editors. Public Key Cryptography “ PKC 2002.
Springer-Verlag, LNCS 2274, 2002.
[P03] Y.G. Desmedt, editor. Public Key Cryptography “ PKC 2003. Springer-Verlag,
LNCS 2567, 2003.
[P04] F. Bao, editor. Public Key Cryptography “ PKC 2004. Springer-Verlag, LNCS 2947,
[ANSI X9.62] ANSI X9.62. Public Key Cryptography for the Financial Services Industry:
The Elliptic Curve Digital Signature Algorithm (ECDSA). American National Stan-
dards Institute, 1999.

[ANSI X9.63] ANSI X9.63. Public Key Cryptography for the Financial Services Industry:
Elliptic Curve Key Agreement and Transport Protocols. American National Stan-
dards Institute, 2001. Draft.
[EU 1999] EU Directive 1999/93/EC of the European Parliament and of the Council. On
a Community Framework for Electronic Signatures, December 1999.
[FIPS 140.1] FIPS PUB 140-1. Security requirements for cryptographic modules. National
Institute for Standards and Technology, 1994.
[FIPS 180.1] FIPS PUB 180-1. Secure Hash Standard. National Institute for Standards
and Technology, 1995.
[FIPS 180.2] FIPS PUB 180-2. Secure Hash Standard. National Institute for Standards
and Technology, 2001.
[FIPS 186] FIPS PUB 186. Digital Signature Standard (DSS). National Institute for Stan-
dards and Technology, 1994.
[FIPS 186.2] FIPS PUB 186-2. Digital Signature Standard (DSS). National Institute for
Standards and Technology, 2000.
[IBM CoPro] IBM Corporation. IBM PCI Cryptographic Coprocessor“General Informa-
tion Manual, 6th ed., 2002.
[IEEE 1363] IEEE 1363. Standard Speci¬cations for Public Key Cryptography. IEEE, 2000.
[ISO 15946-2] ISO X9.62. International Standard 15946-2: Information Technology ” Se-
curity Techniques ” Cryptographic techniques based on elliptic curves ” Part 2:
Digital Signatures. International Standards Organization, 2000.
[NESSIE] NESSIE. Security Evaluation Report. NESSIE, 2002.
[RFC 2412] IETF. The Oakley Key Determination Protocol, 1998.
[RFC 3278] IETF. The Use of Elliptic Curve Cryptography in the Cryptographic Message
Syntax, 2001.
[SECG] SEC 1. Elliptic Curve Cryptography. Standards for E¬cient Cryptography Group,
[1] M. Abdalla, M. Bellare and P. Rogaway. DHAES: An encryption scheme based
on the Di¬e-Hellman problem. Submission to P1363a: Standard Speci¬cations for
Public-Key Cryptography, Additional Techniques, 2000.
[2] L.M. Adleman. The function ¬eld sieve. In [A-1], 108“121.
[3] L.M. Adleman and M.-D. Huang. Function ¬eld sieve method for discrete loga-
rithms over ¬nite ¬elds. Information and Computation, 151, 5“16, 1999.
[4] L.M. Adleman, J. DeMarrais and M.-D. Huang. A subexponential algorithm for
discrete logarithms over the rational subgroup of the jacobians of large genus hy-
perelliptic curves over ¬nite ¬elds. In [A-1], 28“40.
[5] D. Agrawal, B. Archambeault, J.R. Rao and P. Rohatgi. The EM side-channel(s).
In [CH02], 29“45.
[6] T. Akishita and T. Takagi. Zero-value point attacks on elliptic curve cryptosys-
tem. In C. Boyd and W. Mao, editors, Information Security, LNCS 2851, 218“233.
Springer-Verlag, 2003.
[7] M.-L. Akkar and C. Giraud. An implementation of DES and AES secure against
some attacks. In [CH01], 309“318.
[8] S.S. Al-Riyami and K.G. Paterson. Authenticated three party key agreement pro-
tocols from pairings. In K.G. Paterson, editor, Cryptography and Coding, LNCS
2898, 332“359. Springer-Verlag, 2003.
[9] S.S. Al-Riyami and K.G. Paterson. Certi¬cateless public key cryptography. In
[A03], 452“473.
[10] G. Appenzeller and B. Lynn. Minimal-overhead IP security using identity-based
encryption. Preprint, 2003.

[11] A.O.L. Atkin. The number of points on an elliptic curve modulo a prime. Series of
emails to the NMBRTHRY mailing list, 1992.
[12] R. Balasubramanian and N. Koblitz. The improbability that an elliptic curve has
sub-exponential discrete log problem under the Menezes“Okamoto“Vanstone algo-
rithm. J. Cryptology, 11, 141“145, 1998.
[13] D. Balfanz, G. Durfee, N. Shankar, D. Smetters, J. Staddon and H.-C. Wong.
Secret handshakes from pairing-based key agreements. In Proc. IEEE Symposium
on Security and Privacy, 180“196. IEEE, 2003.
[14] R. Barua, R. Dutta and P. Sarkar. Extending Joux™s protocol to multi party key
agreement. In T. Johansson and S. Maitra, editors, Progress in Cryptology “ IN-
DOCRYPT 2003, LNCS 2551, 205“217. Springer-Verlag, 2003.
[15] P. Barreto. The pairing-based crypto lounge. http://planeta.terra.com.
[16] P.S.L.M. Barreto, H.Y. Kim, B. Lynn and M. Scott. E¬cient algorithms for pairing-
based cryptosystems. In [C02], 354“368.
[17] P.S.L.M. Barreto, B. Lynn and M. Scott. Constructing elliptic curves with pre-
scribed embedding degrees. In S. Cimato, C. Galdi and G. Persiano, editors, Se-
curity in Communication Networks (SCN 2002), LNCS 2576, 257“267. Springer-
Verlag, 2002.
[18] P.S.L.M. Barreto, B. Lynn and M. Scott. On the selection of pairing-friendly groups.
In M. Matsui and R. Zuccherato, editors, Selected Areas in Cryptography “ SAC
2003, LNCS 3006, 17“25. Springer-Verlag, 2004.
[19] M. Bellare, A. Desai, E. Jokipii and P. Rogaway. A concrete security treatment of
symmetric encryption. In Proc. of the 38th Symposium on Foundations of Computer
Science, IEEE, 1997.
[20] M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. Relations among notions of
security for public-key encryption schemes. In [C98], 26“45.
[21] M. Bellare, S. Goldwasser and D. Micciancio. “Pseudo-random” number generation
within cryptographic algorithms: The DSS case. In [E97], 277“291.
[22] M. Bellare, R. Canetti and H. Krawczyk. A modular approach to the design and
analysis of authentication and key exchange protocols. In Proc. of the 30th Annual
Symposium on the Theory of Computing, 419“428. ACM, 1998.
[23] M. Bellare and A. Palacio. Protecting against key exposure: strongly key-insulated
encryption with optimal threshold. See [EP], # 2002/064, 2002.
[24] M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for design-
ing e¬cient protocols. In Proc. of the First ACM Conference on Computer and
Communications Security, 62“73. ACM, 1993.
[25] M. Bellare and P. Rogaway. Entity authentication and key distribution. In [C93],
[26] I. Biehl, B. Meyer and V. M¨ller. Di¬erential fault attacks on elliptic curve cryp-
tosystems. In [C00], 131“146.
[27] O. Billet and M. Joye. The Jacobi model of an elliptic curve and side-channel
analysis. In M. Fossorier, T. Høholdt and A. Poli, editors, Applied Algebra, Algebraic
Algorithms and Error-Correcting Codes, LNCS 2643, 34“42. Springer-Verlag, 2003.
[28] S. Blake-Wilson, D. Johnson and A.J. Menezes. Key agreement protocols and their
security analysis. In Cryptography and Coding, LNCS 1355, 30“45. Springer-Verlag,
[29] S. Blake-Wilson and A.J. Menezes. Security proofs for entity authentication and au-
thenticated key transport protocols employing asymmetric techniques. In B. Chris-
tianson, B. Crispo, T. Lomas and M. Roe, editors, Security Protocols, LNCS 1361,
137“158. Springer-Verlag, 1997.

[30] D. Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA
encryption standard PKCS #1. In [C98], 1“12.
[31] D. Bleichenbacher. On the generation of DSS one-time keys. Preprint, 2001.
[32] A. Boldyreva. E¬cient threshold signature, multisignature and blind signature
schemes based on the gap-Di¬e-Hellman-group signature scheme. In [P03], 31“
[33] A. Boldyreva, A. Palacio and B. Warinschi. Secure proxy signature schemes for
delegation of signing rights. See [EP], # 2003/096, 2003.
[34] D. Boneh. The decision Di¬e-Hellman problem. In [A-3], 48“63.
[35] D. Boneh and X. Boyen. Short signatures without random oracles. In [E04], 56“73.
[36] D. Boneh and X. Boyen. E¬cient selective-ID secure identity-based encryption
without random oracles. In [E04], 223“238.
[37] D. Boneh, G. Di Crescenzo, R. Ostrovsky and G. Persiano. Public key encryption
with keyword search. In [E04], 506“522.
[38] D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. In
[C01], 213“229.
[39] D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. SIAM
J. Comp., 32, 586“615, 2003.
[40] D. Boneh, C. Gentry, B. Lynn and H. Shacham. Aggregate and veri¬ably encrypted
signatures from bilinear maps. In [E03], 416“432.
[41] D. Boneh, A. Joux and P. Nguyen. Why textbook ElGamal and RSA encryption
are insecure. In [A00], 30“43.
[42] D. Boneh, B. Lynn and H. Shacham. Short signatures from the Weil pairing. In
[A01], 514“532.
[43] D. Boneh, B. Lynn and H. Shacham. Short signatures from the Weil
pairing. Technical report, 2003. Revised version of [42], available from
[44] D. Boneh, I. Mironov and V. Shoup. Provably secure signature scheme from bilinear
mapping. In M. Joye, editor, Topics in Cryptology “ CT-RSA 2003, LNCS 2612,
98“110. Springer-Verlag, 2003.
[45] I. Bouw, C. Diem and J. Scholten. Ordinary elliptic curves of high rank over Fp (x)
with constant j-invariant. Manuscripta Mathematica, To appear.
[46] W. Bosma, J. Cannon and C. Playoust. The Magma algebra system I: The user
language. J. Symbolic Comp., 24, 3/4, 235“265, 1997.
[47] C. Boyd, W. Mao and K.G. Paterson. Deniable authenticated key establishment
for Internet protocols. In Security Protocols, LNCS. Springer-Verlag, To appear.
[48] X. Boyen. Multipurpose identity-based signcryption: A swiss army knife for
identity-based cryptography. In [C03], 382“398.
[49] F. Brezing and A. Weng. Elliptic curves suitable for pairing based cryptography.
See [EP], # 2003/143, 2003.
[50] E. Brier, I. D´ch`ne and M. Joye. Uni¬ed addition formul¦ for elliptic curve cryp-
tosystems. In N. Nedjah and L. de Macedo Mourelle, editors, Embedded Crypto-
graphic Hardware: Methodologies and Architectures. Nova Science Publishers, 2004.
[51] E. Brier and M. Joye. Weierstraß elliptic curves and side-channel attacks. In [P02],
[52] D.R.L. Brown. Generic groups, collision resistance and ECDSA. See [EP], #
2002/026, 2002.
[53] M. Burmester and Y. Desmedt. A secure and e¬cient conference key distribution
system. In [E94], 267“275.

[54] R. Canetti, O. Goldreich and S. Halevi. The random oracle model, revisited. In
Proc. of the 30th Annual ACM Symposium on the Theory of Computing, 209“218.
ACM, 1998.
[55] R. Canetti, S. Halevi and J. Katz. A forward-secure public-key encryption scheme.
In [E03], 255“271.
[56] R. Canetti, S. Halevi and J. Katz. Chosen-ciphertext security from identity-based
encryption. See [E04], #, 2003.
[57] R. Canetti and H. Krawczyk. Analysis of key-exchange protocols and their use for
building secure channels. In [E01], 453“474.
[58] R. Canetti, H. Krawczyk and J.B. Nielsen. Relaxing chosen-ciphertext security. In
[C03], 565“582.
[59] D.G. Cantor. Computing in the Jacobian of an hyperelliptic curve. Math. Comp.,
48, 95“101, 1987.
[60] R. Carls. A generalized arithmetic geometric mean (GAGM) sequence. Preprint,
[61] J. Cathalo, F. Koeune and J.-J. Quisquater. A new type of timing attack: Appli-
cation to GPS. In [CH03], 291“303.
[62] J.C. Cha and J.H. Cheon. An identity-based signature from gap Di¬e“Hellman
groups. In [P03], 18“30.
[63] L.S. Charlap and R. Coley. An elementary introduction to elliptic curves ii. Institute
for Defense Analysis, CCR Expository Report 34, 1990.
[64] S. Chari, C.S. Jutla, J.R. Rao and P. Rohatgi. Towards sound approaches to coun-
teract power-analysis attacks. In [C99], 398“412.
[65] D. Chaum. Security without identi¬cation: Transaction systems to make Big
Brother obsolete. Comm. ACM, 28, 1030“1044, 1985.
[66] D. Chaum. Zero-knowledge undeniable signatures. In [E90], 458“464.
[67] D. Chaum and H. van Antwerpen. Undeniable signatures. In [C89], 212“216.
[68] L. Chen, K. Harrison, A. Moss, D. Soldera and N.P. Smart. Certi¬cation of public
keys within an identity based system. In A.H. Chan and V.D. Gligor, editors,
Information Security, LNCS 2433, 322“333. Springer-Verlag, 2002.
[69] L. Chen, K. Harrison, D. Soldera and N.P. Smart. Applications of multiple trust
authorities in pairing based cryptosystems. In G.I. Davida, Y. Frankel and O. Rees,
editors, Infrastructure Security, International Conference, InfraSec, LNCS 2437,
260“275. Springer-Verlag, 2002.
[70] L. Chen and C. Kudla. Identity based authenticated key agreement protocols from
pairings. See [EP], # 2002/184, 2002.
[71] L. Chen and C. Kudla. Identity based authenticated key agreement protocols from
pairings. In IEEE Computer Security Foundations Workshop, 219“233. IEEE Com-
puter Society Press, 2003.
[72] L. Chen and J. Malone-Lee. Improved identity-based signcryption. Preprint, 2004.
[73] X. Chen, F. Zhang and K. Kim. A new ID-based group signature scheme from
bilinear pairings. See [EP], # 2003/116, 2003.
[74] Z. Chen. Security analysis of Nalla-Reddy™s ID-based tripartite authenticated key
agreement protocols. See [EP], # 2003/103, 2003.
[75] J.H. Cheon. A universal forgery of Hess™s second ID-based signature against the
known-message attack. See [EP], # 2002/028, 2002.
[76] B. Chevallier-Mames, M. Ciet and M. Joye. Low-cost solutions for preventing simple
side-channel analysis: Side-channel atomicity. IEEE Trans. Computers, 53, 760“
768, 2004.

[77] D.V. Chudnovsky and G.V. Chudnovsky. Sequences of numbers generated by ad-
dition in formal groups and new primality and factorization tests. Adv. Applied
Math., 7, 385“434, 1987.
[78] M. Ciet and M. Joye. Elliptic curve cryptosystems in the presence of permanent
and transient faults. Designs, Codes and Cryptography, To appear.
[79] M. Ciet, J.-J. Quisquater and F. Sica. Preventing di¬erential analysis in GLV elliptic
curve scalar multiplication. In [CH02], 540“550.
[80] M. Ciet, J.-J. Quisquater and F. Sica. A secure family of composite ¬nite ¬elds
suitable for fast implementation of elliptic curve cryptography. In C. Pandu Rangan
and C. Ding, editors, Progress in Cryptology “ INDOCRYPT 2001, LNCS 2247,
108“116. Springer-Verlag, 2001.
[81] C. Clavier, J.-S. Coron and N. Dabbous. Di¬erential power analysis in the presence
of hardware countermeasures. In [CH00], 252“263.
[82] C. Clavier and M. Joye. Universal exponentiation algorithm: A ¬rst step towards
provable SPA-resistance. In [CH01], 300“308.
[83] C. Cocks. An identity based encryption scheme based on quadratic residues. In
B. Honary, editor, Cryptography and Coding, LNCS 2260, 360“363. Springer-Verlag,
[84] C. Cocks and R.G.E. Pinch. ID-based cryptosystems based on the Weil pairing.
Unpublished manuscript, 2001.
[85] H. Cohen, A. Miyaji and T. Ono. E¬cient elliptic curve exponentiation using mixed
coordinates. In [A98], 51“65.
[86] D. Coppersmith. Fast evaluation of logarithms in ¬elds of characteristic 2. IEEE
Trans. Inf. Theory, 30, 587“594, 1984.
[87] J.-S. Coron. Resistance against di¬erential power analysis for elliptic curve cryp-
tosystems. In [CH99], 292“302.
[88] J.-S. Coron and L. Goubin. On Boolean and arithmetic masking against di¬erential
power analysis. In [CH00], 231“237.
[89] J.-S. Coron and D. Naccache. Boneh et al.™s k-element aggregate extraction as-
sumption is equivalent to the Di¬e-Hellman assumption. In [A03], 392“397.
[90] J.-M. Couveignes. Quelques calculs en th´orie des nombres. PhD thesis, Universit´
e e
de Bordeaux, 1994.
[91] J.-M. Couveignes. Computing l-isogenies with the p-torsion. In [A-2], 59“65.
[92] J.-M. Couveignes. Algebraic groups and discrete logarithms. In Public Key Cryp-
tography and Computational Number Theory, 17“27. Walter de Gruyter, 2001.
[93] R. Cramer and V. Shoup. Design and analysis of practical public-key encryption
schemes secure against adaptive chosen ciphertext attack. SIAM Journal on Com-
puting, 33(1), 167“226, 2004.
[94] C.R. Dalton. The NHS as a proving ground for cryptosystems. Information Security
Technical Report, 8(3), 73“88, 2003.
[95] B. den Boer, K. Lemke and G. Wicke. A DPA attack against the modular reduction
within a CRT implementation of RSA. In [CH02], 228“234.
[96] J. Denef and F. Vercauteren. An extension of Kedlaya™s algorithm to Artin-Schreier
curves in characteristic 2. In [A-5], 308“323.
[97] J. Denef and F. Vercauteren. An extension of Kedlaya™s algorithm to hyperelliptic
curves in characteristic 2. J. Cryptology, To appear.
[98] J. Denef and F. Vercauteren. Computing zeta functions of Cab curves using Monsky-
Washnitzer cohomology. Preprint, 2003.
[99] A.W. Dent. An evaluation of EPOC-2. NESSIE, Public report, 2001.
[100] A.W. Dent. Adapting the weaknesses of the random oracle model to the generic
group model. In [A02], 100“109.

[101] M. Deuring. Die Typen der Multiplikatorenringe elliptischer Funktionenk¨rper. o
Abh. Math. Sem. Univ. Hamburg, 14, 197“272, 1941.
[102] E. De Win, S. Mister, B. Preneel and M. Wiener. On the performance of signature
schemes based on elliptic curves. In [A-3], 252“266.
[103] C. Diem. A study on theoretical and practical aspects of Weil-restrictions of vari-
eties. PhD thesis, Universtit¨t-Gesamthochschule Essen, 2001.
[104] C. Diem. The GHS-attack in odd characteristic. J. Ramanujan Math. Soc., 18,
[105] C. Diem and N. Naumann. On the structure of Weil restrictions of abelian varieties.
J. Ramanujan Math. Soc., 18, 2003.
[106] C. Diem and J. Scholten. Cover attacks “ a report for the AREHCC project.
Preprint, 2003.
[107] Y. Dodis, M. Franklin, J. Katz, A. Miyaji and M. Yung. Intrusion-resilient public-
key encryption. In M. Joye, editor, Topics in Cryptology “ CT-RSA 2003, LNCS
2612, 19“32. Springer-Verlag, 2003.
[108] R. Dupont and A. Enge. Practical non-interactive key distribution based on pair-
ings. Discrete Applied Mathematics, To appear.
[109] R. Dupont, A. Enge and F. Morain. Building curves with arbitrary small MOV
degree over ¬nite prime ¬elds. See [EP], # 2002/094, 2002.
[110] I.M. Duursma. Class numbers for some hyperelliptic curves. In R. Pellikaan, M. Per-
ret and S.G. Vladut, editors, Arithmetic, Geometry and Coding Theory, 45“52.
Walter de Gruyter, 1996.
[111] I.M. Duursma, P. Gaudry and F. Morain. Speeding up the discrete log computation
on curves with automorphisms. In [A99], 103“121.
[112] I.M. Duursma and H.-S. Lee. Tate pairing implementation for hyperelliptic curves.
In [A03], 111“222.
[113] B. Dwork. On the rationality of the zeta function of an algebraic variety. Amer. J.
Math., 82, 631“648, 1960.
[114] K. Eisentr¨ger, K. Lauter and P.L. Montgomery. Fast elliptic curve arithmetic and
improved Weil pairing evaluation. In M. Joye, editor, Topics in Cryptology “ CT-
RSA 2003, LNCS 2612, 343“354. Springer-Verlag, 2003.
[115] N. Elkies. Elliptic and modular curves over ¬nite ¬elds and related computational
issues. In Computational Perspectives on Number Theory, 21“76, 1998.
[116] A. Enge. Computing discrete logarithms in high-genus hyperelliptic Jacobians in
provably subexponential time. Math. Comp., 71, 729“742, 2002.
[117] A. Enge and P. Gaudry. A general framework for subexponential discrete logarithm
algorithms. Acta Arith., 102, 83“103, 2002.
[118] A. Enge and A. Stein. Smooth ideals in hyperelliptic function ¬elds. Math. Comp.,
71, 1219“1230, 2002.
[119] P. Fahn and P. Pearson. IPA: A new class of power attacks. In [CH99], 173“186.
[120] W. Fischer, C. Giraud, E.W. Knudsen and J.-P. Seifert. Parallel scalar multiplica-
tion on general elliptic curves over Fp hedged against non-di¬erential side-channel
attacks. See [EP], # 2002/007, 2002.
[121] R. Flassenberg and S. Paulus. Sieving in function ¬elds. Experiment. Math., 8,
339“349, 1999.
[122] P.-A. Fouque and F. Valette. The doubling attack “ Why upwards is better than
downwards. In [CH03], 269“280.
[123] M. Fouquet, P. Gaudry and R. Harley. On Satoh™s algorithm and its implementa-
tion. J. Ramanujan Math. Soc., 15, 281“318, 2000.
[124] G. Frey. How to disguise an elliptic curve. Talk at ECC™ 98, Waterloo, 1998.

[125] G. Frey, M. M¨ller and H.-G. R¨ck. The Tate pairing and the discrete logarithm
u u
applied to elliptic curve cryptosystems. IEEE Trans. Inf. Theory, 45, 1717“1719,
[126] G. Frey and H.-G. R¨ck. A remark concerning m-divisibility and the discrete log-
arithm problem in the divisor class group of curves. Math. Comp., 62, 865“874,
[127] G. Frey. Applications of arithmetical geometry to cryptographic constructions. In
D. Jungnickel and H. Niederreiter, editors, Finite Fields and Applications “ 5,
128“161. Springer, 2001.
[128] E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric en-
cryption schemes. In [C99], 537“554.
[129] S.D. Galbraith. Constructing isogenies between elliptic curves over ¬nite ¬elds.
LMS J. Comput. and Math., 2, 118“138, 1999.
[130] S.D. Galbraith. Supersingular curves in cryptography. In [A01], 495“513.
[131] S.D. Galbraith. Weil descent of Jacobians. In D. Augot and C. Carlet, editors,
WCC2001 International workshop on coding and cryptography, Electron. Notes Dis-
crete Math. 6. Elsevier, 2001.
[132] S.D. Galbraith. Limitations of constructive Weil descent. In Public Key Cryptog-
raphy and Computational Number Theory, 59“70. Walter de Gruyter, 2001.
[133] S.D. Galbraith, K. Harrison and D. Soldera. Implementing the Tate pairing. In
[A-5], 324“337.
[134] S.D. Galbraith, F. Hess and N.P. Smart. Extending the GHS Weil descent attack.
In [E02], 29“44.
[135] S.D. Galbraith, H.J. Hopkins and I.E. Shparlinski. Secure Bilinear Di¬e-Hellman
bits. In J. Pieprzyk H. Wang and V. Varadharajan, editors, Information Security
and Privacy “ ACISP 2004, LNCS 3108, 370“378. Springer-Verlag, 2004.
[136] S.D. Galbraith and J. McKee. The probability that the number of points on an
elliptic curve over a ¬nite ¬eld is prime. J. London Math. Soc., 62, 671“684, 2000.
[137] S.D. Galbraith and N.P. Smart. A cryptographic application of Weil descent. In
M. Walker, editor, Cryptography and Coding, LNCS 1746, 191“200. Springer-Verlag,
[138] R. Gallant, R. Lambert and S. Vanstone. Improving the parallelized Pollard lambda
search on binary anomalous curves. Math. Comp., 69, 1699“1705, 2000.
[139] K. Gandol¬, C. Mourtel and F. Olivier. Electromagnetic analysis: Concrete results.
In [CH01], 251“261.
[140] T. Garefalakis. The generalised Weil pairing and the discrete logarithm problem
on elliptic curves. In S. Rajsbaum, editor, LATIN 2002: Theoretical Informatics,
LNCS 2286, 118“130. Springer-Verlag, 2002.
[141] J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge Univer-
sity Press, 1999.
[142] P. Gaudry. An algorithm for solving the discrete log problem on hyperelliptic curves.
In [E00], 19“34.
[143] P. Gaudry. A comparison and a combination of SST and AGM algorithms for
counting points of elliptic curves in characteristic 2. In [A02], 311“327.
[144] P. Gaudry and N. G¨rel. An extension of Kedlaya™s point-counting algorithm to
superelliptic curves. In [A01], 480“494.
[145] P. Gaudry, F. Hess and N.P. Smart. Constructive and destructive facets of Weil
descent on elliptic curves. J. Cryptology, 15, 19“46, 2002.
[146] C. Gentry. Certi¬cate-based encryption and the certi¬cate revocation problem. In
[E03], 272“293.

[147] C. Gentry and A. Silverberg. Heirarchical ID-based cryptography. In [A02], 548“
[148] R. Gerkmann. The p-adic cohomology of varieties over ¬nite ¬elds and applications
to the computation of zeta functions. PhD thesis, Universit¨t Duisberg-Essen, 2003.
[149] S. Goldwasser and S. Micali. Probabilistic encryption. J. Comp. Syst. Sci., 28,
270“299, 1984.
[150] S. Goldwasser, S. Micali and R. Rivest. A digital signature scheme secure against
adaptive chosen-message attacks. SIAM J. Comp., 17, 281“308, 1988.
[151] L. Goubin. A re¬ned power-analysis attack on elliptic curve cryptosystems. In
[P03], 199“210.
[152] L. Goubin and J. Patarin. DES and di¬erential power analysis “ The duplication
method. In [CH99], 158“172.
[153] L. Granboulan. RSA hybrid encryption schemes. Available from http://www.di.
ens.fr/˜granboul/recherche/publications/abs-2001-RSAenc.html, 2001.
[154] R. Granger. Estimates for discrete logarithm computations in ¬nite ¬elds. In K.G.
Paterson, editor, Cryptography and Coding, LNCS 2898, 190“206. Springer-Verlag,
[155] G. Grimmett and D. Stirzaker. Probability and Random Processes. Oxford Univer-
sity Press, 2nd ed., 1992.
[156] J. Ha and S. Moon. Randomized signed-scalar multiplication of ECC to resist power
attacks. In [CH02], 551“563.
[157] H. Handschuh, P. Paillier and J. Stern. Probing attacks on tamper-resistant devices.
In [CH99], 303“315.
[158] R. Harley. Asymptotically optimal p-adic point-counting. Email to normal-
fontNMBRTHRY mailing list, December 2002.
[159] R. Harley. Method for solving Frobenius equations for elliptic-curve cryptography.
United States Patent Application, December 2003.
[160] R. Harley and J.-F. Mestre. Method for generating secure elliptic curves using an
arithmetic-geometric mean iteration. United States Patent Application, June 2002.
[161] M.A. Hasan. Power analysis attacks and algorithmic approaches to their counter-
measures for Koblitz cryptosystems. In [CH00], 93“108.
[162] J. Herranz and G. S´ez. A provably secure ID-based ring signature scheme. See
[EP], # 2003/261, 2003.
[163] F. Hess. Exponent group signature schemes and e¬cient identity based signature
schemes based on pairings. See [EP], # 2002/012, 2002.
[164] F. Hess. E¬cient identity based signature schemes based on pairings. In K. Nyberg
and H. Heys, editors, Selected Areas in Cryptography “ SAC 2002, LNCS 2595,
310“324. Springer-Verlag, 2003.
[165] F. Hess. The GHS attack revisited. In [E03], 374“387.
[166] F. Hess. On the security of the veri¬ably-encrypted signature scheme of Boneh,
Gentry, Lynn and Shacham. Info. Proc. Lett., 89, 111“114, 2004.
[167] F. Hess. A note on the Tate pairing of curves over ¬nite ¬elds. Arch. Math., 82,
28“32, 2004.
[168] F. Hess. Generalising the GHS attack on the elliptic curve discrete logarithm prob-
lem. LMS J. Comput. and Math., 7, 167“192, 2004.
[169] F. Hess. Computing relations in divisor class groups of algebraic curves over ¬nite
¬elds. Preprint, 2003.
[170] F. Hess, N. P. Smart and G. Seroussi. Two topics in hyperelliptic cryptography.
In S. Vaudenay and A.M. Youssef, editors, Selected Areas in Cryptography “ SAC
2001, LNCS 2259, 181“189. Springer-Verlag, 2001.

[171] Y. Hitchcock and P. Montague. A new elliptic curve scalar multiplication algorithm
to resist simple power analysis. In L.M. Batten and J. Seberry, editors, Information
Security and Privacy “ ACISP 2002, LNCS 2384, 214“225. Springer-Verlag, 2002.
[172] J. Horowitz and B. Lynn. Toward hierarchical identity-based encryption. In [E02],
[173] E. W. Howe. The Weil pairing and the Hilbert symbol. Math. Ann., 305, 387“392,
[174] N. Howgrave-Graham and N.P. Smart. Lattice attacks on digital signature schemes.
Designs, Codes and Cryptography, 23, 283“290, 2001.
[175] K. Itoh, T. Izu and M. Takaneka. Address-bit di¬erential power analysis of crypto-
graphic schemes OK-ECDH and OK-ECDSA. In [CH02], 129“143.
[176] K. Itoh, T. Izu and M. Takaneka. A practical countermeasure against address-bit
di¬erential power analysis. In [CH03], 382“396.
[177] K. Itoh, J. Yajima, M. Takaneka and N. Torii. DPA countermeasures by improving
the window method. In [CH02], 303“317.
[178] T. Izu and T. Takagi. A fast parallel elliptic curve multiplication resistant against
side channel attacks. In [P02], 280“296.
[179] T. Izu and T. Takagi. Exceptional procedure attack on elliptic curve cryptosystems.
In [P03], 224“239.
[180] T. Izu and T. Takagi. E¬cient computations of the Tate pairing for the large MOV
degrees. In P.J. Lee and C.H. Lim, editors, Information Security and Cryptology “
ICISC 2002, LNCS 2587, 283“297. Springer-Verlag, 2003.
[181] M. Jacobson, A.J. Menezes and A. Stein. Solving elliptic curve discrete logarithm
problems using Weil descent. J. Ramanujan Math. Soc., 16, 231“260, 2001.
[182] M. Jacobson and A. van der Poorten. Computational aspects of NUCOMP. In
[A-5], 120“133.
[183] A. Joux. A one round protocol for tripartite Di¬e“Hellman. In [A-4], 385“394.
[184] A. Joux. The Weil and Tate pairings as building blocks for public key cryptosystems.
In [A-5], 20“32.
[185] A. Joux and R. Lercier. The function ¬eld sieve is quite special. In [A-5], 431“445.
[186] A. Joux and K. Nguyen. Separating Decision Di¬e“Hellman from Di¬e“Hellman
in cryptographic groups. J. Cryptology, 16, 239“248, 2003.
[187] M. Joye. Recovering lost e¬ciency of exponentiation algorithms on smart cards.
Elect. Lett., 38, 1095“1097, 2002.
[188] M. Joye and J.-J. Quisquater. Hessian elliptic curves and side-channel attacks. In
[CH01], 402“410.
[189] M. Joye, J.-J. Quisquater and M. Yung. On the power of misbehaving adversaries
and security analysis of the original EPOC. In D. Naccache, editor, Topics in
Cryptology “ CT-RSA 2001, LNCS 2020, 208“222. Springer-Verlag, 2001.
[190] M. Joye and C. Tymen. Protections against di¬erential analysis for elliptic curve
cryptography: An algebraic approach. In [CH01], 377“390.
[191] M. Joye and S.-M. Yen. The Montgomery powering ladder. In [CH02], 291“302.
[192] B.G. Kang, J.H. Park and S.G. Hahn. A certi¬cate-based signature scheme. In
T. Okamoto, editor, Topics in Cryptology “ CT-RSA 2004, LNCS 2964, 99“111.
Springer-Verlag, 2004.
[193] Kant group. Kash. http://www.math.tu-berlin.de/˜kant, 2003.
[194] A. Karatsuba and Y. Ofman. Multiplication of multidigit numbers on automata.
Soviet Physics Doklady, 7, 595“596, 1963.
[195] C. Karlof and D. Wagner. Hidden Markov model cryptanalysis. In [CH03], 17“34.
[196] K.S. Kedlaya. Counting points on hyperelliptic curves using Monsky-Washnitzer
cohomology. J. Ramanujan Math. Soc., 16, 323“338, 2001.

[197] J. Kempf, C. Gentry and A. Silverberg. Securing IPv6 neighbor discovery using
address based keys (ABKs). Internet Draft Document, expired December 2002,
2002. Available from http://www.docomolabs-usa.com/pdf/PS2003-080.pdf.
[198] A. Khalili, J. Katz and W.A. Arbaugh. Toward secure key distribution in truly
ad-hoc networks. In Proc. 2003 Symposium on Applications and the Internet Work-
shops (SAINT 2003). IEEE Computer Society, 2003.
[199] H.Y. Kim, J.Y. Park, J.H. Cheon, J.H. Park, J.H. Kim. and S.G. Hahn. Fast elliptic
curve point counting using Gaussian Normal Basis. In [A-5], 292“307.
[200] V. Klima and T. Rosa. Further results and considerations on side channel attacks
on RSA. In [CH02], 244“259.
[201] N. Koblitz. p-Adic Numbers, p-Adic Analysis, and Zeta-Functions. Springer-Verlag,
GTM 58, 1984.
[202] N. Koblitz. CM curves with good cryptographic properties. In [C91], 279“287.
[203] N. Koblitz. Algebraic Aspects of Cryptography. Springer-Verlag, 1997.
[204] H. Koch. Algebraic Number Theory. Springer-Verlag, 2nd ed., 1997.
[205] P.C. Kocher. Timing attacks on implementations of Di¬e“Hellman, RSA, DSS, and
other systems. In [C96], 104“113.
[206] P.C. Kocher, J. Ja¬e and B. Jun. Di¬erential power analysis. In [C99], 388“397.
[207] D.R. Kohel. Endomorphism rings of elliptic curves over ¬nite ¬elds. PhD thesis,
University of California, Berkeley, 1996.
[208] D.R. Kohel. The AGM-X0 (N ) Heegner point lifting algorithm and elliptic curve
point counting. In [A03], 124“136.
[209] D.R. Kohel and I.E. Shparlinski. On exponential sums and group generators for
elliptic curves over ¬nite ¬elds. In [A-4], 395“404.
[210] S. Lang. Algebra. Addison-Wesley, 3rd ed., 1993.
[211] T. Lange. E¬cient arithmetic on hyperelliptic curves. PhD thesis, Universit¨t- a
Gesamthochschule Essen, 2001.
[212] T. Lange. Formulae for arithmetic on genus 2 hyperelliptic curves. Appl. Algebra
Engrg. Comm. Comput., To appear.
[213] A.G.B. Lauder and D. Wan. Counting points on varieties over ¬nite ¬elds of small
characteristic. In J.P. Buhler and P. Stevenhagen, editors, Algorithmic Number
Theory: Lattices, Number Fields, Curves and Cryptography. Mathematical Sciences
Research Institute Publications, 2002. To appear.
[214] A.G.B. Lauder and D. Wan. Computing zeta functions of Artin-Schreier curves
over ¬nite ¬elds. LMS J. Comput. and Math., 5, 34“55, 2002.
[215] A.G.B. Lauder and D. Wan. Computing zeta functions of Artin-Schreier curves
over ¬nite ¬elds II. J. Complexity, 20, 331“349, 2004.
[216] L. Law, A.J. Menezes, M. Qu, J. Solinas and S. Vanstone. An e¬cient protocol
for authenticated key agreement. Designs, Codes and Cryptography, 28, 119“134,
[217] R. Lercier. Algorithmique des courbes elliptiques dans les corps ¬nis. PhD thesis,
Ecole Polytechnique, 1997.
[218] R. Lercier and D. Lubicz. Counting points on elliptic curves over ¬nite ¬elds of
small characteristic in quasi quadratic time. In [E03], 360“373.
[219] R. Lercier and D. Lubicz. A quasi quadratic time algorithm for hyperelliptic curve
point counting. Preprint, 2003.
[220] P.-Y. Liardet and N.P. Smart. Preventing SPA/DPA in ECC systems using the
Jacobi form. In [CH01], 391“401.
[221] B. Libert and J.-J. Quisquater. New identity based signcryption schemes from pair-
ings. See [EP], # 2003/023, 2003.

[222] B. Libert and J.-J. Quisquater. Identity based undeniable signatures. In
T. Okamoto, editor, Topics in Cryptology “ CT-RSA 2004, LNCS 2964, 112“125.
Springer-Verlag, 2004.
[223] B. Libert and J.-J. Quisquater. E¬cient signcryption with key privacy from gap
Di¬e-Hellman groups. In [P04], 187“200.
[224] S. Lichtenbaum. Duality theorems for curves over p-adic ¬elds. Inventiones Math.,
7, 120“136, 1969.
[225] J. L´pez and R. Dahab. Fast multiplication on elliptic curves over GF (2m ) without
precomputation. In [CH99], 316“327.
[226] D. Lorenzini. An Invitation to Arithmetic Geometry. AMS, Graduate Studies in
Mathematics 106, 1993.
[227] J. Lubin, J.-P. Serre and J. Tate. Elliptic curves and formal groups. Lecture notes
prepared in connection with the seminars held at the Summer Institute on Algebraic
Geometry, Whitney Estate, Woods Hole, Massachusetts, 1964.
[228] B. Lynn. Authenticated identity-based encryption. See [EP], # 2002/072, 2002.
[229] Magma Comp. algebra group. Magma. Available from http://www.maths.usyd.
edu.au:8000/u/magma/, 2003.
[230] J. Malone-Lee. Identity-based signcryption. See [EP], # 2002/098, 2002.
[231] J. Malone-Lee. Signcryption with non-interactive non-repudiation, To appear.
[232] J. Manger. A chosen ciphertext attack on RSA optimal asymmetric encryption
padding (OAEP) as standardized in PKCS # 1 v2.0. In [C01], 230“238.
[233] M. Maurer, A.J. Menezes and E. Teske. Analysis of the GHS Weil descent attack
on the ECDLP over characteristic two ¬nite ¬elds of composite degree. LMS J.
Comput. and Math., 5, 127“174, 2002.
[234] D. May, H.L. Muller and N.P. Smart. Random register renaming to foil DPA. In
[CH01], 28“38.
[235] R. Mayer-Sommer. Smartly analyzing the simplicity and the power of simple power
analysis on smartcards. In [CH00], 78“92.
[236] A. Miyaji, T. Ono and H. Cohen. E¬cient elliptic curve exponentiation. In Y. Han,
T. Okamoto and S. Qing, editors, Information and Communications Security
(ICICS ™97), LNCS 1334, 282“290. Springer-Verlag, 1997.
[237] W. Meier and O. Sta¬elbach. E¬cient multiplication on certain non-supersingular
elliptic curves. In [C92], 333“344.
[238] A.J. Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer, 1993.
[239] A.J. Menezes, T. Okamoto and S.A. Vanstone. Reducing elliptic curve logarithms
to a ¬nite ¬eld. IEEE Trans. Inf. Theory, 39, 1639“1646, 1993.
[240] A.J. Menezes, P.C. van Oorschot and S.A. Vanstone. Handbook of Applied Cryp-
tography. CRC Press, 1996.
[241] A.J. Menezes and M. Qu. Analysis of the Weil descent attack of Gaudry, Hess and
Smart. In D. Naccache, editor, Topics in Cryptology “ CT-RSA 2001, LNCS 2020,
308“318. Springer-Verlag, 2001.
[242] A.J. Menezes, E. Teske and A. Weng. Weak ¬elds for ECC. In T. Okamoto, editor,
Topics in Cryptology “ CT-RSA 2004, LNCS 2964, 366“386. Springer-Verlag, 2004.
[243] A.J. Menezes, Y.-H. Wu and R. Zuccherato. An elementary introduction to hyper-
elliptic curves. In [203], 155-178.
[244] T.S. Messerges. Using second-order power analysis to attack DPA resistant soft-
ware. In [CH00], 238“251.
[245] T.S. Messerges, E.A. Dabbish and R.H. Sloan. Power analysis attacks of modular
exponentiation in smartcards. In [CH99], 144“157.
[246] W. Messing. The crystals associated to Barsotti-Tate groups: with applications to
abelian schemes. Springer-Verlag, GTM 264, 1972.

[247] J.-F. Mestre. Lettre adress´e ` Gaudry et Harley, December 2000. Available at
[248] J.-F. Mestre. Algorithmes pour compter des points de courbes en
petite caract´ristique et en petit genre, March 2002. Available at
[249] V. Miller. Short programs for functions on curves. Unpublished manuscript, 1986.
[250] S. Mitsunari, R. Sakai and M. Kasahara. A new traitor tracing schemes using
bilinear map. IEICE Trans. Fundamentals, E84, 481“484, 2002.
[251] A. Miyaji, M. Nakabayashi and S. Takano. New explicit conditions of elliptic curve
traces for FR-reduction. IEICE Trans. Fundamentals, E84, 1234“1243, 2001.
[252] R.T. Moenck. Fast computation of GCDs. In Proc. 5th Annual ACM Symposium
on the Theory of Computing, 142“151. ACM, 1973.
[253] B. M¨ller. Securing elliptic curve point multiplication against side-channel attacks.
In G.I. Davida and Y. Frankel, editors, Information Security, LNCS 2200, 324“334.
Springer-Verlag, 2001.
[254] P.L. Montgomery. Modular multiplication without trial division. Math. Comp., 44,
519“521, 1985.
[255] P.L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization.
Math. Comp., 48, 243“264, 1987.
[256] F. Morain and J. Olivos. Speeding up the computations on an elliptic curve using
addition-subtraction chains. Theoretical Informatics and Applications, 24, 531“543,
[257] V. M¨ller, A. Stein and C. Thiel. Computing discrete logarithms in real quadratic
congruence function ¬elds of large genus. Math. Comp., 68, 807“822, 1999.
[258] K. Nagao. Improving group law algorithms for Jacobians of hyperelliptic curves. In
[A-4], 439“447.
[259] D. Nalla and K.C. Reddy. ID-based tripartite authenticated key agreement proto-
cols from pairings. See [EP], # 2003/04, 2003.
[260] J. Neukirch. Algebraic Number Theory. Springer-Verlag, 1999.
[261] P.Q. Nguyen and I.E. Shparlinski. The insecurity of the Digital Signature Algorithm
with partially known nonces. J. Cryptology, 15, 151“176, 2002.
[262] P.Q. Nguyen and I.E. Shparlinski. The insecurity of the Elliptic Curve Digital Sig-
nature Algorithm with partially known nonces. Designs, Codes and Cryptography,
30, 201“217, 2003.
[263] T. Okamoto and D. Pointcheval. The gap problems: A new class of problems for
the security of cryptographic schemes. In [P01], 104“118.
[264] K. Okeya and K. Sakurai. Power analysis breaks elliptic curve cryptosystems even
secure against the timing attack. In B. Roy and E. Okamoto, editors, Progress in
Cryptology “ INDOCRYPT 2000, LNCS 1977, 178“190. Springer-Verlag, 2000.
[265] K. Okeya and K. Sakurai. On insecurity of the side channel attack countermeasure
using addition-subtraction chains under distinguishability between addition and
doubling. In L. Batten and J. Seberry, editors, Information Security and Privacy “
ACISP 2002, LNCS 2384, 420“435. Springer-Verlag, 2002.
[266] P.C. van Oorschot and M.J. Wiener. Parallel collision search with cryptanalytic
applications. J. Cryptology, 12, 1“28, 1999.
[267] G. Orlando and C. Paar. A high performance recon¬gurable elliptic curve processor
for GF (2m ). In [CH00], 41“56.
[268] S.B. Ors, E. Oswald and B. Preneel. Power-analysis attacks on FPGAs “ First
experimental results. In [CH03], 35“50.
[269] E. Oswald. Enhancing simple power-analysis attacks on elliptic curve cryptosys-
tems. In [CH02], 82“97.

[270] E. Oswald. Markov model side-channel analysis. Unpublished manuscript, 2003.
[271] E. Oswald and M. Aigner. Randomized addition-subtraction chains as a counter-
measure against power attacks. In [CH01], 39“50.
[272] K.G. Paterson. ID-based signatures from pairings on elliptic curves. Elect. Lett.,
38, 1025“1026, 2002.
[273] K.G. Paterson. Cryptography from pairings: a snapshot of current research. Infor-
mation Security Technical Report, 7, 41“54, 2002.
[274] K.G. Paterson and G. Price. A comparion between traditional PKIs and identity-
based cryptography. Information Security Technical Report, 8, 57“72, 2003.
[275] S. Paulus and A. Stein. Comparing real and imaginary arithmetics for divisor class
groups of hyperelliptic curves. In [A-3], 576“591.
[276] D. Pointcheval and J. Stern. Security arguments for digital signatures and blind
signatures. J. Cryptology, 13, 361“396, 2000.
[277] J. Pelzl, T. Wollinger, J. Guajardo and C. Paar. Hyperelliptic curve cryptosystems:
Closing the performance gap to elliptic curves. In [CH03], 351“365.
[278] J.-J. Quisquater and D. Samyde. Electromagnetic analysis (EMA): Measures and
counter-measures for smart cards. In S. Attali and T. Jensen, editors, Smart Card
Programming and Security (E-smart 2001), LNCS 2140, 200“210. Springer-Verlag,
[279] M.O. Rabin. Digitalized signatures and public-key functions as intractable as factor-
ization. MIT Laboratory for Computer Science, Technical Report MIT/LCS/TR-
212, 1979.
[280] C. Racko¬ and D. Simon. Non-interactive zero-knowledge proof of knowledge and
chosen ciphertext attack. In [C91], 434“444.
[281] K.C. Reddy and D. Nalla. Identity based authenticated group key agreement proto-
col. In A.J. Menezes and P. Sarkar, editors, Progress in Cryptology “ INDOCRYPT
2002, LNCS 2551, 215“233. Springer-Verlag, 2002.
[282] C. Ritzenthaler. Point counting on genus 3 non hyperelliptic curves. In [A-6], 379“
[283] H.G. R¨ck. On the discrete logarithm in the divisor class group of curves. Math.
Comp., 68, 805“806, 1999.
[284] R. Sakai, K. Ohgishi and M. Kasahara. Cryptosystems based on pairing. In 2000
Symposium on Cryptography and Information Security “ SCIS 2000, 2000.
[285] T. Satoh. The canonical lift of an ordinary elliptic curve over a ¬nite ¬eld and its
point counting. J. Ramanujan Math. Soc., 15, 247“270, 2000.
[286] T. Satoh. On p-adic point counting algorithms for elliptic curves over ¬nite ¬elds.
In [A-5], 43“66.
[287] T. Satoh, B. Skjernaa and Y. Taguchi. Fast computation of canonical lifts of elliptic
curves and its application to point counting. Finite Fields Appl., 9, 89“101, 2003.
[288] W. Schindler. A timing attack against RSA with the Chinese remainder theorem.
In [CH00], 109“124.
[289] W. Schindler. A combined timing and power attack. In [P02], 263“279.
[290] J. Scholten. Weil restriction of an elliptic curve over a quadratic extension. Preprint,
[291] A. Sch¨nhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. Computing
(Arch. Elektron. Rechnen), 7, 281“292, 1971.
[292] R. Schoof. Elliptic curves over ¬nite ¬elds and the computation of square roots
modp. Math. Comp., 44, 483“494, 1985.
[293] R. Schoof. Nonsingular plane cubic curves over ¬nite ¬elds. J. Combin. Theory Ser.
A, 46, 183“211, 1987.

[294] R. Schoof. Counting points on elliptic curves over ¬nite ¬elds. J. Th´or. Nombres
Bordeaux, 7, 219“254, 1995.
[295] J.-P. Serre. Local Fields. Springer-Verlag, GTM 67, 1979.
[296] A. Shamir. Identity based cryptosystems and signature schemes. In [C84], 47“53.
[297] A. Shamir. Protecting smart cards from passive power analysis with detached power
supplies. In [CH00], 71“77.
[298] D. Shanks. On Gauss and composition I and II. In R. Mollin, editor, Number Theory
and its Applications, 163“204. Kluwer Academic Publishers, 1989.
[299] K. Shim. A man-in-the-middle attack on Nalla-Reddy™s ID-based tripartite authen-
ticated key agreement protocol. See [EP], # 2003/115, 2003.
[300] K. Shim. Cryptanalysis of Al-Riyami-Paterson™s authenticated three party key
agreement protocols. See [EP], # 2003/122, 2003.
[301] K. Shim. E¬cient one round tripartite authenticated key agreement protocol from
Weil pairing. Elect. Lett., 39, 208“209, 2003.
[302] K. Shim. E¬cient ID-based authenticated key agreement protocol based on Weil
pairing. Elect. Lett., 39, 653“654, 2003.
[303] V. Shoup. Lower bounds for discrete logarithms and related problems. In [C97],
[304] V. Shoup. Using hash functions as a hedge against chosen ciphertext attack. In
[E00], 275“288.
[305] V. Shoup. A proposal for an ISO standard for public key encryption, v2.1. Preprint,
[306] A. Silverberg and K. Rubin. Supersingular abelian varieties in cryptology. In [C02],
[307] J.H. Silverman. The Arithmetic of Elliptic Curves. Springer-Verlag, GTM 106,
[308] B. Skjernaa. Satoh™s algorithm in characteristic 2. Math. Comp., 72, 477“487, 2003.
[309] N.P. Smart. The Hessian form of an elliptic curve. In [CH01], 118“125.
[310] N.P. Smart. The exact security of ECIES in the generic group model. In B. Honary,
editor, Coding and Cryptography, LNCS 2260, 73“84. Springer-Verlag, 2001.
[311] N.P. Smart. How secure are elliptic curves over composite extension ¬elds? In
[E01], 30“39.
[312] N.P. Smart. An identity based authenticated key agreement protocol based on the
Weil pairing. Elect. Lett., 38, 630“632, 2002.
[313] N.P. Smart. An analysis of Goubin™s re¬ned power analysis attack. In [CH03],
[314] N.P. Smart. Access control using pairing based cryptography. In M. Joye, editor,
Topics in Cryptology “ CT-RSA 2003, LNCS 2612, 111“121. Springer-Verlag, 2003.
[315] D.K. Smetters and G. Durfee. Domain-based administration of identity-based cryp-
tosystems for secure email and IPSEC. In Proc. 12th USENIX Security Symposium,
215“229, 2003.
[316] J. Solinas. E¬cient arithmetic on Koblitz curves. Designs, Codes and Cryptography,
19, 195“249, 2000.
[317] A. Stein. Sharp upper bounds for arithmetics in hyperelliptic function ¬elds. J.
Ramanujan Math. Soc., 16, 1“86, 2001.
[318] E. Steinfeld, L. Bull, H. Wang and J. Pieprzyk. Universal designated-veri¬er signa-
tures. In [A03], 523“542.
[319] H. Stichtenoth. Algebraic Function Fields and Codes. Springer-Verlag, 1993.
[320] H. Stichtenoth and C. Xing. On the structure of the divisor class group of a class
of curves over ¬nite ¬elds. Arch. Math,, 65, 141“150, 1995.

[321] D.R. Stinson. Some observations on the theory of cryptographic hash functions.
See [EP], # 2001/020, 2002.
[322] H.-M. Sun and B.-T. Hsieh. Security analysis of Shim™s authenticated key agreement
protocols from pairings. See [EP], # 2003/113, 2003.
[323] E. Teske. Speeding up Pollard™s rho method for computing discrete logarithms. In
[A-3], 541“554.
[324] E. Teske. An elliptic curve trapdoor system. J. Cryptology, To appear.
[325] N. Th´riault. Index calculus attack for hyperelliptic curves of small genus. In [A03],
[326] N. Th´riault. Weil descent attack for Kummer extensions. J. Ramanujan Math.
Soc., 18, 281“312, 2003.
[327] N. Th´riault. Weil descent attack for Artin-Schreier curves. Preprint, 2004.
´ Thom´. Subquadratic computation of vector generating polynomials and im-
[328] E. e
provement of the block Wiedemann algorithm. J. Symbolic Comput., 33, 757“775,
[329] E. Trichina and A. Bellezza. Implementation of elliptic curve cryptography with
built-in countermeasures against side channel attacks. In [CH02], 98“113.
[330] S. Vaudenay. Security ¬‚aws induced by CBC padding “ Applications to SSL, IPSEC,
WTLS... In [E02], 534“546.
[331] S. Vaudenay. Hidden collisions on DSS. In [C96], 83“87.
[332] J. V´lu. Isog´nies entre courbes elliptiques. C.R. Acad. Sc. Paris, S´rie A, 273,
e e e
238“241, 1971.
[333] F. Vercauteren. Computing Zeta Functions of Curves over Finite Fields. PhD thesis,
Katholieke Universiteit Leuven, 2003.
[334] F. Vercauteren, B. Preneel and J. Vandewalle. A memory e¬cient version of Satoh™s
algorithm. In [E01], 1“13.
[335] E.R. Verheul. Evidence that XTR is more secure than supersingular elliptic curve
cryptosystems. In [E01], 195“210.
[336] E.R. Verheul. Evidence that XTR is more secure than supersingular elliptic curve
cryptosystems. J. Cryptology, To appear.
[337] E.R. Verheul. Self-blindable credential certi¬cates from the Weil pairing. In [A01],
[338] C.D. Walter. Montgomery™s multiplication technique: How to make it smaller and
faster. In [CH99], 80“93.
[339] C.D. Walter. Sliding windows succumbs to Big Mac attack. In [CH01], 286“299.
[340] C.D. Walter. Breaking the Liardet-Smart randomized exponentiation algorithm.
In P. Honeyman, editor, Smart Card Research and Advanced Applications, 59“68.
Usenix Association, 2002.
[341] C.D. Walter. Some security aspects of the MIST randomized exponentiation algo-
rithm. In [CH02], 276“290.
[342] C.D. Walter and S. Thompson. Distinguishing exponent digits by observing mod-
ular subtractions. In D. Naccache, editor, Topics in Cryptology “ CT-RSA 2001,
LNCS 2020, 192“207. Springer-Verlag, 2001.
[343] L.C. Washington. Elliptic Curves: Number Theory and Cryptography. CRC Press,
[344] E. Waterhouse. Abelian varieties over ¬nite ¬elds. Ann. Sci. Ecole Norm. Sup., 4th
series, 2, 521“560, 1969.
[345] B.R. Waters, D. Balfanz, G. Durfee and D.K. Smetters. Building an encrypted
and searchable audit log. In Proc. of Network and Distributed System Security
Symposium 2004 “ NDSS ™04, 2004.

[346] A. Weil. Numbers of solutions of equations in ¬nite ¬elds. Bull. Amer. Math. Soc.,
55, 497“508, 1949.
[347] A. Weil. The ¬eld of de¬nition of a variety. Am. J. Math., 78, 509“524, 1956.
[348] N. Weste and K. Eshraghian. Principles of CMOS VLSI Design. Addison-Wesley,
2nd ed., 1993.
[349] P. Wright. Spy Catcher: The Candid Autobiography of a Senior Intelligence O¬cer.
Viking Press, 1987.
[350] X. Yi. An identity-based signature scheme from the Weil pairing. IEEE Comm.
Lett., 7, 76“78, 2003.
[351] X. Yi. E¬cient ID-based key agreement from Weil pairing. Elect. Lett., 39, 206“
208, 2003.
[352] D.H. Yum and P.J. Lee. E¬cient key updating signature schemes based on IBS. In
K.G. Paterson, editor, Cryptography and Coding, LNCS 2898, 167“182. Springer-
Verlag, 2003.
[353] F. Zhang and X. Chen. Attack on two ID-based group key agreement schemes. See
[EP], # 2003/259, 2003.
[354] F. Zhang and K. Kim. ID-based blind signature and ring signature from pairings.
In [A02], 533“547.
[355] F. Zhang and K. Kim. E¬cient ID-based blind signature and proxy signature from
bilinear pairings. In R. Safavi-Naini, editor, Information Security and Privacy “
ACISP 2003, LNCS 2727, 312“323. Springer-Verlag, 2003.
[356] F. Zhang and S. Liu. ID-based one round authenticated tripartite key agreement
protocol with pairings. See [EP], # 2002/122, 2002.
[357] F. Zhang, R. Safavi-Naini and W. Susilo. E¬cient veri¬ably encrypted signa-
tures and partially blind signatures from bilinear pairings. In T. Johansson and
S. Maitra, editors, Progress in Cryptology “ INDOCRYPT 2003, LNCS 2904, 191“
204. Springer-Verlag, 2003.
[358] F. Zhang, R. Safavi-Naini and W. Susilo. An e¬cient signature scheme from bilinear
pairings and its applications. In [P04], 277“290.
[359] F. Zhang, R. Safavi-Naini and C.-Y. Lin. New proxy signature, proxy blind signa-
ture and proxy ring signature schemes from bilinear pairing. See [EP], # 2003/104,

Summary of Major LNCS Proceedings
For ease of reference we include here a table listing the main conference
proceedings and the associated LNCS volume numbers. This includes all
conferences in the relevant series which were published by Springer-Verlag
and not necessarily those just referenced in this book.
Year Crypto Eurocrypt Asiacrypt CHES PKC ANTS
2004 3027 2947 3076
2003 2729 2656 2894 2779 2567
2002 2442 2332 2501 2523 2274 2369
2001 2139 2045 2248 2162 1992
2000 1880 1807 1976 1965 1838
1999 1666 1592 1716 1717 1560
1998 1462 1403 1514 1431 1423
1997 1294 1233
1996 1109 1070 1163 1122
1995 963 921
1994 839 950 917 877
1993 773 765
1992 740 658
1991 576 547 739
1990 537 473
1989 435 434
1988 403 330
1987 293 304
1986 263
1985 218 219
1984 196 209
1982 149
Author Index

Abdalla, M., 12, 50 Dahab, R., 93
Dalton, C.R., 249
Adleman, L., 142, 144
DeMarrais, J., 142, 144
Al-Riyami, S.S., 247, 248
Denef, J., 132
van Antwerpen, H., 230
Dent, A., 32
Appenzeller, G., 249
Desmedt, Y.G., 242
Arbaugh, W.A., 249
Deuring, M., 105
Atkin, A.O.L., 103
Diem, C., 231
Dodis, Y., 240
Balasubramanian, R., 192, 208, 209
Dupont, R., 211, 219
Balfanz, D., 249
Durfee, G., 249
Barreto, P.S.L.M., 205, 206, 211, 215
Duursma, I., 208
Bellare, M., 12, 26, 41, 50, 240, 241
Dwork, B., 132
Blake-Wilson, S., 241
Bleichenbacher, D., 8, 26, 74
Eisentr¨ger, K., 206
Boldyreva, A., 233
Elkies, N., 103
Boneh, D., 8, 42, 194, 195, 202, 215, 218,
Enge, A., 143, 144, 147, 211, 219
219, 221“233, 235, 239, 240, 244, 247,
249, 250
Flassenberg, R., 144
Boyd, C., 241
Fouquet, M., 113
Boyen, X., 234, 239
Franklin, M., 202, 215, 218, 219, 221“229,
Brezing, F., 211
235, 240, 244, 247, 249, 250
Brier, E., 88
Frey, G., 151, 185, 189, 197
Brown, D., 31
Fujisaki, E., 225, 237, 247
Bull, L., 233
Burmester, M., 242 Galbraith, S.D., 205, 208, 242
Garefalakis, T., 192
Canetti, R., 32, 238, 239 von zur Gathen, J., 131
Cantor, D.G., 136 Gaudry, P., 113, 115, 121, 132, 144, 147,
Carls, R., 115 148, 152, 156
Cha, J., 228 Gauss, F., 136
Chaum, D., 97, 230 Gentry, C., 233, 235, 237, 246, 247, 249
Chen, A.H., 246 Gerhard, J., 131
Chen, L., 234, 241 Gerkmann, R., 132
Chen, X., 247 Gligor, V.D., 246
Cheon, J.H., 122, 123, 228 Goldreich, O., 32
Chevallier-Mames, B., 94 Goldwasser, S., 23, 26, 41
Ciet, M., 94 Goubin, L., 84
Cocks, C., 210, 221 G¨rel, N., 132
Coppersmith, D., 205, 231
Coron, J.-S., 84, 85 Hahn, S.G., 122, 123
Halevi, S., 32, 238, 239
Couveignes, J.-M., 103

Mao, W., 241
Harley, R., 103, 113, 115, 127, 128, 131,
148, 156 Maurer, U,, 8
Harrison, K., 205 Menezes, A., 10, 197, 198, 200, 241
Herranz, J., 232 Messerges, T.S., 84
Hess, F., 152, 189, 191 Messing, W., 106
Hopkins, H.J., 242 Mestre, J.-F., 115, 132
Horowitz, J., 235 Micali, S., 23, 41
Howgrave-Graham, N, 8, 26 Micciancio, D., 26
Huang, M.-D., 142, 144 Miller, V., 196, 201
Mironov, I., 233
Izu, T., 206 Miyaji, A., 209, 240
Moenck, R.T., 131
Johnson, D., 241
Montgomery, P., 93, 206
Joux, A., 42, 202, 203, 215, 218, 220, 221,
Morain, F., 211
223, 242
M¨ller, V., 144
Joye, M., 88, 90, 94
Nakabayashi, M., 209
Karatsuba, A., 103
Nalla, D., 242
Kasahara, M., 215, 218, 220, 222, 228,
Naor, M., 230, 237
234, 237, 240, 241, 249
Nguyen, K., 193, 202
Katz, J., 238“240, 249
Nguyen, P., 8, 26, 42
Kedlaya, K.S., 129, 132
Kempf, J., 249
Ofman, Y., 103
Khalili, A., 249
Ohgishi, K., 215, 218, 220, 222, 228, 234,
Kim, H.Y., 122, 123, 205
237, 240, 241, 249
Kim, J.H., 122, 123
Okamoto, T., 197, 198, 200, 225, 237, 247
Kim, K., 232, 247
van Oorschot, P., 142
Koblitz, N., 99, 104, 133, 192, 208, 209
Kocher, P., 72, 73
Palacio, A., 233, 240
Kohel, D., 115, 201
Park, J.H., 122, 123
Kudla, C., 241
Park, J.Y., 122, 123
Paterson, K.G., 241, 247, 248
Lagrange, J.-L., 136
Paulus, S., 144
Lang, S., 210
Pieprzyk, J., 233
Lauder, A., 132
Pinch, R., 210
Lauter, K., 206
Pointcheval, D., 22
Law, L., 10
Pollard, J., 142, 148
Lee, H.-S., 208
Lee, P.J., 240
Qu, M., 10
Lercier, R., 103, 126, 132
Quisquater, J.-J., 90, 232“234
Liardet, P.-Y., 90, 91
Libert, B., 232“234
R¨ck, H.-G., 141, 185, 189, 197
Lichtenbaum, S., 185
Rabin, M.O., 41
Lin, C.-Y., 232
Racko¬, C., 41
Liu, S., 242
Reddy, K.C., 242
L´pez, J., 93
Rivest, R., 23
Lubicz, D., 126, 132
Rogaway, P., 12, 41, 50, 241
Lubin, J., 105, 106
Rubin, K., 208
Lynn, B., 194, 205, 206, 211, 228“235,
S´ez. G., 232
Malone-Lee, J., 233, 234 Safavi-Naini, R., 232, 233

Sakai, R., 215, 218“220, 222, 228, 234, Wolf, S., 8
237, 240, 241, 249 Wright, P., 72
Satoh, T., 103“132
Yi, X., 241
Sch¨nhage, A., 103
Yum, D.H., 240
Schoof, R., 103
Yung, M., 240
Scott, M., 205, 206, 211
Serre, J.-P., 104“106, 132 Zhang, F., 232, 233, 242, 247
Shacham, H., 194, 229“233
Shamir, A., 218, 221, 228
Shanks, D., 137
Shim, K., 241
Shoup, V., 31, 57, 61, 62, 64, 233
Shparlinski, I., 8, 26, 201, 242
Silverberg, A., 208, 235, 237, 249
Silverman, J.H., 184, 191, 198, 212
Simon, D., 41
Skjernaa, B., 113, 122“125, 129, 130
Smart, N.P., 8, 26, 57, 90, 91, 152, 240,
Smetters, D.K., 249
Soldera, D., 205
Solinas, J., 10
Stein, A., 143, 144
Steinfeld, E., 233
Stern, J., 22
Stinson, D., 28
Strassen, V., 103
Susilo, W., 233

Taguchi, Y., 122“125, 129, 130
Takagi, T., 206
Takano, S., 209
Tate, J., 105, 106, 132, 185
Th´riault, N., 148, 149, 156
Thiel, C., 144

Vanstone, S., 10, 197, 198, 200
Vaudenay, S., 27
V´lu, J., 110
Vercauteren, F., 114, 122, 132
Verheul, E., 194, 203, 215, 216, 221, 226,
227, 233

Wan, D., 132
Wang, H., 233
Warinschi, B., 233
Washington, L.C., 184
Waterhouse, W.C., 199
Waters, B.R., 249
Weil, A., 136, 153, 185
Weng, A., 211
Wiener, M., 142
Subject Index

abelian variety, 151 BSGS, 18, 142
active attack, 64
canonical lift, 105“108, 116“117
on a device, 69, 71“72
Cantor™s algorithm, 136, 140
adaptive chosen ciphertext attack, see CCA2
CBE, 246“248
addition formulae
CCA, 16, 46, 48, 50, 51, 64“66, 74, 224,
dummy operations, 91“92
225, see also CCA1 and CCA2
indistinguishable, 88“92
CCA1, 46, 64
uni¬ed, 88“89
CCA2, 13, 14, 46, 48, 61, 64
Advanced Encryption Standard, see AES
CDH problem, 47, 48, 50, 202, 228“230,
advantage, 44
232, 233, 237, 250
AES, 12
Certicom, 4
aggregate signature, 233
Certi¬cate-Based Encryption, see CBE
AGM, 115“121
Certi¬cateless Public Key Cryptography,
algorithm, 119“120
see CL-PKC
univariate, 120“121
Certi¬cation Authority, 218
anomalous attack, 141
chosen ciphertext attack, see CCA
ANSI, 18
chosen plaintext attack, see CPA
ANSI X9.62, 4, 174
CL-PKC, 247“249
ANSI X9.63, 4
CM method, 209, 210
Application protocol data units, 71
cofactor Di¬e“Hellman, 9
collusion resistent, 220
construction, 164
complexity-theoretic, 47
equation, 125“128, 154
computational Di¬e“Hellman problem, see
extension, 153, 155, 176
CDH problem
operator, 164
conorm, 152
Baby Step/Giant Step, see BSGS conversion function, 5, 24, 26, 29, 32, 33
BDH problem, 202, 203, 218, 219, 221, correlation analysis, 76
222, 224, 226, 228, 234, 237, 238, CPA, 45, 46, 64
241, 242, 247, 250 cryptographic hardware, 69“71
generalized, 248 cryptographic work¬‚ow, 244“246, 248
benign malleability, 14, 15, 61 curve validation, 18
bilinear Di¬e“Hellman problem, see BDH cyclotomic polynomial, 210
bilinearity (of modi¬ed pairing), 217 Data Encapsulation Mechanism, see DEM
binary tree encryption, 238 data origin authentication, 9
black box groups, 8 DBDH problem, 202, 218, 234, 238, 239
blind signature, 97 DDH problem, 47, 50, 55“58, 202, 229,
BLS short signature, 229“232
Boneh“Franklin encryption scheme, 222“ decision bilinear Di¬e“Hellman problem,
226 see DBDH problem


. 9
( 10)