Some tricks in lattice-based cryptography

Sigma conjugation

Let’s consider the polynomial ring $\mathbb{Z}_q[x] / (x^d + 1)$ and two polynomials:

$\mathbf{a}(x) = a_0 + a_1 x + ... + a_{d-1} x^{d-1}$

$\mathbf{b}(x) = b_0 + b_1 x + ... + b_{d-1} x^{d-1}$

Sometimes it’s necessary to prove something in $\mathbb{Z}_q$, let’s say

$a_0 b_0 + a_1 b_1 + ... + a_{d-1} b_{d-1} = r$

for some $r$.

For example, one might want to prove that the norm of $\mathbf{a}$ is $r$:

$a_0 a_0 + a_1 a_1 + ... + a_{d-1} a_{d-1} = r$

But how can we compute the inner product of the coefficients of $a$ and $b$, given that we operate in $\mathbb{Z}_q[x] / (x^d + 1)$?

It turns out that we can use sigma conjugation. The sigma conjugation is defined as:

$\sigma(\mathbf{b})(x) = b_0 - b_{d-1} x - b_{d-2} x^2 - ... - b_1 x^{d-1}$

Now, let’s compute only the constant term of $\mathbf{a}(x) \sigma(\mathbf{b})(x)$:

$ct(\mathbf{a}(x) \sigma(\mathbf{b})(x)) = a_0 b_0 - a_1 x b_1 x^{d-1} - a_2 x^2 b_2 x^{d-2} - ... - a_{d-1} x^{d-1} b_{d-1} x$

Now we use the fact that $x^d = -1$:

$ct(\mathbf{a}(x) \sigma(\mathbf{b})(x)) = a_0 b_0 + a_1 b_1 + a_2 b_2 + ... + a_{d-1} b_{d-1}$

Sigma conjugate in NTT space

In lattice-based cryptosystems, polynomial multiplication is a central operation. Standard polynomial multiplication has a time complexity of $O(n^2)$, which is inefficient for large $n$. The use of the Number Theoretic Transform (NTT) allows polynomial multiplication to be reduced to $O(n \log n)$, greatly improving performance and making it practical for cryptographic applications.

For this reason we move the polynomials into NTT space. When you apply the NTT, your polynomial is represented as evaluations at roots of unity $\omega^i$, where $\omega$ is a primitive $2^k$-th root of unity in a finite field. In $\mathbb{Z}_q[x] / (x^d + 1)$, we take (note that $d = 2k$):

$\omega^d = -1 \; mod \; q$

Let’s apply NTT to the polynomial $\mathbf{a}$, we obtain

$\mathbf{\hat{a}} = (\mathbf{a}(1), \mathbf{a}(\omega), ..., \mathbf{a}(\omega^{d-1}))$

Let’s say we would like to have $\hat{\sigma(\mathbf{a})} = (\sigma(\mathbf{a})(1), \sigma(\mathbf{a})(\omega), ..., \sigma(\mathbf{a})(\omega^{d-1}))$. Can we compute it directly from $\mathbf{\hat{a}}$?

Yes, it holds:

$\hat{\sigma(\mathbf{a})} = (\mathbf{a}(1), \mathbf{a}(-\omega^{d-1}), ..., \mathbf{a}(-\omega))$

It is actually the same permutation as when computing $\sigma(\mathbf{a})$ from $\mathbf{a}$, but with no negation (negation is now there by putting $-\omega^i$ instead of $\omega^i$). Remember:

$\sigma(\mathbf{a}) = a_0 - a_{d-1} x - ... - a_1 x^{d-1}$

Why does such a simple formula for $\hat{\sigma(\mathbf{a})}$ hold?

Let’s observe an example with $d = 8$ (that means $x^8 = -1$):

$\mathbf{a}(x) = a_0 + a_1 x + a_2 x^2 + ... + a_7 x^7$

$\sigma(\mathbf{a})(x) = a_0 - a_7 x - a_6 x^2 - ... - a_1 x^7$

Let’s now observe $\sigma(\mathbf{a})(-\omega^7)$:

$\sigma(\mathbf{a})(-\omega^7) = a_0 - a_7 (-\omega^7) - a_6 (-\omega^7)^{2} - ... - a_1 (-\omega^7)^{7}$

$= a_0 + a_7 \omega^7 - a_6 \omega^{14} - ... + a_1 \omega^{49}$

$= a_0 + a_7 \omega^7 - a_6 \omega^{8} \omega^6 + ... + a_1 \omega^{6 \cdot 8} \omega^7$

$= a_0 + a_7 \omega^7 + a_6 \omega^6 + ... + a_1 \omega^7$

We see:

$\mathbf{a}(\omega) = \sigma(\mathbf{a})(-\omega^{d-1})$

Similarly:

$\sigma(\mathbf{a})(\omega^7) = a_0 - a_7 (\omega^7) - a_6 (\omega^7)^{2} - ... - a_1 (\omega^7)^{7}$

$= a_0 - a_7 \omega^7 - a_6 \omega^{14} - ... - a_1 \omega^{49}$

$= a_0 - a_7 \omega^7 - a_6 \omega^{8} \omega^6 - ... - a_1 \omega^{6 \cdot 8} \omega^7$

$= a_0 - a_7 \omega^7 + a_6 \omega^6 - ... - a_1 \omega^7$

We see:

$\mathbf{a}(-\omega) = \sigma(\mathbf{a})(\omega^{d-1})$