Abstract
In this article we propose a study of the modified Tate pairing in characteristics two and three. Starting from the η T pairing introduced by Barreto et al. [1], we detail various algorithmic improvements in the case of characteristic two. As far as characteristic three is concerned, we refer to the survey by Beuchat et al. [5]. We then show how to get back to the modified Tate pairing at almost no extra cost. Finally, we explore the trade-offs involved in the hardware implementation of this pairing for both characteristics two and three. From our experiments, characteristic three appears to have a slight advantage over characteristic two.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Barreto, P.S.L.M., Galbraith, S.D., ÓhÉigeartaigh, C., Scott, M.: Efficient pairing computation on supersingular Abelian varieties. Designs, Codes and Cryptography 42, 239–271 (2007)
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)
Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E.: Arithmetic operators for pairing-based cryptography. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 239–255. Springer, Heidelberg (2007)
Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E., Rodríguez-Henríquez, F.: A comparison between hardware accelerators for the modified Tate pairing over \(\mathbb{F}_{2^m}\) and \(\mathbb{F}_{3^m}\). Cryptology ePrint Archive, Report 2008/115 (2008)
Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E., Shirase, M., Takagi, T.: Algorithms and arithmetic operators for computing the η T pairing in characteristic three. IEEE Transactions on Computers 57(11) (November 2008) (to appear) An extended version is available as Report 2007/417 of the Cryptology ePrint Archive
Beuchat, J.-L., Shirase, M., Takagi, T., Okamoto, E.: An algorithm for the η T pairing calculation in characteristic three and its hardware implementation. In: Kornerup, P., Muller, J.-M. (eds.) Proceedings of the 18th IEEE Symposium on Computer Arithmetic, pp. 97–104. IEEE Computer Society, Los Alamitos (2007)
Duursma, I., Lee, H.S.: 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)
Fong, K., Hankerson, D., López, J., Menezes, A.: Field inversion and point halving revisited. IEEE Transactions on Computers 53(8), 1047–1059 (2004)
Frey, G., Rück, H.-G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation 62(206), 865–874 (1994)
Galbraith, S.D., 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)
Grabher, P., Page, D.: Hardware acceleration of the Tate pairing in characteristic three. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 398–411. Springer, Heidelberg (2005)
Granger, R., Page, D., Smart, N.P.: High security pairing-based cryptography revisited. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 480–494. Springer, Heidelberg (2006)
Granger, R., Page, D., Stam, M.: On small characteristic algebraic tori in pairing-based cryptography. LMS Journal of Computation and Mathematics 9, 64–85 (2006)
Hess, F., Smart, N., Vercauteren, F.: The Eta pairing revisited. IEEE Transactions on Information Theory 52(10), 4595–4602 (2006)
Itoh, T., Tsujii, S.: A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases. Information and Computation 78, 171–177 (1988)
Jiang, J.: Bilinear pairing (Eta_T Pairing) IP core. Technical report, City University of Hong Kong – Department of Computer Science (May 2007)
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)
Keller, M., Kerins, T., Crowe, F., Marnane, W.P.: FPGA implementation of a GF(2m) Tate pairing architecture. In: Bertels, K., Cardoso, J.M.P., Vassiliadis, S. (eds.) ARC 2006. LNCS, vol. 3985, pp. 358–369. Springer, Heidelberg (2006)
Keller, M., Ronan, R., Marnane, W.P., Murphy, C.: Hardware architectures for the Tate pairing over GF(2m). Computers and Electrical Engineering 33(5–6), 392–406 (2007)
Kerins, T., Marnane, W.P., Popovici, E.M., Barreto, P.S.L.M.: Efficient hardware for the Tate pairing calculation in characteristic three. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 412–426. Springer, Heidelberg (2005)
Koblitz, N., Menezes, A.: Pairing-based cryptography at high security levels. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005)
Kwon, S.: Efficient Tate pairing computation for elliptic curves over binary fields. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 134–145. Springer, Heidelberg (2005)
Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing elliptic curves logarithms to logarithms in a finite field. IEEE Transactions on Information Theory 39(5), 1639–1646 (1993)
Miller, V.S.: Short programs for functions on curves (1986), http://crypto.stanford.edu/miller
Miller, V.S.: The Weil pairing, and its efficient calculation. Journal of Cryptology 17(4), 235–261 (2004)
Mitsunari, S., Sakai, R., Kasahara, M.: A new traitor tracing. IEICE Trans. Fundamentals E85-A(2), 481–484 (2002)
Rodríguez-Henríquez, F., Morales-Luna, G., López, J.: Low-complexity bit-parallel square root computation over GF(2m) for all trinomials. IEEE Transactions on Computers 57(4), 472–480 (2008)
Ronan, R., Murphy, C., Kerins, T., ÓhÉigeartaigh, C., Barreto, P.S.L.M.: A flexible processor for the characteristic 3 η T pairing. Int. J. High Performance Systems Architecture 1(2), 79–88 (2007)
Ronan, R., ÓhÉigeartaigh, C., Murphy, C., Scott, M., Kerins, T.: FPGA acceleration of the Tate pairing in characteristic 2. In: Proceedings of the IEEE International Conference on Field Programmable Technology – FPT 2006, pp. 213–220. IEEE, Los Alamitos (2006)
Ronan, R., ÓhÉigeartaigh, C., Murphy, C., Scott, M., Kerins, T.: Hardware acceleration of the Tate pairing on a genus 2 hyperelliptic curve. Journal of Systems Architecture 53, 85–98 (2007)
Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: 2000 Symposium on Cryptography and Information Security (SCIS 2000), Okinawa, Japan, pp. 26–28 (January 2000)
Scott, M.: Optimal irreducible polynomials for GF(2m) arithmetic. Cryptology ePrint Archive, Report 2007/192 (2007)
Shu, C., Kwon, S., Gaj, K.: FPGA accelerated Tate pairing based cryptosystem over binary fields. In: Proceedings of the IEEE International Conference on Field Programmable Technology – FPT 2006, pp. 173–180. IEEE, Los Alamitos (2006)
Song, L., Parhi, K.K.: Low energy digit-serial/parallel finite field multipliers. Journal of VLSI Signal Processing 19(2), 149–166 (1998)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beuchat, JL., Brisebarre, N., Detrey, J., Okamoto, E., Rodríguez-Henríquez, F. (2008). A Comparison between Hardware Accelerators for the Modified Tate Pairing over \(\mathbb{F}_{2^m}\) and \(\mathbb{F}_{3^m}\) . In: Galbraith, S.D., Paterson, K.G. (eds) Pairing-Based Cryptography – Pairing 2008. Pairing 2008. Lecture Notes in Computer Science, vol 5209. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85538-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-85538-5_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85503-3
Online ISBN: 978-3-540-85538-5
eBook Packages: Computer ScienceComputer Science (R0)