Article Contents
Article Contents

Generalizations of Verheul's theorem to asymmetric pairings

• For symmetric pairings $e : \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$, Verheul proved that the existence of an efficiently-computable isomorphism $\phi : \mathbb{G}_T \rightarrow \mathbb{G}$ implies that the Diffie-Hellman problems in $\mathbb{G}$ and $\mathbb{G}_T$ can be efficiently solved. In this paper, we explore the implications of the existence of efficiently-computable isomorphisms $\phi_1 : \mathbb{G}_T \rightarrow \mathbb{G}_1$ and $\phi_2 : \mathbb{G}_T \rightarrow \mathbb{G}_2$ for asymmetric pairings $e : \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. We also give a simplified proof of Verheul's theorem.
Mathematics Subject Classification: 94A60.

 Citation:

•  [1] D. Aranha, K. Karabina, P. Longa, C. Gebotys and J. López, Faster explicit formulas for computing pairings over ordinary curves, in "Advances in Cryptology - EUROCRYPT 2011,'' (2011), 48-68. [2] P. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order, in "Selected Areas in Cryptography - SAC 2005,'' (2006), 319-331. [3] D. Boneh, B. Lynn, and H. Shacham, Short signatures from the Weil pairing, J. Cryptology, 17 (2004), 297-319.doi: 10.1007/s00145-004-0314-9. [4] D. Brown and R. Gallant, The static Diffie-Hellman problem, available online at http://eprint.iacr.org/2004/306 [5] J. Cheon, Security analysis of the Strong Diffie-Hellman problem, in "Advances in Cryptology - EUROCRYPT 2006,'' (2006), 1-11. [6] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, 30 (1984), 587-594. [7] T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over $GF(p^{2})$, IEEE Trans. Inform. Theory, 31 (1985), 473-481. [8] G. Frey and H. Rück, A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comput., 62 (1994), 865-874. [9] S. Galbraith, Pairings, in "Advances in Elliptic Curve Cryptography'' (eds. I. Blake, G. Seroussi and N. Smart), Cambridge University Press, 2005. [10] S. Galbraith, C. Ó hÉigeartaigh and C. Sheedy, Simplified pairing computation and security implications, J. Math. Crypt., 1 (2007), 267-281. [11] S. Galbraith, F. Hess and F. Vercauteren, Aspects of pairing inversion, IEEE Trans. Inform. Theory, 54 (2008), 5719-5728.doi: 10.1109/TIT.2008.2006431. [12] S. Galbraith, K. Paterson and N. Smart, Pairings for cryptographers, Discr. Appl. Math., 156 (2008), 3113-3121.doi: 10.1016/j.dam.2007.12.010. [13] Z. Hu, M. Xu and Z. Zhou, A generalization of Verheul's theorem for some ordinary curves, in "Inscrypt 2010,'' (2011), 105-114. [14] N. Koblitz and A. Menezes, Pairing-based cryptography at high security levels, in "Cryptography and Coding: 10th IMA International Conference,'' (2005), 13-36. [15] A. Lenstra and E. Verheul, The XTR public key system, in "Advances in Cryptology - CRYPTO 2000,'' (2000), 1-19. [16] A. Menezes, T. Okamoto and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory, 39 (1993), 1639-1646.doi: 10.1109/18.259647. [17] A. Menezes and S. Vanstone, ECSTR (XTR): Elliptic curve singular trace representation, in "Rump Session of Crypto 2000''. [18] D. Mireles Morales, Cheon's algorithm, pairing inversion and the discrete logarithm problem, available online at http://eprint.iacr.org/2008/300 [19] D. Moody, The Diffie-Hellman problem and generalization of Verheul's theorem, Des. Codes Crypt., 52 (2009), 381-390. [20] J. Pollard, Monte Carlo methods for index computation mod $p$, Math. Comput., 32 (1978), 918-924. [21] T. Satoh, On degrees of polynomial interpolations related to elliptic curve cryptography, in "WCC 2005,'' (2006), 155-163. [22] T. Satoh, On polynomial interpolations related to Verheul homomorphisms, LMS J. Comput. Math., 9 (2006), 135-158. [23] T. Satoh, Closed formulae for the Weil pairing inversion, Finite Fields Appl., 14 (2008), 743-765.doi: 10.1016/j.ffa.2007.12.003. [24] E. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, J. Cryptology, 17 (2004), 277-296.doi: 10.1007/s00145-004-0313-x.