Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In this survey, I don't understand the necessary of coefficient (paragraph 4.1.2) growth and the choice of $X^d\pm 1 $ or $ X^d \pm X^{d/2} +1 $, since later introduces $q$ which doesn't mention the coefficient growth. I want to understand this paragraph please and its importance.
Thanks in advance
The goal here is that for any two polynomials $a(X),b(X)\in \mathcal R_f:=\mathbb Z[X]/f(X)$ should have a product whose coefficients are controlled as well as possible in absolute size by the absolute size of the coefficients of $a$ and $b$. This should mean that the products of polynomials with very small coefficients relative to $q$ will themselves have small-ish coefficients relative to $q$ and coefficient reduction modulo $q$ will not affect this property. We will require this property to hold for a wide range of choices of $a$ and $b$, and we want to choose a polynomial $f(X)$ that guarantees this for all $a(X)$ and $b(X)$.
If we look at the coefficient of $X^{d-1}$ in the product of $a(X)$ and $b(X)$ before reduction modulo $f(X)$, say $c(X):=a(X)b(X)$ it is given by $$c_{d-1}=\sum_{i=0}^{d-1}a_ib_{d-i-1}.$$ This is a sum of $d$ terms each of which is the product of two coefficients and this leads us to expect that we cannot hope to bound coefficients of the product better than $d||a||_\infty||b||_\infty$. Reduction modulo $f$ could potentially make matters worse by accumulating terms and scaling by integer multiples. We can make this feeling more precise by writing out the effect of multiplication by $a\mod f$ as matrix which acts on the coefficients of $b$ and this is what the paper does.
The best cases are when a) $f(X)=X^d-1$ when the general coefficient for the $j$th term of the product is $$c_j=\sum_{i=0}^{d-1}a_ib_{j-i\mod d},$$ which matches our naive bound before reduction, or b) when $f(X)=X^d+1$ when the general coefficient for the $j$th term of the product is $$c_j=\sum_{i=0}^{j}a_ib_{j-i}-\sum_{i=j+1}^{d-1}a_ib_{j+d-1-i},$$ again matching our naive bound before reduction in absolute value, or c) when $f(X)=X^d$ when the general coefficient for the $j$th term of the product is $$c_j=\sum_{i=0}^{j}a_ib_{j-i}$$ matching our naive bound before reduction in absolute value when $j=d-1$, but which is very bad choice for other reasons. For any other choice of $f(X)$ there will be a coefficient expression where the number of terms in the sum is greater than $d$ or where part of the sum is scaled by a coefficient of $f(X)$ that is greater than 1 in absolute value.
Polynomials of the form $f(X)= 𝑋^𝑑\pm X^{𝑑/2}\pm 1$ create coefficient expressions which are the sum of at most $2d$ terms which leads to a slightly poorer bound.
