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

  • $\begingroup$ Would you elaborate your question, especially "q"? Also please consider summerize the section from the book here instead of asking to read it. Thanks. $\endgroup$
    – Cloud Cho
    Sep 15, 2022 at 17:58
  • $\begingroup$ I don't see any mention of $q$ in section 4.1.2. $\mathcal{R}_{q,f}$ is introduced in the next section which is just the polynomial ring $\mathbb{Z}_q[x]/f(x)$. The ring of polynomials in $x$ with coefficients mod $q$ quotiented by a polynomial $f(x)$ $\endgroup$
    – Lev
    Sep 15, 2022 at 22:34

1 Answer 1


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.

  • $\begingroup$ thanks for the rich explanation, I have one other question related to this, why should the multiplication result should have small-ish coefficients ? $\endgroup$
    – Don Freecs
    Sep 20, 2022 at 0:05
  • 1
    $\begingroup$ It is necessary for the product polynomial to have small coefficients so that it may be treated as an error term in expressions that arise from products in such constructions as Ding's key exchange or Gentry's homomorphic encryption scheme. $\endgroup$
    – Daniel S
    Sep 20, 2022 at 5:58
  • $\begingroup$ Dear Daniel I need references for Ding's key exchange please $\endgroup$
    – Don Freecs
    Dec 29, 2022 at 17:06
  • $\begingroup$ @DonFreecs eprint.iacr.org/2012/688.pdf $\endgroup$
    – Daniel S
    Dec 29, 2022 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.