A Highly Parallel Constant-Time Almost-Inverse Algorithm
Daniele Venier, Ray C. C. Cheung · 2020
In this paper, we present a highly parallel and area-efficient constant-time inversion algorithm over the r-th degree polynomial ring, derived from Schroeppel's Almost Inverse algorithm. We propose a first constant time version, from which we derive a highly-parallel and a faster algorithm, while still preserving the constant-time property. This constitutes an alternative and relatively unexplored approach to inversion, compared to the more common multiplicative approach by Itoh and Tsuji, and has extensive application in algorithms such as the BIKE proposal for quantumresistant cryptography. Our approach is extremely area-efficient, with a constant area with respect to the polynomial degree r.