Constant Time algorithms for $\mathbb{Z}/m\mathbb{Z}$, $\mathbb{Z}/m\mathbb{Z}[x]$, and $\mathbb{Z}/m\mathbb{Z}[x] / (f(x))$?

Question

I want to implement some (lattice based) protocols to better familiarize myself with a programming language (Rust). These tend to do arithmetic over rings like $\mathbb{Z}/m\mathbb{Z}$, or "extensions" of this ring (meaning $(\mathbb{Z}/m\mathbb{Z})[x] / (f(x))$. Since it seems like I'll need to implement the ring arithmetic myself (there are finite field libraries, but this stops certain optimizations I am interested in exploring such as double-CRT arithmetic), I might as well do something slightly-more-than-naive, and use constant time algorithms (which I am assuming are quite well-known at this point). I am somewhat interested in algorithms that assume special structure of $m$ and $f(x)$ (say $m = 2^k \pm c$ for small $c$, or $f(x)$ a cyclotomic polynomial), but my primary interest is of algorithms that make no special assumptions on the structure of $m$ or $f(x)$.

Is there a particularly good reference for these algorithms? Chapter 14 of Handbook of Applied Cryptography seems to be a good start. It doesn't appear to discuss polynomial arithmetic directly, but it seems like you could piece together something by using their MPI arithmetic section. Additionally, this chapter doesn't discuss constant time algorithms directly, but quickly glancing over their algorithms I don't see anything that is too obviously variable time.

Still, is there some better reference for the task I am interested in?

Answer 1

While this is not a total answer (it does not discuss polynomial arithmetic), the Big Integer Design section of the BearSSL page seems like a good resource to share on this problem. Many of the algorithms are roughly similar to those in chapter 14 of Handbook of Applied Cryptography, but care has been made to make them constant time (not all of the algorithms in chapter 14 are by default). In general BearSSL aims to be a "pedagogical" implementation of TLS. Practically speaking, this means it is well-documented, and algorithmic decisions seem to be explained well.

I have not yet looked into algorithms for $\mathbb{Z}/n\mathbb{Z}[x]$ or $\mathbb{Z}/n\mathbb{Z}[x]/(f(x))$, so won't accept an answer until I get to there (or someone else suggests references).