Common subexpression algorithms for space-complexity reduction of Gaussian normal basis application

Reza Azarderakhsh, David Jao, and Hao Lee, 2015

Background

Normal bases have an easy implementation for the squaring operations in hardware. Hence they are used to represent elements in a binary field.
A Gaussian Normal Basis (GNB) is a special class of normal basis where field multiplication could be implemented efficiently.
Elliptic Curve Cryptography (ECC) are cryptographic algorithms using finite field arithmetic operations.
There are two types of normal basis multipliers. Recently, digit-level multipliers have been applied in ECC-based crypto-processors.
- Bit-level:
- Digit-level:
  The digit size is chosen dependent upon the amount of available resources. For high performance applications, they could be easily scaled up to perform bit-parallel multipliers; for resource-constrained applications, they could be scaled down to perform bit-level multipliers.

Motivation

As of 2010, the 80-bit (163-bit keys) and 112-bit (233-bit keys) became outdated. Hence ECC demands an increase in key size to at least 283 bits (128-bit security level). Such increment in key size results in the increased space complexity of the field multipliers. To optimize the efficiency of a squaring operation, we need to reduce the cost of implementing multiplication in hardware.

deliverable

For digit-multiplier architectures, Azarderakhsh et al presented two space-complexity reduction algorithms. The first algorithm produces optimal output in exponential time; the other runs in polynomial time but produce an approximate output. They produce compact multiplication matrices for all binary fields admitting suitable GNBs. Compared to previous results, there is no additional costs in time complexity, and both algorithms reduce the number of required XORs in the multiplication matrix. Moreover, the approximate algorithm is scalable with respect to the field and digit size.

The space-complexity reduction algorithm is based on generating minimum lists of distinct distances for Gaussian normal basis multiplication matrices for binary extension fields.

Intuition

Technical definitions

DL-SIPO Multiplier: a GNB multiplier architecture. One of its operands is fully available while the other one is available in a digit-serial fasion.

To implement the multiplication matrix R, a special module is employed (P module).
To generate all coordinates of the product AB, d copies of these P modules are needed to perform a multiplication in q = ceiling[m/d] clock cycles, where d is the digit size.
To construct a Q module, Figure 1 shows how to append to the R matrix. To reduce the space complexity, Q module is obtained with combining the d shifted versions of the P module.
To reduce the number of XORs for Q module implementation, apply a common subexpression elimination algorithm.

DL-PIPO Multiplier: a GNB multiplier architecture. Both input operands are fully available during the multiplication process, and the products will be available after the last clock cycle.

Let half of the multiplication matrix R be u.
To construct a p module, Figure 2 shows how to append to the u matrix.
To reduce the space complexity, apply a common subexpression elimination algorithm.