# American Institute of Mathematical Sciences

February  2013, 7(1): 103-111. doi: 10.3934/amc.2013.7.103

## Generalizations of Verheul's theorem to asymmetric pairings

 1 Department of Mathematics, Bilkent University, Bilkent, Ankara 06800, Turkey 2 Google, Inc., 1600 Amphitheater Parkway, Mountain View, California 94043, United States 3 Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1

Received  June 2012 Revised  September 2012 Published  January 2013

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.
Citation: Koray Karabina, Edward Knapp, Alfred Menezes. Generalizations of Verheul's theorem to asymmetric pairings. Advances in Mathematics of Communications, 2013, 7 (1) : 103-111. doi: 10.3934/amc.2013.7.103
##### References:
 [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.

show all references

##### References:
 [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.
 [1] Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete and Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557 [2] Santos González, Llorenç Huguet, Consuelo Martínez, Hugo Villafañe. Discrete logarithm like problems and linear recurring sequences. Advances in Mathematics of Communications, 2013, 7 (2) : 187-195. doi: 10.3934/amc.2013.7.187 [3] Gabriella Pinzari. Global Kolmogorov tori in the planetary $\boldsymbol N$-body problem. Announcement of result. Electronic Research Announcements, 2015, 22: 55-75. doi: 10.3934/era.2015.22.55 [4] John Hubbard, Yulij Ilyashenko. A proof of Kolmogorov's theorem. Discrete and Continuous Dynamical Systems, 2004, 10 (1&2) : 367-385. doi: 10.3934/dcds.2004.10.367 [5] Rabah Amir, Igor V. Evstigneev. On Zermelo's theorem. Journal of Dynamics and Games, 2017, 4 (3) : 191-194. doi: 10.3934/jdg.2017011 [6] Hahng-Yun Chu, Se-Hyun Ku, Jong-Suh Park. Conley's theorem for dispersive systems. Discrete and Continuous Dynamical Systems - S, 2015, 8 (2) : 313-321. doi: 10.3934/dcdss.2015.8.313 [7] Sergei Ivanov. On Helly's theorem in geodesic spaces. Electronic Research Announcements, 2014, 21: 109-112. doi: 10.3934/era.2014.21.109 [8] Madhurima Mukhopadhyay, Palash Sarkar, Shashank Singh, Emmanuel Thomé. New discrete logarithm computation for the medium prime case using the function field sieve. Advances in Mathematics of Communications, 2022, 16 (3) : 449-464. doi: 10.3934/amc.2020119 [9] Hiroshi Isozaki, Hisashi Morioka. A Rellich type theorem for discrete Schrödinger operators. Inverse Problems and Imaging, 2014, 8 (2) : 475-489. doi: 10.3934/ipi.2014.8.475 [10] Pengyan Wang, Pengcheng Niu. Liouville's theorem for a fractional elliptic system. Discrete and Continuous Dynamical Systems, 2019, 39 (3) : 1545-1558. doi: 10.3934/dcds.2019067 [11] V. Niţicâ. Journé's theorem for $C^{n,\omega}$ regularity. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 413-425. doi: 10.3934/dcds.2008.22.413 [12] Jacques Féjoz. On "Arnold's theorem" on the stability of the solar system. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3555-3565. doi: 10.3934/dcds.2013.33.3555 [13] Lena Noethen, Sebastian Walcher. Tikhonov's theorem and quasi-steady state. Discrete and Continuous Dynamical Systems - B, 2011, 16 (3) : 945-961. doi: 10.3934/dcdsb.2011.16.945 [14] Dmitry Kleinbock, Barak Weiss. Dirichlet's theorem on diophantine approximation and homogeneous flows. Journal of Modern Dynamics, 2008, 2 (1) : 43-62. doi: 10.3934/jmd.2008.2.43 [15] Fatiha Alabau-Boussouira, Piermarco Cannarsa. A constructive proof of Gibson's stability theorem. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 611-617. doi: 10.3934/dcdss.2013.6.611 [16] Mateusz Krukowski. Arzelà-Ascoli's theorem in uniform spaces. Discrete and Continuous Dynamical Systems - B, 2018, 23 (1) : 283-294. doi: 10.3934/dcdsb.2018020 [17] Shalosh B. Ekhad and Doron Zeilberger. Proof of Conway's lost cosmological theorem. Electronic Research Announcements, 1997, 3: 78-82. [18] Florian Wagener. A parametrised version of Moser's modifying terms theorem. Discrete and Continuous Dynamical Systems - S, 2010, 3 (4) : 719-768. doi: 10.3934/dcdss.2010.3.719 [19] Xue Meng, Miaomiao Gao, Feng Hu. New proofs of Khinchin's law of large numbers and Lindeberg's central limit theorem –PDE's approach. Mathematical Foundations of Computing, 2022  doi: 10.3934/mfc.2022017 [20] Torsten Lindström. Discrete models and Fisher's maximum principle in ecology. Conference Publications, 2003, 2003 (Special) : 571-579. doi: 10.3934/proc.2003.2003.571

2021 Impact Factor: 1.015