Abstract
Elliptic curves were first proposed as a tool for cryptography by V. Miller in 1985 [29]. Indeed, since elliptic curves have a group structure, they nicely fit as a replacement for more traditional groups in discrete logarithm based systems such as Diffie-Hellman or ElGamal. Moreover, since there is no non-generic algorithm for computing discrete logarithms on elliptic curves, it is possible to reach a high security level while using relatively short keys.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. M. Adleman and M. A. Huang. Function field sieve method for discrete logarithms over finite fields. In Information and Computation, volume 151, pages 5–16. Academic Press, 1999.
P. Barreto and H. Kim. Fast hashing onto elliptic curves of fields of characteristic 3. Cryptology eprint Archives http://eprint.iacr.org, 2001. Number 2001/096.
P. Barreto, H. Kim, B. Lynn, and M. Scott. Efficient algorithms for pairing-based cryptosystems. Cryptology eprint Archives http://eprint.iacr.org, 2002. Number 2002/008.
D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. In J. Kilian, editor, Proceedings of CRYPTO’2001, volume 2139 of Lecture Notes in Comput. Sci., pages 213–229. Springer, 2001.
D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In C. Boyd, editor, Proceedings of ASIACRYPT’2001, volume 2248 of Lecture Notes in Comput. Sci., pages 514–532. Springer, 2001. Updated version available from the authors.
S. Brands. An efficient off-line electronic cash system based on the representation problem. Technical Report CS-R9323, CWI, Amsterdam, 1993.
M. Burmester and Y. Desmedt. A secure and efficient conference key distribution system. In A. De Santis, editor, Advances in Cryptology — EUROCRYPT’94, volume 950 of Lecture Notes in Comput. Sci., pages 275–286. Springer, 1995.
J. C. Cha and J. H. Cheon. An identity-based signature from gap Diffie—Hellman groups. Cryptology eprint Archives http://eprint.iacr.org, 2002. Number 2002/018.
D. Chaum. Zero-knowledge undeniable signatures (extended abstract). In Ivan B. Damgård, editor, Advances in Cryptology-EuroCrypt’ 90, volume 473 of Lecture Notes in Comput. Sci., pages 458–464, Berlin, 1990. Springer-Verlag.
D. Chaum and T. P. Pedersen. Wallet databases with observers. In Ernest F. Brickell, editor, Advances in Cryptology-Crypto’ 92, volume 740 of Lecture Notes in Comput. Sci., pages 89–105, Berlin, 1992. Springer-Verlag.
D. Chaum and H. van Antwerpen. Undeniable signatures. In Gilles Brassard, editor, Advances in Cryptology-Crypto’ 89, volume 435 of Lecture Notes in Comput. Sci., pages 212–217, Berlin, 1989. Springer-Verlag.
Q. Cheng and S. Uchiyama. Nonuniform polynomial time algorithm to solve decisional Diffie-Hellman problem in finite fields under conjecture. In CR-RSA 2002, number 2271 in Lecture Notes in Comput. Sci., pages 290–299. Springer, 2002.
Y. Choie, E. Jeong, and E. Lee. Supersingular hyperelliptic curve of genus 2 over finite fields. Cryptology eprint Archives http://eprint.iacr.org, 2002. Number 2002/032.
C. Cocks. An identity based encryption scheme based on quadratic residues. Cryptography and Coding, 2001. To appear, preprint available at http://www.cesg.-gov.uk/technology/id-pkc/media/ciren.pdf.
G. Frey, M. Müller, and H.-G. Rück. The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems. IEEE Transactions on Information Theory, 45(5):1717–1718, 1999.
S. D. Galbraith. Supersingular curves in cryptography. In C. Boyd, editor, Proceedings of ASIACRYPT’2001, volume 2248 of Lecture Notes in Comput. Sci., pages 495–513. Springer, 2001.
S. D. Galbraith, K. Harrison, and D. Soldera. Implementing the Tate pairing. In This Volume, 2002.
F. Hess. Exponent groups signature schemes and efficient identity based signature schemes based on pairings. Cryptology eprint Archives http://eprint.iacr.org, 2002. Number 2002/012.
J. Horwitz and B. Lynn. Toward hierarchical identity-based encryption. To appear at Eurocrypt 2002., May 2002.
A. Joux. A one round protocol for tripartite Diffie—Hellman. In Wieb Bosma, editor, Proceedings of the ANTS-IV conference, volume 1838 of Lecture Notes in Comput. Sci., pages 385–394. Springer, 2000.
A. Joux and L. Lercier. The function field sieve is quite special. In This Volume, 2002.
N. Koblitz. Elliptic curve cryptography: Which curves to use? Transparencies available at http://www.ipam.ucla.edu/publications/cry2002/cry2002nkoblitz.-pdf, January 2002. Talk given at the IPAM Cryptography Workshop.
N. Koblitz and A. Menezes. Obstacles to the torsion-subgroup attack on the decision Diffie-Hellman problem. Technical Report CORR 2002-05, CACR, 2002. Available at http://www.cacr.math.uwaterloo.ca/techreports.html.
A. Lentra and E. Verheul. The XTR public key system. In Mihir Bellare, editor, Proceedings of CRYPTO’2000, volume 1880 of Lecture Notes in Comput. Sci., pages 1–19. Springer, 2000.
U. Maurer and S. Wolf. The relationship between breaking the Diffie—Hellman protocol and computing discrete logarithms. SIAM J. Comput., 28(5):1689–1721, 1999.
U. M. Maurer and Y. Yacobi. Non-interative public-key cryptography. In Donald W. Davies, editor, Advances in Cryptology-EuroCrypt’ 91, volume 547 of Lecture Notes in Comput. Sci., pages 498–507, Berlin, 1991. Springer-Verlag.
A. Menezes, T. Okamoto, and S. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transaction on Information Theory, 39:1639–1646, 1993.
V. Miller. Short programs for functions on curves. Unpublished manuscript, 1986.
V. Miller. Use of elliptic curves in cryptography. In H. Williams, editor, Advances in Cryptology — CRYPTO’85, volume 218 of Lecture Notes in Comput. Sci., pages 417–428. Springer, 1986.
T. Okamoto and D. Pointcheval. The gap problems: a new class of problems for the security of cryptographic primitives. In Public Key Cryptography, PKC 2001, volume 1992 of Lecture Notes in Comput. Sci., pages 104–118. Springer, 2001.
K. Paterson. ID-based signatures from pairings on elliptic curves. Cryptology eprint Archives http://eprint.iacr.org, 2002. Number 2002/004.
K. Rubin and A. Silverberg. The best and worst of supersingular abelian varieties in cryptology. Cryptology eprint Archives http://eprint.iacr.org, 2002. Number 2002/006.
H. G. Rück and K. Nguyen. A comparison of the Weil and Tate pairing. preprint.
O. Schirokauer. The special function field sieve. Preprint.
I. Semaev. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Mathematics of Computation, 67:353–356, 1998.
A. Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and David Chaum, editors, Advances in Cryptology: Proceedings of Crypto’ 84, volume 196 of Lecture Notes in Comput. Sci., pages 47–53, Berlin, 1985. Springer-Verlag.
N. Smart. The discrete logarithm problem on elliptic curves of trace one. Journal of Cryptology, 12(3):193–196, 1999.
E. Verheul. Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. In B. Pfizmann, editor, Proceedings of EUROCRYPT’2001, volume 2045 of Lecture Notes in Comput. Sci., pages 195–210. Springer, 2001.
E. Verheul. Self-blindable credential certificates from the Weil pairing. In C. Boyd, editor, Proceedings of ASIACRYPT’2001, volume 2248 of Lecture Notes in Comput. Sci., pages 533–551. Springer, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Joux, A. (2002). The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems. In: Fieker, C., Kohel, D.R. (eds) Algorithmic Number Theory. ANTS 2002. Lecture Notes in Computer Science, vol 2369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45455-1_3
Download citation
DOI: https://doi.org/10.1007/3-540-45455-1_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43863-2
Online ISBN: 978-3-540-45455-7
eBook Packages: Springer Book Archive