International Association
for Cryptologic Research

This paper proposes a compact and efficient $GF(2^8)$ inversion

circuit design based on a combination of non-redundant and redundant

Galois Field (GF) arithmetic. The proposed design utilizes redundant

GF representations, called Polynomial Ring Representation (PRR)

and Redundantly Represented Basis (RRB), to implement GF(28) inversion

using a tower field $GF((2^4)2)$. In addition to the redundant representations,

we introduce a specific normal basis that makes it possible

to map the former components for the 16th and 17th powers of

input onto logic gates in an efficient manner. The latter components

for $GF(2^4)$ inversion and $GF(2^4)$ multiplication are then implemented

by PRR and RRB, respectively. The flexibility of the redundant representations

provides efficient mappings from/to the $GF(2^8)$. This paper

also evaluates the efficacy of the proposed circuit by means of gate

counts and logic synthesis with a 65 nm CMOS standard cell library and

comparisons with conventional circuits, including those with tower fields

$GF(((2^2)^2)^2)$. Consequently, we show that the proposed circuit achieves

approximately 40% higher efficiency in terms of area-time product than

the conventional best $GF(((2^2)^2)^2)$ circuit excluding isomorphic mappings.

We also demonstrate that the proposed circuit achieves the best

efficiency (i.e., area-time product) for an AES encryption S-Box circuit

including isomorphic mappings.