Join Log in
Score:1
avatar Crypto

Why use negacyclic convolutions for polynomial multiplication instead of regular convolutions?

pm flag
warforgad

When multiplying polynomials from $\mathbb{Z}_q[X] / (X^n-1) $, the discrete NTT is used because: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \right) $$ However, in virtually all schemes I've seen the negacyclic convolution is used - the ring is $\mathbb{Z}_q[X] / (X^n+1) $ and a trick is used to compute $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right) \right) $ using $\mathsf{NTT}_n$ because we have to multiply the polynomials in $\mathbb{Z}_q[X] / (X^{2n}-1) $.
My question is - why bother with $\mathbb{Z}_q[X] / (X^n+1) $ and not simply use $\mathbb{Z}_q[X] / (X^n-1) $, thus applying $\mathsf{NTT}_n$ in a straightforward way with no extra complications?

41
0 + 0
lwe
Score:1
Hilder Vitor Lima Pereira avatar Crypto
us flag
Hilder Vitor Lima Pereira

The underlying hard problem used to construct the cryptographic primitives requires us to use that ring of polynomials modulo $X^n + 1$.

For example, if the security of your scheme relies on RLWE, then you have to stick with the rings that make the RLWE secure, which means that you cannot use $X^n - 1$, as discussed in this answer.

You have the same situation for the Ring-SIS problem.

In general, you have to be careful when you instantiate any problem with $X^n - 1$ as the modulus, because one can evaluate the polynomials on $1$ to work over integers instead of polynomials. This is discussed, for example, in the section "Polynomial evaluation" of this paper.

0 + 0
Score:1
kodlu avatar Crypto
sa flag
kodlu

You state (I have fixed your notation, residue classes are taken with a $/$ not $\backslash)$ the former is setminus which is not the same:

However, in virtually all schemes I've seen the negacyclic convolution is used - the ring is $\mathbb{Z}_q[X] / (X^n+1) $ and a trick is used to compute $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right) \right) $ using $\mathsf{NTT}_n$ because we have to multiply the polynomials in $\mathbb{Z}_q[X] / (X^{2n}-1) $.

and ask the question:

why bother with $\mathbb{Z}_q[X] / (X^n+1) $ and not simply use $\mathbb{Z}_q[X] \setminus (X^n-1) $?

If we have the polynomial factorization $x^{2n}-1=(x^n-1)(x^n+1)$ then computations modulo $x^{2n}-1$ can be speeded up by convolving (via NTT) with respect to each one of the factors and then combining. So

  1. We have a factorization that leads to a fast transform, so we take this route. The extreme case is complex FFT when we can factor all the way into linear factors $x^n-1=\prod_{i=1}^n (\omega^i-1)$ with $\omega$ a primitive $n^{th}$ root of unity.
  2. The factorization is unique, you cannot use $(x^n+1)$ only since $(x^n+1)^2=(x^{2n}+2 x^n+1)$ and $q$ is in general not characteristic 2. If you meant actually just use $x^{2n}-1$ directly, you'd have no speedup.
0 + 0
pm flag
warforgad
Sorry, my bad with the quotient notation. I think you misunderstood my question (or I have misunderstood your answer). I'm not asking how to multiply polynomials of degree $(2n-1)$ using NTTs of order $n$, and am not asking why it's impossible to multiply polynomials from $\mathbb{Z}_q[X]/(X^n+1)$ with NTTs. I'm asking why use polynomials modolu $X^n+1$ in the first place (which need the trick with $(X^{2n}-1)$), and not use polynomials modolu $X^n-1$
1
Reply
kodlu avatar
sa flag
kodlu
if your length is $N=2n,$ i.e., even, this IS the factorisation you must use to begin with i.e., $x^{2n}-1=(x^n-1)(x^n+1)$ because any $2n^{th}$ root of unity in any field or ring is either order $2n$ (those which are -1 when raised to power $n$) or have order dividing $n$.
0
Reply
kodlu avatar
sa flag
kodlu
you start with $N$ as a given.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.