Additive FFT Explained: Fast Fourier Transforms Over Binary Fields

Sign in<br>Subscribe

Warning : This post is more math heavy than other articles.

Introduction

In this article we continue our study of towers of binary fields, motivated by the proposal of Diamond and Posen for a complete protocol working over fields of characteristic 2, BINIUS. Previously we covered basic arithmetic of field elements in a tower of binary fields, namely Wiedemann's iterative quadratic extension of $\mathbb{F_2}$. We address the problem of evaluating and interpolating polynomials with coefficients in such fields, with cryptographic applications in mind. Devising a smart and efficient algorithm for doing polynomial evaluations will open the door for efficient implementation of Reed-Solomon encoding in characteristic 2, which is a crucial building block for polynomial commitments.

On the general problem of polynomial multiplication

Once we covered the structure of the Wiedemann's binary tower, it is natural to wonder how functions over this tower can be evaluated or multiplied together. To our goals, this is important since polynomial evaluation over a cleverly selected subset of the base field (for example, the $n$-th roots of unity) is the ground for encoding messages using Reed-Solomon techniques; in this light, the problem of polynomial evaluation is very close the problem of Reed-Solomon encoding.

A recollection of an efficient method for multiplication of polynomials comes to mind: the Fast Fourier Transform algorithm. It employs the celebrated scheme

$$\text{ evaluate }\implies\text{ multiply }\implies \text{ interpolate}$$

In more technical terms for the acquainted reader, "polynomial evaluation" stands for "take the FFT of the polynomial", multiply means "pointwise multiply their FFT's" and interpolate says "take the inverse FFT of the result". This general scheme allows us to bypass the computational cost of multiplying two polynomials and applying the distributive law, as in highschool. These "evaluation" and "interpolation" steps usually involve matrix multiplication; whenever we evaluate a polynomial $f$ in the powers if a primitive $n$-th root of unity and $n$ is a power of 2, a recursive algorithm is available and all this can be done quickly, say $\mathcal{O}(n\log(n))$. Obviously this has to be one of the most recorded facts of the history of mathematics; literature abounds.

So what about applying the FFT here? Well, there's a catch. In the context of finite fields "roots of unity" may not readily exist, or finding a sufficient number of them might require working in much larger and more complex extension fields.This fundamental limitation renders the standard FFT either impractical or very slow for these specific field types.

A general framework for towers of extensions in positive characteristic

To overcome this, we look into the work of David Cantor, "On Arithmetical Algorithms over Finite Fields" from 1989. There he develops an analogue of the FFT that operates on additive subgroups of the base field instead of multiplicative ones; since now we are dealing with additions instead of multiplication of group elements, this scheme is usually coined "Additive FFT". Cantor finds an analogue of the roots of unity and proceeds to break down the problem into a smaller one that can be solved recursively, just like in the classical FFT case. The good piece good news is that these additive subgroups are no other than than $\mathbb{F_p}$-vector subspaces, closely related to the familiar subfields that appear in Wiedemann's work and Diamond and Posen's proposal.

The crucial object for the construction of the Additive FFT is the notion of linearized polynomial ; they are a special class of polynomials that exhibit very interesting properties due to their "linear" nature with respect to addition and scalar multiplication in the base finite field. A linearized polynomial is such that all its monomials have a degree that is a power of $q$, that is $q^r$ ; this is a polynomial of the form (check the appendix at the end for more)

$$L(x) = \sum_{ i = 0 }^d a_i x^{ q^i }$$

where $a_i \in F_q$ (in this discussion, assume $p$ is a prime number and $q = p^n$ for some natural number $n$) The main property of this polynomials is that since we're working modulo $p$, behave just like linear transformations, in the standard linear algebra sense . This is, they satisfy for any $u, v \in F_{ q^n }$ and $c \in F_q$:

$L(u + v) = L(u) + L(v)$

$L(cu) = cL(u)$

Whenever we have a linearized polynomial $L$, the set of its roots (zeros) forms a vector space over $\mathbb{F_q}$ (called Kernel):

$$Ker(L) = \{v \in \mathbb{F_{ q^n }} : L(v) = 0 \}\subset \mathbb{F_{ q^n }}$$

fact that stems from the general theory of linear algebra; this means that linear combinations of roots are still roots of $L$. Lastly, the very form (along with the linearity just discussed) of linearized polynomials offers a very neat property: composition...