Abstract
Although identity based cryptography offers many functional advantages over conventional public key alternatives, the computational costs are significantly greater. The core computational task is evaluation of a bilinear map, or pairing, over elliptic curves. In this paper we prototype and evaluate polynomial and normal basis field arithmetic on an FPGA device and use it to construct a hardware accelerator for pairings over fields of characteristic three. The performance of our prototype improves roughly ten-fold on previous known hardware implementations and orders of magnitude on the fastest known software implementation. As a result we reason that even on constrained devices one can usefully evaluate the pairing, a fact that gives credence to the idea that identity based cryptography is an ideal partner for identity aware smart-cards.
The work described in this paper has been supported in part by the European Commission through the IST Programme under Contract IST-2002-507932 ECRYPT. The information in this document reflects only the author’s views, is provided as is and no guarantee or warranty is given that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability.
Chapter PDF
Similar content being viewed by others
References
Barreto, P.S.L.M.: A Note On Efficient Computation Of Cube Roots In Characteristic 3. In: Cryptology ePrint Archive, Report 2004/305 (2004)
Barreto, P.S.L.M., Galbraith, S., O’hEigeartaigh, C., Scott, M.: Efficient Pairing Computation on Supersingular Abelian Varieties. In: Cryptology ePrint Archive, Report 2004/375 (2004)
Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing Elliptic Curves with Prescribed Embedding Degree. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 257–267. Springer, Heidelberg (2003)
Barreto, P.S.L.M., Kim, H., 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., Naehrig, M.: Pairing-Friendly Elliptic Curves of Prime Order. In: Cryptology ePrint Archive, Report 2005/133 (2005)
Bertoni, G., Guajardo, J., Kumar, S., Orlando, G., Paar, C., Wollinger, T.: Efficient GF(p m) Arithmetic Architectures for Cryptographic Applications. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 158–175. Springer, Heidelberg (2003)
Blake, I.F., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography. Cambridge University Press, Cambridge (2004)
Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. SIAM Journal on Computing 32(3), 586–615 (2003)
Clark, W., Liang, J.: On Arithmetic Weight for a General Radix Representation of Integers. IEEE Transactions on Information Theory 19, 823–826 (1973)
Duursma, I., Lee, H.: Tate Pairing Implementation for Hyperelliptic Curves y 2 = x p − x + d. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 111–123. Springer, Heidelberg (2003)
Dutta, R., Barua, R., Sarkar, P.: Pairing-Based Cryptographic Protocols: A Survey. In: Cryptology ePrint Archive, Report 2004/064 (2004)
Galbraith, S.: Supersingular Curves in Cryptography. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 495–513. Springer, Heidelberg (2001)
Granger, R., Page, D., Stam, M.: Hardware and Software Normal Basis Arithmetic for Pairing Based Cryptography in Characteristic Three. In: Cryptology ePrint Archive, Report 2004/157 (2004)
Granger, R., Page, D., Stam, M.: On Small Characteristic Algebraic Tori in Pairing-Based Cryptography. In: Cryptology ePrint Archive, Report 2004/132 (2004)
Harrison, K., Page, D., Smart, N.P.: Software Implementation of Finite Fields of Characteristic Three, for use in Pairing Based Cryptosystems. LMS Journal of Computation and Mathematics 5(1), 181–193 (2002)
Itoh, T., Tsujii, S.: A Fast Algorithm for Computing Multiplicative Inverses in GF(2n) Using Normal Bases. Information and Computation 78, 171–177 (1988)
Kerins, T., Popovici, E., Marnane, W.P.: Algorithms and Architectures for Use in FPGA Implementations of Identity Based Encryption Schemes. In: Becker, J., Platzner, M., Vernalde, S. (eds.) FPL 2004. LNCS, vol. 3203, pp. 74–83. Springer, Heidelberg (2004)
Kwon, S.: Efficient Tate Pairing Computation for Supersingular Elliptic Curves over Binary Fields. In: Cryptology ePrint Archive, Report 2004/303 (2004)
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)
Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Transactions on Information Theory 39, 1639–1646 (1993)
Nöcker, M.: Data Structures for Parallel Exponentiation in Finite Fields. PhD Thesis, Universität Paderborn (2001)
Page, D., Smart, N.P.: Hardware Implementation of Finite Fields of Characteristic Three. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 529–539. Springer, Heidelberg (2003)
Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems Based on Pairings. In: Symposium on Cryptography and Information Security (SCIS) (2000)
Silverman, J.: The Arithmetic of Elliptic Curves. Springer, Heidelberg (1986)
Shamir, A.: Identity-Based Cryptosystems and Signature Schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
Takagi, T., Yen, S.-M., Wu, B.-C.: Radix-r Non-Adjacent Form. In: Zhang, K., Zheng, Y. (eds.) ISC 2004. LNCS, vol. 3225, pp. 99–110. Springer, Heidelberg (2004)
Voltage Security, Press Release. Gemplus Develops the World’s First Identity-Based Encryption for Smart Cards, Available from, http://www.voltage.com/about/pressreleases/PR041102.htm
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grabher, P., Page, D. (2005). Hardware Acceleration of the Tate Pairing in Characteristic Three. In: Rao, J.R., Sunar, B. (eds) Cryptographic Hardware and Embedded Systems – CHES 2005. CHES 2005. Lecture Notes in Computer Science, vol 3659. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11545262_29
Download citation
DOI: https://doi.org/10.1007/11545262_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28474-1
Online ISBN: 978-3-540-31940-5
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science