Paper 2010/069

Type-II Optimal Polynomial Bases

Daniel J. Bernstein and Tanja Lange

Abstract

In the 1990s and early 2000s several papers investigated the relative merits of polynomial-basis and normal-basis computations for $\F_{2^n}$. Even for particularly squaring-friendly applications, such as implementations of Koblitz curves, normal bases fell behind in performance unless a type-I normal basis existed for $\F_{2^n}$. In 2007 Shokrollahi proposed a new method of multiplying in a type-II normal basis. Shokrollahi's method efficiently transforms the normal-basis multiplication into a single multiplication of two size-$(n+1)$ polynomials. This paper speeds up Shokrollahi's method in several ways. It first presents a simpler algorithm that uses only size-$n$ polynomials. It then explains how to reduce the transformation cost by dynamically switching to a `type-II optimal polynomial basis' and by using a new reduction strategy for multiplications that produce output in type-II polynomial basis. As an illustration of its improvements, this paper explains in detail how the multiplication overhead in Shokrollahi's original method has been reduced by a factor of $1.4$ in a major cryptanalytic computation, the ongoing attack on the ECC2K-130 Certicom challenge. The resulting overhead is also considerably smaller than the overhead in a traditional low-weight-polynomial-basis approach. This is the first state-of-the-art binary-elliptic-curve computation in which type-II bases have been shown to outperform traditional low-weight polynomial bases.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
optimal normal basisONBpolynomial basistransformationelliptic-curve cryptography
Contact author(s)
tanja @ hyperelliptic org
History
2010-04-14: revised
2010-02-11: received
See all versions
Short URL
https://ia.cr/2010/069
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/069,
      author = {Daniel J.  Bernstein and Tanja Lange},
      title = {Type-II Optimal Polynomial Bases},
      howpublished = {Cryptology ePrint Archive, Paper 2010/069},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/069}},
      url = {https://eprint.iacr.org/2010/069}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.