# Ring-LWE lattice cryptography and FFT Trick for $X^n+1$

in reference here the FFT trick for $$X^n+1$$ is discussed with reference to the Number Theoretic transformation. On page 5, the Chinese Remainder Theorem is used to define the mapping.

So far so good. But I am particularly interested in how to arrive at the statement that on the k-th level we have the following relationship:

Where $$i = 0,...,2^k-1$$. Here $$\text{brv}$$ maps an $$log(n)$$-bit number to its bitreversal, $$brv(b_{log(n)−1}2^{log(n)−1} + · · · + b_1 2 + b_0) = b_0 2^{ log(n)−1} + · · · + b_{log(n)−2}2 + b_{log(n)−1}$$.

I cannot deduce from the text how to arrive at the expression in the exponent $$\text{brv}(2^k+i)$$. That is the reason for my question, how exactly do you arrive at the exponent here?

• Please edit into question to make it self contained: here brv maps an log(n)-bit number to its bitreversal, brv(blog(n)−12 log(n)−1 + · · · + b12 + b0) = b02 log(n)−1 + · · · + blog(n)−22 + blog(n)−1. Commented Feb 22 at 14:35

It's first worth clarifying that your question has nothing (directly) to do with cryptography, and instead is entirely a question about how the FFT works. The map

$$f\mapsto (f\bmod X^{n/2}-\zeta^{n/2}, f\bmod X^{n/2}+\zeta^{n/2})$$

is typically called a "butterfly" (though often $$\zeta$$ is a root of unity in $$\mathbb{C}$$ rather than $$\mathbb{Z}_p$$. This difference doesn't really matter). Bit reversal appears when one studies the inplace Cooley-Tukey FFT in particular. So to understand this you can look for any explanation of the (inplace) Cooley-Tukey FFT. See for example this random website I found, though if you want something else the thing to search on is "inplace Cooley-Tukey", perhaps with "bit reversal" thrown in there.

At this point it is worth clarifying the one point here that is of cryptographic relevance. The inplace Cooley-Tukey FFT $$\mathcal{F}_{\mathsf{CT}}$$ can be decomposed into

1. A bunch of computations of butterflies, which I will call $$\mathcal{B}$$, followed by
2. a bit-reversal permutation to "fix" that the outputs being in the wrong order, which I will call $$\sigma$$.

This is to say that

$$\mathcal{F}_{\mathsf{CT}}(x) = (\sigma\circ \mathcal{B})(x).$$

Some schemes (namely Kyber/ML-KEM) choose to omit $$\sigma$$. This is to say that they leave their FFT domain values "in the wrong order", and $$\mathcal{F}_{\mathsf{Kyber}} = \mathcal{B}$$. This has some benefits when it comes to AVX implementations of the FFT, but does mean that the FFT in Kyber is not exactly the same as a standard FFT, both because

1. it is done over $$\mathbb{Z}_p$$ rather than $$\mathbb{C}$$ (this requires $$p$$ to be NTT friendly, but besides that is standard/boring), and
2. the output is (not) permuted by $$\sigma$$.

Some more details:

One way of viewing the FFT is linear algebraically. The following is from Tolimieri et al., "Algorithms for Discrete Fourier Transform and Convolution", section 4.

The DFT is linear on a finite-dimensional space, and so can be written as a matrix multiplication. One can write an $$N = 2M$$ dimensional DFT as

$$F_{N} = P_N(I_2\otimes F_M)T_N(F_2\otimes I_M)$$

Here, $$A\otimes B$$ is the kronecker product of matrices, $$T_N$$ is the matrix of "twiddle factors", and $$P_N$$ is the matrix such that $$P_N(A\otimes B) = B\otimes A$$.

Anyway, applying the above relation a few times, one can find (Theorem 1) that if $$N = 2^k$$

$$F_N = Q_N\prod_{i = 1}^k(I_{2^{i-1}}\otimes T_{2^{k-i+1}})\otimes (I_{2^{i-1}}\otimes F_2\otimes I_{2^{k-1}})$$

Note that the kronecker product $$A\otimes B$$ satisfies the "mixed-product property" $$(A\otimes B)(C\otimes D) = (AC)\otimes (BC)$$, at least when the matrix sizes match up. One also has that $$I_{2^k} = I_2\otimes I_{2^{k-1}} = I_{2^{k-1}}\otimes I_2$$.

Here, one can compute that

$$Q_N = P_N(I_2\otimes P_{N/2})\dots (I_{N/4}\otimes P_4)$$

All that remains is to show that $$Q_N$$ is actually bit reversal. This is done in discussion around eq. 19 in the source.

• Hi Mark, thanks for your reply and your efforts! I would agree with what you say. But: For me, this does not yet conclusively clarify how to apply this to my question. For me, the aspect that explains how the exponent $\text{brv}(2^k+i)$ is obtained is still missing. Commented Feb 22 at 19:12
• @TreeBook1 the link "random website that I found" goes through a worked example for $N = 2^3$, though for FFTs over $\mathbb{C}$. Commented Feb 22 at 19:44
• @TreeBook1 you can also view this (linear)-algebraically. See example section 4 of "Algorithms for Discrete Fourier Transform and Convolution" by Tolimieri et. al, which includes a derivation where bit reversal pops out. Commented Feb 22 at 19:56
• Thanks for the references! Quick note, I know that the indices of the coefficients follow the bit reversal. This is also shown by the formula in your first source $(f_0 + ... f_4) + ... + (f_3 + ... f_7)$. But: How the exponent is then explained, from my source, is not yet completely transparent. Let me take a look at your second source. Commented Feb 22 at 20:02
• +1 for mentioning Tolimieri's book Commented Feb 22 at 20:53