# 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, (2011), 48. Google Scholar [2] P. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order,, in, (2006), 319. Google Scholar [3] D. Boneh, B. Lynn, and H. Shacham, Short signatures from the Weil pairing,, J. Cryptology, 17 (2004), 297. doi: 10.1007/s00145-004-0314-9. Google Scholar [4] D. Brown and R. Gallant, The static Diffie-Hellman problem,, available online at \url{http://eprint.iacr.org/2004/306}, (). Google Scholar [5] J. Cheon, Security analysis of the Strong Diffie-Hellman problem,, in, (2006), 1. Google Scholar [6] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two,, IEEE Trans. Inform. Theory, 30 (1984), 587. Google Scholar [7] T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over $GF(p^{2})$,, IEEE Trans. Inform. Theory, 31 (1985), 473. Google Scholar [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. Google Scholar [9] S. Galbraith, Pairings,, in, (2005). Google Scholar [10] S. Galbraith, C. Ó hÉigeartaigh and C. Sheedy, Simplified pairing computation and security implications,, J. Math. Crypt., 1 (2007), 267. Google Scholar [11] S. Galbraith, F. Hess and F. Vercauteren, Aspects of pairing inversion,, IEEE Trans. Inform. Theory, 54 (2008), 5719. doi: 10.1109/TIT.2008.2006431. Google Scholar [12] S. Galbraith, K. Paterson and N. Smart, Pairings for cryptographers,, Discr. Appl. Math., 156 (2008), 3113. doi: 10.1016/j.dam.2007.12.010. Google Scholar [13] Z. Hu, M. Xu and Z. Zhou, A generalization of Verheul's theorem for some ordinary curves,, in, (2011), 105. Google Scholar [14] N. Koblitz and A. Menezes, Pairing-based cryptography at high security levels,, in, (2005), 13. Google Scholar [15] A. Lenstra and E. Verheul, The XTR public key system,, in, (2000), 1. Google Scholar [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. doi: 10.1109/18.259647. Google Scholar [17] A. Menezes and S. Vanstone, ECSTR (XTR): Elliptic curve singular trace representation,, in, (2000). Google Scholar [18] D. Mireles Morales, Cheon's algorithm, pairing inversion and the discrete logarithm problem,, available online at \url{http://eprint.iacr.org/2008/300}, (). Google Scholar [19] D. Moody, The Diffie-Hellman problem and generalization of Verheul's theorem,, Des. Codes Crypt., 52 (2009), 381. Google Scholar [20] J. Pollard, Monte Carlo methods for index computation mod $p$,, Math. Comput., 32 (1978), 918. Google Scholar [21] T. Satoh, On degrees of polynomial interpolations related to elliptic curve cryptography,, in, (2006), 155. Google Scholar [22] T. Satoh, On polynomial interpolations related to Verheul homomorphisms,, LMS J. Comput. Math., 9 (2006), 135. Google Scholar [23] T. Satoh, Closed formulae for the Weil pairing inversion,, Finite Fields Appl., 14 (2008), 743. doi: 10.1016/j.ffa.2007.12.003. Google Scholar [24] E. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems,, J. Cryptology, 17 (2004), 277. doi: 10.1007/s00145-004-0313-x. Google Scholar

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, (2011), 48. Google Scholar [2] P. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order,, in, (2006), 319. Google Scholar [3] D. Boneh, B. Lynn, and H. Shacham, Short signatures from the Weil pairing,, J. Cryptology, 17 (2004), 297. doi: 10.1007/s00145-004-0314-9. Google Scholar [4] D. Brown and R. Gallant, The static Diffie-Hellman problem,, available online at \url{http://eprint.iacr.org/2004/306}, (). Google Scholar [5] J. Cheon, Security analysis of the Strong Diffie-Hellman problem,, in, (2006), 1. Google Scholar [6] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two,, IEEE Trans. Inform. Theory, 30 (1984), 587. Google Scholar [7] T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over $GF(p^{2})$,, IEEE Trans. Inform. Theory, 31 (1985), 473. Google Scholar [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. Google Scholar [9] S. Galbraith, Pairings,, in, (2005). Google Scholar [10] S. Galbraith, C. Ó hÉigeartaigh and C. Sheedy, Simplified pairing computation and security implications,, J. Math. Crypt., 1 (2007), 267. Google Scholar [11] S. Galbraith, F. Hess and F. Vercauteren, Aspects of pairing inversion,, IEEE Trans. Inform. Theory, 54 (2008), 5719. doi: 10.1109/TIT.2008.2006431. Google Scholar [12] S. Galbraith, K. Paterson and N. Smart, Pairings for cryptographers,, Discr. Appl. Math., 156 (2008), 3113. doi: 10.1016/j.dam.2007.12.010. Google Scholar [13] Z. Hu, M. Xu and Z. Zhou, A generalization of Verheul's theorem for some ordinary curves,, in, (2011), 105. Google Scholar [14] N. Koblitz and A. Menezes, Pairing-based cryptography at high security levels,, in, (2005), 13. Google Scholar [15] A. Lenstra and E. Verheul, The XTR public key system,, in, (2000), 1. Google Scholar [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. doi: 10.1109/18.259647. Google Scholar [17] A. Menezes and S. Vanstone, ECSTR (XTR): Elliptic curve singular trace representation,, in, (2000). Google Scholar [18] D. Mireles Morales, Cheon's algorithm, pairing inversion and the discrete logarithm problem,, available online at \url{http://eprint.iacr.org/2008/300}, (). Google Scholar [19] D. Moody, The Diffie-Hellman problem and generalization of Verheul's theorem,, Des. Codes Crypt., 52 (2009), 381. Google Scholar [20] J. Pollard, Monte Carlo methods for index computation mod $p$,, Math. Comput., 32 (1978), 918. Google Scholar [21] T. Satoh, On degrees of polynomial interpolations related to elliptic curve cryptography,, in, (2006), 155. Google Scholar [22] T. Satoh, On polynomial interpolations related to Verheul homomorphisms,, LMS J. Comput. Math., 9 (2006), 135. Google Scholar [23] T. Satoh, Closed formulae for the Weil pairing inversion,, Finite Fields Appl., 14 (2008), 743. doi: 10.1016/j.ffa.2007.12.003. Google Scholar [24] E. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems,, J. Cryptology, 17 (2004), 277. doi: 10.1007/s00145-004-0313-x. Google Scholar
 [1] 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 [2] Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557 [3] Rabah Amir, Igor V. Evstigneev. On Zermelo's theorem. Journal of Dynamics & Games, 2017, 4 (3) : 191-194. doi: 10.3934/jdg.2017011 [4] John Hubbard, Yulij Ilyashenko. A proof of Kolmogorov's theorem. Discrete & Continuous Dynamical Systems - A, 2004, 10 (1&2) : 367-385. doi: 10.3934/dcds.2004.10.367 [5] 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 [6] Hahng-Yun Chu, Se-Hyun Ku, Jong-Suh Park. Conley's theorem for dispersive systems. Discrete & 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] Hiroshi Isozaki, Hisashi Morioka. A Rellich type theorem for discrete Schrödinger operators. Inverse Problems & Imaging, 2014, 8 (2) : 475-489. doi: 10.3934/ipi.2014.8.475 [9] V. Niţicâ. Journé's theorem for $C^{n,\omega}$ regularity. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 413-425. doi: 10.3934/dcds.2008.22.413 [10] Jacques Féjoz. On "Arnold's theorem" on the stability of the solar system. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3555-3565. doi: 10.3934/dcds.2013.33.3555 [11] 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 [12] Lena Noethen, Sebastian Walcher. Tikhonov's theorem and quasi-steady state. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 945-961. doi: 10.3934/dcdsb.2011.16.945 [13] Fatiha Alabau-Boussouira, Piermarco Cannarsa. A constructive proof of Gibson's stability theorem. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 611-617. doi: 10.3934/dcdss.2013.6.611 [14] Mateusz Krukowski. Arzelà-Ascoli's theorem in uniform spaces. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 283-294. doi: 10.3934/dcdsb.2018020 [15] Shalosh B. Ekhad and Doron Zeilberger. Proof of Conway's lost cosmological theorem. Electronic Research Announcements, 1997, 3: 78-82. [16] Florian Wagener. A parametrised version of Moser's modifying terms theorem. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 719-768. doi: 10.3934/dcdss.2010.3.719 [17] Pengyan Wang, Pengcheng Niu. Liouville's theorem for a fractional elliptic system. Discrete & Continuous Dynamical Systems - A, 2019, 39 (3) : 1545-1558. doi: 10.3934/dcds.2019067 [18] 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 [19] Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281 [20] Chihurn Kim, Dong Han Kim. On the law of logarithm of the recurrence time. Discrete & Continuous Dynamical Systems - A, 2004, 10 (3) : 581-587. doi: 10.3934/dcds.2004.10.581

2018 Impact Factor: 0.879