Wiener, Michael J.; Zuccherato, Robert J. Faster attacks on elliptic curve cryptosystems. (English) Zbl 1025.94511 Tavares, Stafford (ed.) et al., Selected areas in cryptography. 5th annual international workshop, SAC ’98. Kingston, Ontario, Canada, August 17-18, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1556, 190-200 (1999). Summary: The previously best attack known on elliptic curve cryptosystems used in practice was the parallel collision search based on Pollard’s \(\rho\)-method. The complexity of this attack is the square root of the prime order of the generating point used. For arbitrary curves, typically defined over \(\text{GF}(p)\) or \(\text{GF}(2^m)\), the attack time can be reduced by a factor or \(\sqrt{2}\), a small improvement. For subfield curves, those defined over \(\text{GF}(2^{ed})\) with coefficients defining the curve restricted to \(\text{GF}(2^e)\), the attack time can be reduced by a factor of \(\sqrt{2d}\). In particular for curves over \(\text{GF}(2^m)\) with coefficients in \(\text{GF}(2)\), called anomalous binary curves or Koblitz curves, the attack time can be reduced by a factor of \(\sqrt{2m}\). These curves have structure which allows faster cryptosystem computations. Unfortunately, this structure also helps the attacker. In an example, the time required to compute an elliptic curve logarithm on an anomalous binary curve over \(\text{GF}(2^{163})\) is reduced from \(2^{81}\) to \(2^{77}\) elliptic curve operations.For the entire collection see [Zbl 0912.00037]. Cited in 30 Documents MSC: 94A60 Cryptography 14G50 Applications to coding theory and cryptography of arithmetic geometry Keywords:elliptic curve discrete logarithm problem; attacks; elliptic curve cryptosystems; Koblitz curves PDFBibTeX XMLCite \textit{M. J. Wiener} and \textit{R. J. Zuccherato}, Lect. Notes Comput. Sci. 1556, 190--200 (1999; Zbl 1025.94511)