TY - BOOK

T1 - Type-II optimal polynomial bases

AU - Bernstein, D.J.

AU - Lange, T.

PY - 2010

Y1 - 2010

N2 - In the 1990s and early 2000s several papers investigated the relative merits of
polynomial-basis and normal-basis computations for F2n. 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 F2n.
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.
Keywords: Optimal normal basis, ONB, polynomial basis, transformation, elliptic-curve cryptography.

AB - In the 1990s and early 2000s several papers investigated the relative merits of
polynomial-basis and normal-basis computations for F2n. 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 F2n.
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.
Keywords: Optimal normal basis, ONB, polynomial basis, transformation, elliptic-curve cryptography.

M3 - Report

T3 - Cryptology ePrint Archive

BT - Type-II optimal polynomial bases

PB - IACR

ER -