Advanced Search
Article Contents
Article Contents

Generalizations of Verheul's theorem to asymmetric pairings

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: 94A60.


    \begin{equation} \\ \end{equation}
  • [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.


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


    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.


    D. Brown and R. GallantThe static Diffie-Hellman problem, available online at http://eprint.iacr.org/2004/306


    J. Cheon, Security analysis of the Strong Diffie-Hellman problem, in "Advances in Cryptology - EUROCRYPT 2006,'' (2006), 1-11.


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


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


    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.


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


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


    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.


    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.


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


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


    A. Lenstra and E. Verheul, The XTR public key system, in "Advances in Cryptology - CRYPTO 2000,'' (2000), 1-19.


    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.


    A. Menezes and S. Vanstone, ECSTR (XTR): Elliptic curve singular trace representation, in "Rump Session of Crypto 2000''.


    D. Mireles MoralesCheon's algorithm, pairing inversion and the discrete logarithm problem, available online at http://eprint.iacr.org/2008/300


    D. Moody, The Diffie-Hellman problem and generalization of Verheul's theorem, Des. Codes Crypt., 52 (2009), 381-390.


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


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


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


    T. Satoh, Closed formulae for the Weil pairing inversion, Finite Fields Appl., 14 (2008), 743-765.doi: 10.1016/j.ffa.2007.12.003.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(128) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint