Generalizations of Verheul's theorem to asymmetric pairings

Koray Karabina; Edward Knapp; Alfred Menezes

doi:10.3934/amc.2013.7.103

Article Contents

2013, Volume 7, Issue 1: 103-111. Doi: 10.3934/amc.2013.7.103

This issue Previous Article New constructions of optimal frequency hopping sequences with new parameters Next Article

Generalizations of Verheul's theorem to asymmetric pairings

1.
Department of Mathematics, Bilkent University, Bilkent, Ankara 06800
2.
Google, Inc., 1600 Amphitheater Parkway, Mountain View, California 94043
3.
Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1

Received: May 31, 2012

Revised: August 31, 2012

Published: January 2013

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 94A60.

Citation:

Related Papers

Cited by

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.