American Institute of Mathematical Sciences

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

Generalizations of Verheul's theorem to asymmetric pairings

Koray Karabina 1, , Edward Knapp 2, and  Alfred Menezes 3,

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.
Keywords: cryptography, discrete logarithm problem., asymmetric pairings, Verheul's theorem.
Mathematics Subject Classification: 94A6.
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.  Google Scholar

[2]

P. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order, in "Selected Areas in Cryptography - SAC 2005,'' (2006), 319-331.  Google Scholar

[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.  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 "Advances in Cryptology - EUROCRYPT 2006,'' (2006), 1-11.  Google Scholar

[6]

D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, 30 (1984), 587-594.  Google Scholar

[7]

T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over $GF(p^{2})$, IEEE Trans. Inform. Theory, 31 (1985), 473-481.  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-874.  Google Scholar

[9]

S. Galbraith, Pairings, in "Advances in Elliptic Curve Cryptography'' (eds. I. Blake, G. Seroussi and N. Smart), Cambridge University Press, 2005.  Google Scholar

[10]

S. Galbraith, C. Ó hÉigeartaigh and C. Sheedy, Simplified pairing computation and security implications, J. Math. Crypt., 1 (2007), 267-281.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

Z. Hu, M. Xu and Z. Zhou, A generalization of Verheul's theorem for some ordinary curves, in "Inscrypt 2010,'' (2011), 105-114.  Google Scholar

[14]

N. Koblitz and A. Menezes, Pairing-based cryptography at high security levels, in "Cryptography and Coding: 10th IMA International Conference,'' (2005), 13-36.  Google Scholar

[15]

A. Lenstra and E. Verheul, The XTR public key system, in "Advances in Cryptology - CRYPTO 2000,'' (2000), 1-19.  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-1646. doi: 10.1109/18.259647.  Google Scholar

[17]

A. Menezes and S. Vanstone, ECSTR (XTR): Elliptic curve singular trace representation, in "Rump Session of Crypto 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-390.  Google Scholar

[20]

J. Pollard, Monte Carlo methods for index computation mod $p$, Math. Comput., 32 (1978), 918-924.  Google Scholar

[21]

T. Satoh, On degrees of polynomial interpolations related to elliptic curve cryptography, in "WCC 2005,'' (2006), 155-163.  Google Scholar

[22]

T. Satoh, On polynomial interpolations related to Verheul homomorphisms, LMS J. Comput. Math., 9 (2006), 135-158.  Google Scholar

[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.  Google Scholar

[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.  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 "Advances in Cryptology - EUROCRYPT 2011,'' (2011), 48-68.  Google Scholar

[2]

P. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order, in "Selected Areas in Cryptography - SAC 2005,'' (2006), 319-331.  Google Scholar

[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.  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 "Advances in Cryptology - EUROCRYPT 2006,'' (2006), 1-11.  Google Scholar

[6]

D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, 30 (1984), 587-594.  Google Scholar

[7]

T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over $GF(p^{2})$, IEEE Trans. Inform. Theory, 31 (1985), 473-481.  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-874.  Google Scholar

[9]

S. Galbraith, Pairings, in "Advances in Elliptic Curve Cryptography'' (eds. I. Blake, G. Seroussi and N. Smart), Cambridge University Press, 2005.  Google Scholar

[10]

S. Galbraith, C. Ó hÉigeartaigh and C. Sheedy, Simplified pairing computation and security implications, J. Math. Crypt., 1 (2007), 267-281.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

Z. Hu, M. Xu and Z. Zhou, A generalization of Verheul's theorem for some ordinary curves, in "Inscrypt 2010,'' (2011), 105-114.  Google Scholar

[14]

N. Koblitz and A. Menezes, Pairing-based cryptography at high security levels, in "Cryptography and Coding: 10th IMA International Conference,'' (2005), 13-36.  Google Scholar

[15]

A. Lenstra and E. Verheul, The XTR public key system, in "Advances in Cryptology - CRYPTO 2000,'' (2000), 1-19.  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-1646. doi: 10.1109/18.259647.  Google Scholar

[17]

A. Menezes and S. Vanstone, ECSTR (XTR): Elliptic curve singular trace representation, in "Rump Session of Crypto 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-390.  Google Scholar

[20]

J. Pollard, Monte Carlo methods for index computation mod $p$, Math. Comput., 32 (1978), 918-924.  Google Scholar

[21]

T. Satoh, On degrees of polynomial interpolations related to elliptic curve cryptography, in "WCC 2005,'' (2006), 155-163.  Google Scholar

[22]

T. Satoh, On polynomial interpolations related to Verheul homomorphisms, LMS J. Comput. Math., 9 (2006), 135-158.  Google Scholar

[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.  Google Scholar

[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.  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]

John Hubbard, Yulij Ilyashenko. A proof of Kolmogorov's theorem. Discrete & Continuous Dynamical Systems, 2004, 10 (1&2) : 367-385. doi: 10.3934/dcds.2004.10.367
[4]

Rabah Amir, Igor V. Evstigneev. On Zermelo's theorem. Journal of Dynamics & Games, 2017, 4 (3) : 191-194. doi: 10.3934/jdg.2017011
[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]

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, 2020  doi: 10.3934/amc.2020119
[9]

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
[10]

Pengyan Wang, Pengcheng Niu. Liouville's theorem for a fractional elliptic system. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - S, 2010, 3 (4) : 719-768. doi: 10.3934/dcdss.2010.3.719
[19]

Chihurn Kim, Dong Han Kim. On the law of logarithm of the recurrence time. Discrete & Continuous Dynamical Systems, 2004, 10 (3) : 581-587. doi: 10.3934/dcds.2004.10.581
[20]

Jayadev S. Athreya, Gregory A. Margulis. Logarithm laws for unipotent flows, Ⅱ. Journal of Modern Dynamics, 2017, 11: 1-16. doi: 10.3934/jmd.2017001

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (83)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences