Generalizations of Verheul's theorem to asymmetric pairings

Previous Article
AMC Home
This Issue
Next Article
New constructions of optimal frequency hopping sequences with new parameters

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

Abstract
Related Papers

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

Tools

Metrics

Other articles
by authors

on AIMS
Koray Karabina Edward Knapp Alfred Menezes
on Google Scholar
Koray Karabina Edward Knapp Alfred Menezes

[Back to Top]