International Association
for Cryptologic Research

Koblitz curves are a class of computationally efficient elliptic curves where scalar multiplications can be accelerated using $\\tau$NAF representations of scalars. However conversion from an integer scalar to a short $\\tau$NAF is costly and thus restricts speed. In this paper we present acceleration techniques for the recently proposed scalar conversion hardware based on division by $\\tau^2$. Acceleration is achieved in two steps. First we perform computational optimizations to reduce the number of long subtraction operations during the conversion of scalar. This helps in reducing the number of integer adder/subtracter circuits from the critical paths of the conversion architecture. In the second step, we perform pipelining in the conversion architecture in such a way that the pipeline stages are always utilized. Due to bubble free nature of the pipelining, clock cycle requirement of the conversion architecture remains same, while operating frequency increases drastically.

We present detailed experimental results to support our claims made in this paper.