Super-Optimal Pairings

Abstract:

In this paper, we construct super-optimal pairings with efficiently computable endomorphisms. We first consider elliptic curves E/F_q: y²=x³+B and construct super-optimal pairings with automorphisms and Frobenius endomorphisms. In the case of (3,k)=1, these super-optimal pairings can be computed using log₂ r/φ(3k) Miller iterations, with k the embedding degree. This Miller loop length is only half of that of optimal pairings. Then we consider elliptic curves E^'/F_q: y²=x³+u⁶B and give super-optimal pairings with efficiently computable endomorphisms constructed by Galbraith et al. In the case of (6, k)=1, these super-optimal pairings can be computed by log₂ r/φ(12k)Miller iterations, with k the embedding degree. This Miller loop length is only 1/4 of that of optimal pairings.

• Periodical: Applied Mechanics and Materials (Volume 281)
• Pages: 127-133
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.281.127
• Online since: January 2013
• Authors: Yan Feng Qi, Chun Ming Tang, Baoan Guo, Mao Zhi Xu
• Keywords: Elliptic Curves, Isogeny, Optimized Pairing, Pairing-Based Cryptography

References

[1] A. Joux, A one round protocol for tripartite Diffie-Hellman. In: Bosma, W. (ed. ) Algorithmic Number Theory SymposiumCANTS IV. LNCS, vol. 1838, pp.385-394. Springer, Heidelberg (2000).

DOI: 10.1007/10722028_23

[2] D. Boneh, M. K. Franklin, Identity-based encryption from the Weil pairing. In: Kilian, J. (ed. ) CRYPTO 2001. LNCS, vol. 2139, pp.213-229. Springer, Heidelberg (2001).

DOI: 10.1007/3-540-44647-8_13

[3] D. Boneh, B. Lynn, H. Shacham, Short signatures from the Weil pairing. In C. Boyd, editor, Proceedings of ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2001, 514-532.

DOI: 10.1007/3-540-45682-1_30

[4] V. S. Miller, Short programs for functions on curves (1986), http: /crypto. stanford. edu/miller/miller. pdf.

[5] V. S. Miller, The Weil pairing and its efficient calculation. Journal of Cryptology 17(4), 235-261 (2004).

[6] I. Duursma, H. S. Lee, Tate pairing implementation for hyperelliptic curves , In: Laih, C. -S. (ed. ) ASIACRYPT 2003. LNCS, vol. 2894, pp.111-123. Springer, Heidelberg (2003).

DOI: 10.1007/978-3-540-40061-5_7

[7] P. S. L. M. Barreto, S. Galbraith, C. OhEigeartaigh, M. Scott, Efficient pairing computation on supersingular abelian varieties. Designs, Codes and Cryptography 42(3), 239-271 (2007).

DOI: 10.1007/s10623-006-9033-6

[8] F. Hess, N. P. Smart, F. Vercauteren, The Eta Pairing Revisited. IEEE Transaction on Information Theory 52(10), 4595-4602 (2006).

DOI: 10.1109/tit.2006.881709

[9] S. Matsuda, N. Kanayama, F. Hess and E. Okamoto, Optimised ver-sions of the Ate and twisted Ate pairings. In The 11th IMA International Conference on Cryptography and Coding, volume 4887 of Lecture Notes in Computer Science, pages 302-312. Springer-Verlag, (2007).

DOI: 10.1007/978-3-540-77272-9_18

[10] C. A. Zhao, F. Zhang, J. Huang, A note on the Ate pairing, International Journal of Information Security, 7(6): 379-382, (2008).

[11] E. Lee, H. S. Lee, C. M. Park, Efficient and generalized pairing compu-tation on Abelian varieties, IEEE Trans. Inf. Theor., Volume 55 , Issue 4, Pagess 1793-1803, April (2009).

DOI: 10.1109/tit.2009.2013048

[12] C. A. Zhao, D. Xie, F. Zhang, J. Zhang, B. Chen, Computing bilinear pairings on elliptic curves with automorphisms. Designes, Codes and Cryptography. Published online: 27 March (2010).

DOI: 10.1007/s10623-010-9383-y

[13] C. A. Zhao, F. Zhang, Reducing the complexity of the Weil pair-ing computation, Cryptology ePrint Archive, Report 2008/212 (2008), http: /eprint. iacr. org/2008/212.

[14] F. Vercauteren, Optimal pairings. IEEE Transactions on Information Theory, 56(1): 455-461, January (2010).

DOI: 10.1109/tit.2009.2034881

[15] T. Iijima, K. Matsuo, J. Chao, S. Tsujii, Costruction of Frobenius Maps of Twist Elliptic Curves and its Application to Elliptic Scalar Multiplication, In: SCIS 2002, IEICE Japan, pp.699-702 (January 2002).

[16] S. D. Galbraith, X. Lin, M. Scott, Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves. In: EUROCRYPT 2009. LNCS, Vol. 5479, pp.518-535. Springer, Heidelberg (2009).

DOI: 10.1007/978-3-642-01001-9_30

[17] Y. Nogami, M. Akane, Y. Sakemi, H. Kato, Y. Morikawa, Integer variable X-based ate pairing. In: Galbraith, S.D., Paterson, K.G. (eds. ) Pairing 2008. LNCS, vol. 5209, pp.178-191. Springer, Heidelberg (2008).

DOI: 10.1007/978-3-540-85538-5_13

[18] R. Avanz, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen and F. Vercauteren, Handbook of elliptic and hyperelliptic curve cryptography. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, (2006).

DOI: 10.1201/9781420034981

[19] J. H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, (1986).