Faster Ate Pairing Computation over Pairing-Friendly Elliptic Curves Using GLV Decomposition

ETRI Journal

关键词: elliptic curves;    GLV decomposition;    ate pairing;    Pairing computation;   

Others  :  1193709
DOI  :  10.4218/etrij.13.0112.0756

【 摘 要 】

The preexisting pairings ate, ate_i, R-ate, and optimal-ate use q-expansion, where q is the size of the defining field for the elliptic curves. Elliptic curves with small embedding degrees only allow a few of these pairings. In such cases, efficiently computable endomorphisms can be used, as in [11] and [12]. They used the endomorphisms that have characteristic polynomials with very small coefficients, which led to some restrictions in finding various pairing-friendly curves. To construct more pairing-friendly curves, we consider μ-expansion using the Gallant-Lambert-Vanstone (GLV) decomposition method, where μ is an arbitrary integer. We illustrate some pairing-friendly curves that provide more efficient pairing from the μ-expansion than from the ate pairing. The proposed method can achieve timing results at least 20% faster than the ate pairing.

   

【 参考文献 】

• [1]P.S.L.M. Barreto et al., "Efficient Algorithms for Pairing-Based Cryptosystems," Adv. Cryptography: Eurocrypt, LNCS, vol. 2442, 2002, pp. 354-368.
• [2]S. Galbraith, K. Harrison, and S. Soldera, "Implementing the Tate Pairing," Algorithmic Number Theory Symp. V, LNCS, vol. 2369, 2002, pp. 324-337.
• [3]I. Duursma and H.-S. Lee, "Tate Pairing Implementation for Hyperelliptic Curves y2 = xp–x+d," Adv. Cryptography — Asiacrypt, LNCS, vol. 2894, 2003, pp. 111-123.
• [4]F. Hess, N.P. Smart, and F. Vercauteren, "The Eta Pairing Revisited," IEEE Trans. Inf. Theory, vol. 52, 2006, pp. 4595-4602.
• [5]P.S.L.M. Barreto et al., "Efficient Pairing Computation on Supersingular Abelian Varieties," Design, Codes, Cryptography, vol. 42, 2007, pp. 239-271.
• [6]C. Zhao, F. Zhang, and J. Huang, "A Note on the Ate Pairing, Int. J. Inf. Security, vol. 7, no. 6, 2008, pp. 379-382.
• [7]E. Lee, H.-S. Lee, C.M. Park, "Efficient and Generalized Pairing Computation on Abelian Varieties," IEEE Trans. Inf. Theory, vol. 55, no. 4, 2009, pp. 1793-1803.
• [8]F. Vercauteren, "Optimal Pairings," IEEE Trans. Inf. Theory, vol. 56, no. 1, 2010, pp. 455-461.
• [9]V. Miller, "The Weil Pairing, and Its Efficient Calculation," J. Cryptology, vol. 17, 2004, pp. 235-261.
• [10]R.P. Gallant, R.J. Lambert, and S.A. Vanstone, "Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms," Crypto, LNCS, vol. 2139, 2001, pp. 190-200.
• [11]M. Scott, "Faster Pairings Using as Elliptic Curves with an Efficient Endomorphism," Indocrypto, LNCS, vol. 3797, 2005, pp. 258-269.
• [12]S. Ionica and A. Joux, "Pairing Computation on Elliptic Curves with Efficiently Computable Endomorphism and Small Embedding Degree," Pairing, LNCS, vol. 6487, 2010, pp. 435-449.
• [13]C.A. Zhao et al., "Computing Bilinear Pairings on Elliptic Curves with Automorphisms," Designs, Codes, Cryptography, vol. 58, 2011, pp. 35-44.
• [14]S. Galbraith and M. Scott, "Exponentiation in Pairing Friendly Groups Using Homomorphisms," Pairing, LNCS, vol. 5209, 2008, pp. 211-224.
• [15]S. Galbraith, X. Lin, and M. Scott, "Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves," J. Cryptology, vol. 24, no. 3, 2011, pp. 446-469.
• [16]F. Sica, M. Ciet, and J-J. Quisquater, "Analysis of the Gallant-Lambert-Vanstone Method based on Efficient Endomorphisms: Elliptic and Hyperelliptic Curves," Proc. Sel. Areas Cryptography, LNCS, vol. 2595, 2002, pp. 21-36.
• [17]C. Cocks and R.G.E. Pinch, "Identity-Based Cryptosystems Based on the Weil Pairing," unpublished manuscript, 2001.
• [18]D. Freeman, M. Scott, and E. Teske, "A Taxonomy of Pairing-Friendly Elliptic Curves," J. Cryptology, vol. 23, no. 2, 2010, pp. 224-280.
• [19]MAGMA Computational Algebra System MAGMA version V2.18-8, 2012. http://magma.maths.usyd.edu.au/magma/