Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems

  • Eric R. Verheul
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


We show that finding an efficiently computable injective homomorphism from the XTR subgroup into the group of points over GF(p 2) of a particular type of supersingular elliptic curve is at least as hard as solving the Diffie-Hellman problem in the XTR subgroup. This provides strong evidence for a negative answer to the question posed by S. Vanstone and A. Menezes at the Crypto 2000 Rump Session on the possibility of efficiently inverting the MOV embedding into the XTR subgroup. As a side result we show that the Decision Diffie-Hellman problem in the group of points on this type of supersingular elliptic curves is efficiently computable, which provides an example of a group where the Decision Diffie-Hellman problem is simple, while the Diffie-Hellman and discrete logarithm problem are presumably not. The cryptanalytical tools we use also lead to cryptographic applications of independent interest. These applications are an improvement of Joux's one round protocol for tripartite Diffie-Hellman key exchange and a non refutable digital signature scheme that supports escrowable encryption. We also discuss the applicability of our methods to general elliptic curves defined over finite fields.


Elliptic Curve Elliptic Curf Discrete Logarithm Torsion Group Elliptic Curve Cryptosystem 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    R. Barasubramanian, N. Koblitz, The improbability that an elliptic curve has subexponential discrete log problem under the MOV algorithm, J. of Cryptology, vol 11, 141–145, 1999.CrossRefGoogle Scholar
  2. 2.
    R. Cramer, R. Gennaro, B. Schoenmakers, A Secure and Optimally Efficient Multi-Authority Election Scheme Advances in Cryptology-EUROCRYPT '97 Proceedings, Springer-Verlag, 1997, 103–118.Google Scholar
  3. 3.
    R. Cramer, V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, Proceedings of Crypto 1998, LNCS 1462, Springer-Verlag, 1998, 13–25.Google Scholar
  4. 4.
    T. ElGamal, A Public Key Cryptosystem and a Signature scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory 31(4), 1985, 469–472.zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    A. Joux, A one round protocol for tripartite Diffie-Hellman, 4th International Symposium, Proceedings of ANTS, LNCS 1838, Springer-Verlag, 2000, 385–394.Google Scholar
  6. 6.
    A. Joux, K. Nguyen, Seperating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, in preparation. Available from Scholar
  7. 7.
    G. Gong, L. Harn, Public key cryptosystems based on cubic finite field extensions, IEEE Trans. on I.T., November 1999.Google Scholar
  8. 8.
    N. Koblitz, The 4th workshop on Elliptic Curve Cryptography (ECC 2000), Essen, October 4–6 2000.Google Scholar
  9. 9.
    N. Koblitz, An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm, Proceedings of Crypto '98, LNCS 1462, Springer-Verlag, 1998, 327–337.Google Scholar
  10. 10.
    A.K. Lenstra, E.R. Verheul, The XTR public key system, Proceedings of Crypto 2000, LNCS 1880, Springer-Verlag, 2000, 1–19; available from Scholar
  11. 11.
    A.K. Lenstra, E.R. Verheul, Key improvements to XTR, Proceedings of Asiacrypt 2000, LNCS 1976, Springer-Verlag, 2000, 220–223; available from Scholar
  12. 12.
    A.K. Lenstra, E.R. Verheul, Fast irreducibility and subgroup membership testing in XTR, Proceedings of the 2001 Public Key Cryptography conference, LNCS 1992, Springer-Verlag, 2001, 73–86; available from Scholar
  13. 13.
    R. Lidl, W.B. Müller, Permutation Polynomials in RSA-cryptosystems, Crypto '83 Proceedings, Plemium Press, 1984, 293–301.Google Scholar
  14. 14.
    A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Boston 1993.zbMATHGoogle Scholar
  15. 15.
    A. Menezes, T. Okamoto, S.A. Vanstone Reducing elliptic curve logarithms to a finite field, IEEE Trans. Info. Theory, 39, 1639–1646, 1993.zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    A. Menezes, S.A. Vanstone, ECSTR (XTR): Elliptic Curve Singular Trace Representation, Rump Session of Crypto dy2000.Google Scholar
  17. 17.
    S.C. Pohlig, M.E. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. on IT, 24 (1978), 106–110.zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    J. Silverman, The Arithmetic on Elliptic Curves, Springer-Verlag, New York, 1986.Google Scholar
  19. 19.
    P. Smith, C. Skinner, A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms, Asiacrypt '94 proceedings, Springer-Verlag, 1995, 357–364.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Eric R. Verheul
    • 1
  1. 1.PricewaterhouseCoopersGRMS Crypto groupAB UtrechtThe Netherlands

Personalised recommendations