Evidence that XTR is more secure than supersingular elliptic curve cryptosystems
type: Item
instance of: scholarly article
title: Evidence that XTR is more secure than supersingular elliptic curve cryptosystems
zbMATH Open document ID: 1075.94011
author: Eric R. Verheul
published in: Journal of Cryptology
publication date: 2005-04-15T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 14H52
Mathematics Subject Classification ID: 14G50
zbMATH DE Number: 2157502
zbMATH Keywords: XTR public key systems
zbMATH Keywords: Diffie-Hellman problems
zbMATH Keywords: Supersingular elliptic curves
zbMATH Keywords: Inverting MOV embedding
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: s00145-004-0313-x
OpenAlex ID: W2101458679
DOI: 10.1007/S00145-004-0313-X
Recommended article: Q2778850
Recommended article: Easy Decision Diffie-Hellman Groups
Recommended article: Distortion maps for supersingular genus two curves
Recommended article: XTR Algorithm: Efficient and Compact Subgroup Trace Representation
Recommended article: An overview of the XTR public key system
Recommended article: Q4536791
Recommended article: Q2707417
Recommended article: Q2724583
Recommended article: Efficiently Computable Distortion Maps for Supersingular Curves
Recommended article: Information and Communications Security
description: scientific article; zbMATH DE number 2157502