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]

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

[20]

J. S. Athreya, Anish Ghosh, Amritanshu Prasad. Ultrametric logarithm laws I. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 337-348. doi: 10.3934/dcdss.2009.2.337

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]