In this talk, we will introduce a new tower field representation, Optimal Tower Fields (OTFs), that facilitates efficient finite field arithmetic. Particularly, the OTF recursive direct inversion method we will see has significantly lower complexity than the known best method for inversion in optimal extension fields (OEFs), i.e., Itoh-Tsujii's inversion technique. The complexity of OTF inversion algorithm is O(m²), which is similar to the complexity of multiplication and drastically better than O(m²(log₂m)) complexity of the Itoh-Tsujii algorithm. Complexity of OTF inversion can be further improved to O(m^{{log₂ 3}}) by utilizing the Karatsuba-Ofman algorithm. In addition, OTFs may be converted to OEF representation via a simple permutation of the coefficients, and hence OTF operations may be utilized to achieve the OEF arithmetic operations whenever a corresponding OTF representation exists. Elliptic curve cryptography relies heavily on the existence of efficient algorithms for finite field arithmetic. OEFs have been found to be especially successful in embedded software implementations of elliptic curve schemes. Nevertheless, inversion is still the slowest operation in elliptic curve cryptography and this poses a significant problem in embedded systems where computational power is limited. We will address this issue by proposing the use of OTFs. Finally, we will present the implementation results of OTF inversion algorithm on the ARM microprocessor and comment on the remarkable speed-up advantage of using OTFs for Elliptic Curve Cryptography.

DATE: June 22, 2004, Tuesday @ 13:40
PLACE: EA-409