Abstract
Pairing-based cryptosystems rely on bilinear non-degenerate maps called pairings, such as the Tate and Weil pairings defined over certain elliptic curve groups. In this paper we show how to compress pairing values, how to couple this technique with that of point compression, and how to benefit from the compressed representation to speed up exponentiations involving pairing values, as required in many pairing based protocols.
Chapter PDF
Similar content being viewed by others
References
Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient algorithms for pairing-based cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–368. Springer, Heidelberg (2002)
Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 263–273. Springer, Heidelberg (2003)
Barreto, P.S.L.M., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, Springer, Heidelberg (2004) (to appear)
Bleichenbacher, D., Bosma, W., Lenstra, A.K.: Some remarks on lucas-based cryptosystems. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 386–396. Springer, Heidelberg (1995)
Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. SIAM Journal of Computing 32(3), 586–615 (2003)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Cryptology ePrint Archive, Report 2003/143 (2003), Available from http://eprint.iacr.org/2003/143
Brouwer, E., Pellikaan, R., Verheul, E.R.: Doing more with fewer bits. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 321–332. Springer, Heidelberg (1999)
Carlitz, L.: Recurrences of the third order and related combinatorial identities. Fibonacci Quarterly 16(1), 11–18 (1978)
Dupont, R., Enge, A., Morain, F.: Building curves with arbitrary small MOV degree over finite prime fields. Cryptology ePrint Archive, Report 2002/094 (2002), Available from http://eprint.iacr.org/2002/094
Duursma, I., Lee, H.-S.: Tate pairing implementation for hyperelliptic curves y2 = xp−x+d. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 111–123. Springer, Heidelberg (2003)
Galbraith, S., Harrison, K., Soldera, D.: Implementing the Tate pairing. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp. 324–337. Springer, Heidelberg (2002)
Galbraith, S., Harrison, K., Soldera, D.: Using primitive subgroups to do more with fewer bits. In: Buell, D.A. (ed.) ANTS 2004. LNCS, vol. 3076, pp. 18–41. Springer, Heidelberg (2004)
Galbraith, S., Hopkins, H., Shparlinski, I.: Secure bilinear diffie-hellman bits. Cryptology ePrint Archive, Report 2002/155 (2002), Available from http://eprint.iacr.org/2002/155
Gordon, D.: A survey of fast exponentiation methods. Journal of Algorithms 27, 129–146 (2002)
Hoffman, K., Kunze, R.: Linear Algebra, 2nd edn. Prentice Hall, New Jersey (1971)
Joux, A.: A one-round protocol for tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)
Joye, M., Quisquater, J.J.: Efficient computation of full Lucas sequences. Electronics Letters 32(6), 537–538 (1996)
Joye, M., Yen, S.: The montgomery powering ladder. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003)
Lehmer, D.H.: Computer technology applied to the theory of numbers. In: LeVeque, W.J. (ed.) Studies in Number Theory. MAA Studies in Mathematics, vol. 6, pp. 117–151. Math. Assoc. Amer. (1969) (distributed by Prentice-Hall, Englewood Cliffs, N.J.)
Lenstra, K., Verheul, E.R.: The xtr public key system. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 1–19. Springer, Heidelberg (2000)
Lidl, R., Niederreiter, H.: Finite Fields. In: Encyclopedia of Mathematics and its Applications, 2nd edn., vol. 20, Cambridge University Press, Cambridge (1997)
Menezes, A.: Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers, Dordrecht (1993)
Miller, V.S.: Short programs for functions on curves. Unpublished manuscript (1986), Available from http://crypto.stanford.edu/miller/miller.pdf
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals E84-A(5), 1234–1243 (2001)
Montgomery, P.L.: Speeding the pollard and elliptic curve methods of factorization. Mathematics of Computation 48(177), 243–264 (1987)
Nalla, D., Reddy, K.C.: Signcryption scheme for identity-based cryptosystems. Cryptology ePrint Archive, Report 2003/066 (2002), Available from http://eprint.iacr.org/2003/066
Silverman, J.H.: The Arithmetic of Elliptic Curves. In: Graduate Texts in Mathematics, vol. 106, Springer, Berlin (1986)
Smart, N.P.: An identity based authenticated key agreement protocol based on the weil pairing. Electronics Letters 38, 630–632 (2002)
Stam, M., Lenstra, A.K.: Speeding up XTR. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 125–143. Springer, Heidelberg (2001)
Yen, S.M., Laih, C.S.: Fast algorithms for LUC digital signature computation. IEE Proceedings on Computers and Digital Techniques 142(2), 165–169 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Scott, M., Barreto, P.S.L.M. (2004). Compressed Pairings. In: Franklin, M. (eds) Advances in Cryptology – CRYPTO 2004. CRYPTO 2004. Lecture Notes in Computer Science, vol 3152. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28628-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-28628-8_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22668-0
Online ISBN: 978-3-540-28628-8
eBook Packages: Springer Book Archive