ńņš. 9 |

Ė

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:

r

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 .

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

X.7. APPLICATIONS AND INFRASTRUCTURES 247

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

18

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

key.

248 X. CRYPTOGRAPHY FROM PAIRINGS

ļ¬rst checks that the equality

e(XA , Q0 ) = e(YA , P )

Ė Ė

holds, then selects t at random from Zā— and sets:

r

C = [t]P, M ā• H2 (Ė(QA , YA )t ) .

e

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 )).

e

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

r

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

X.7. APPLICATIONS AND INFRASTRUCTURES 249

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

250 X. CRYPTOGRAPHY FROM PAIRINGS

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

http://crypto.stanford.edu/ibe/download.html

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

busy.

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.

X.8. CONCLUDING REMARKS 251

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.

Bibliography

[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.

253

254 BIBLIOGRAPHY

[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,

2001.

[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,

2004.

[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.

BIBLIOGRAPHY 255

[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,

1999.

[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.

256 BIBLIOGRAPHY

[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.

br/informatica/paulobarreto/pblounge.html.

[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],

232ā“249.

[26] I. Biehl, B. Meyer and V. MĀØller. Diļ¬erential fault attacks on elliptic curve cryp-

u

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,

1997.

[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.

BIBLIOGRAPHY 257

[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ā“

46.

[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

http://crypto.stanford.edu/˜dabo/abstracts/weilsigs.html.

[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-

ee

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],

335ā“345.

[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.

258 BIBLIOGRAPHY

[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,

2004.

[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.

BIBLIOGRAPHY 259

[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,

2001.

[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.

260 BIBLIOGRAPHY

[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.

a

[104] C. Diem. The GHS-attack in odd characteristic. J. Ramanujan Math. Soc., 18,

2002.

[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

a

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.

BIBLIOGRAPHY 261

[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,

1999.

[126] G. Frey and H.-G. RĀØck. A remark concerning m-divisibility and the discrete log-

u

arithm problem in the divisor class group of curves. Math. Comp., 62, 865ā“874,

1994.

[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,

1999.

[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

u

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.

262 BIBLIOGRAPHY

[147] C. Gentry and A. Silverberg. Heirarchical ID-based cryptography. In [A02], 548ā“

566.

[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.

a

[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,

2003.

[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

a

[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.

BIBLIOGRAPHY 263

[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],

466ā“481.

[173] E. W. Howe. The Weil pairing and the Hilbert symbol. Math. Ann., 305, 387ā“392,

1996.

[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.

264 BIBLIOGRAPHY

[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,

2003.

[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.

BIBLIOGRAPHY 265

[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

o

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.

266 BIBLIOGRAPHY

[247] J.-F. Mestre. Lettre adressĀ“e ` Gaudry et Harley, December 2000. Available at

ea

http://www.math.jussieu.fr/˜mestre/.

[248] J.-F. Mestre. Algorithmes pour compter des points de courbes en

petite caractĀ“ristique et en petit genre, March 2002. Available at

e

http://www.math.jussieu.fr/˜mestre/.

[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.

o

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,

1990.

[257] V. MĀØller, A. Stein and C. Thiel. Computing discrete logarithms in real quadratic

u

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.

BIBLIOGRAPHY 267

[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,

2001.

[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ā“

394.

[283] H.G. RĀØck. On the discrete logarithm in the divisor class group of curves. Math.

u

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,

2004.

[291] A. SchĀØnhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. Computing

o

(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.

268 BIBLIOGRAPHY

[294] R. Schoof. Counting points on elliptic curves over ļ¬nite ļ¬elds. J. ThĀ“or. Nombres

e

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],

256ā“266.

[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,

2001.

[306] A. Silverberg and K. Rubin. Supersingular abelian varieties in cryptology. In [C02],

336ā“353.

[307] J.H. Silverman. The Arithmetic of Elliptic Curves. Springer-Verlag, GTM 106,

1986.

[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],

281ā“290.

[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.

BIBLIOGRAPHY 269

[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],

e

75ā“92.

[326] N. ThĀ“riault. Weil descent attack for Kummer extensions. J. Ramanujan Math.

e

Soc., 18, 281ā“312, 2003.

[327] N. ThĀ“riault. Weil descent attack for Artin-Schreier curves. Preprint, 2004.

e

Ā“ ThomĀ“. Subquadratic computation of vector generating polynomials and im-

[328] E. e

provement of the block Wiedemann algorithm. J. Symbolic Comput., 33, 757ā“775,

2002.

[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],

533ā“551.

[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,

2003.

Ā“

[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.

270 BIBLIOGRAPHY

[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,

2003.

SUMMARY OF MAJOR LNCS PROCEEDINGS 271

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

a

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

u

Coppersmith, D., 205, 231

Coron, J.-S., 84, 85 Hahn, S.G., 122, 123

Halevi, S., 32, 238, 239

Couveignes, J.-M., 103

273

274 AUTHOR INDEX

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

u

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

u

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

o

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,

249

SĀ“ez. G., 232

a

Malone-Lee, J., 233, 234 Safavi-Naini, R., 232, 233

AUTHOR INDEX 275

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

o

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,

241

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

e

Thiel, C., 144

Vanstone, S., 10, 197, 198, 200

Vaudenay, S., 27

VĀ“lu, J., 110

e

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

Artinā“Schreier

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

problem

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,

230

BLS short signature, 229ā“232

Bonehā“Franklin encryption scheme, 222ā“ decision bilinear Diļ¬eā“Hellman problem,

226 see DBDH problem

277

278 SUBJECT INDEX

ńņš. 9 |