Evidence that XTR is more secure than supersingular elliptic curve cryptosystems (Q1772226)

The well-known MOV algorithm [\textit{A. J. Menezes, T. Okamoto} and \textit{S. A. Vanstone}, IEEE Trans. Inf. Theory 39, No.~5, 1639--1646 (1993; Zbl 0801.94011)] allows to translate the Discrete Logarithm Problem (DLP) in a supersingular elliptic curve defined over GF\((q)\) to the DLP in a subgroup of the multiplicative group GF\((q^r)^*\), for some \(r\leq 6\). The XTR public key cryptosystems [\textit{A. K. Lenstra, E. R. Verheul}, CRYPTO 2000, Lect. Notes Comput. Sci. 1880, 1--19 (2000; Zbl 0995.94538)] work with the order \(p^2-p+1\) subgroup of GF\((p^6)^*\)\, (the XTR group), and the MOV algorithm provides an efficiently computable injective homomorphism of a (Class Three) supersingular elliptic curve over GF\((p^2)\), that the paper calls CTR curve, onto the XTR group. A plausible hypothesis, posed by Vanstone and Menezes, is that the inverse of such homomorphism can also be efficiently computed (so the XTR cryptosystems would reduce in fact to elliptic cryptosystems). The present paper provides evidence for a negative answer to the above hypothesis, showing that under it several believed hard problems, as the Diffie-Hellman Problem (DHP) , could be solved in the XTR subgroup. In Section 2 the authors study the structure of CTP curves and introduce the so-called distortion maps on CTP curves. The main results are proved in Section 3 where, as a side result, is also proved that the DDHP (Decision Diffie-Hellman Problem) in the CTP elliptic supersingular curves is efficiently computable (while the DHP and DLP are believed to be hard problems). In Section 4 the authors discuss possible generalizations of their results and techniques to other cryptosystems and general (nonsupersingular) elliptic curves where distortion map exist and in Section 5 discuss some other cryptographic applications of the distortion maps. Section 6 is for conclusions.