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.

[2]

P. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order,, in, (2006), 319.

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

[4]

D. Brown and R. Gallant, The static Diffie-Hellman problem,, available online at \url{http://eprint.iacr.org/2004/306}, ().

[5]

J. Cheon, Security analysis of the Strong Diffie-Hellman problem,, in, (2006), 1.

[6]

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

[7]

T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over $GF(p^{2})$,, IEEE Trans. Inform. Theory, 31 (1985), 473.

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

[9]

S. Galbraith, Pairings,, in, (2005).

[10]

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

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

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

[13]

Z. Hu, M. Xu and Z. Zhou, A generalization of Verheul's theorem for some ordinary curves,, in, (2011), 105.

[14]

N. Koblitz and A. Menezes, Pairing-based cryptography at high security levels,, in, (2005), 13.

[15]

A. Lenstra and E. Verheul, The XTR public key system,, in, (2000), 1.

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

[17]

A. Menezes and S. Vanstone, ECSTR (XTR): Elliptic curve singular trace representation,, in, (2000).

[18]

D. Mireles Morales, Cheon's algorithm, pairing inversion and the discrete logarithm problem,, available online at \url{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.

[20]

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

[21]

T. Satoh, On degrees of polynomial interpolations related to elliptic curve cryptography,, in, (2006), 155.

[22]

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

[23]

T. Satoh, Closed formulae for the Weil pairing inversion,, Finite Fields Appl., 14 (2008), 743. 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. 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, (2011), 48.

[2]

P. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order,, in, (2006), 319.

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

[4]

D. Brown and R. Gallant, The static Diffie-Hellman problem,, available online at \url{http://eprint.iacr.org/2004/306}, ().

[5]

J. Cheon, Security analysis of the Strong Diffie-Hellman problem,, in, (2006), 1.

[6]

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

[7]

T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over $GF(p^{2})$,, IEEE Trans. Inform. Theory, 31 (1985), 473.

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

[9]

S. Galbraith, Pairings,, in, (2005).

[10]

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

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

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

[13]

Z. Hu, M. Xu and Z. Zhou, A generalization of Verheul's theorem for some ordinary curves,, in, (2011), 105.

[14]

N. Koblitz and A. Menezes, Pairing-based cryptography at high security levels,, in, (2005), 13.

[15]

A. Lenstra and E. Verheul, The XTR public key system,, in, (2000), 1.

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

[17]

A. Menezes and S. Vanstone, ECSTR (XTR): Elliptic curve singular trace representation,, in, (2000).

[18]

D. Mireles Morales, Cheon's algorithm, pairing inversion and the discrete logarithm problem,, available online at \url{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.

[20]

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

[21]

T. Satoh, On degrees of polynomial interpolations related to elliptic curve cryptography,, in, (2006), 155.

[22]

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

[23]

T. Satoh, Closed formulae for the Weil pairing inversion,, Finite Fields Appl., 14 (2008), 743. 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. doi: 10.1007/s00145-004-0313-x.

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

C. D. Ahlbrandt, A. C. Peterson. A general reduction of order theorem for discrete linear symplectic systems. Conference Publications, 1998, 1998 (Special) : 7-18. doi: 10.3934/proc.1998.1998.7

2017 Impact Factor: 0.564

Metrics

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

Other articles
by authors

[Back to Top]