What do dyadic product have to do with polynomial multiplication

abstract-algebralinear algebrapolynomials

I'm reading things about RLWE (Ring Learning With Errors) cryptography, and it relies heavily on polynomial multiplication modulo something. There's this line of code from Microsoft's SEAL RLWE library called

dyadic_product_coeffmod(
                        u.get() + i * coeff_count, public_key.data().data(j) + i * coeff_count, coeff_count,
                        coeff_modulus[i], destination.data(j) + i * coeff_count);

It looks like it multiplies 2 polynomials using the dyadic product. However, looking at the code, it looks like it's doing simply $a_i*b_i$ where $a_i$ and $b_i$ are the polynomial coefficients.

What is happening?

PS: the polynomials coefficients might be in RNS form

Best Answer

They are using a number theoretic transform (NTT) and the convolution property to replace polynomial multiplication (convolution of coefficients of the two polynomials you are multiplying) by termwise product in the Fourier domain.

The number theoretic transform may be meaningful in the ring ${\mathbb {Z}}/m,$ even when the modulus $m$ is not prime, provided a principal root of order $n$ exists. Special cases of the number theoretic transform such as the Fermat Number Transform ($m = 2^k+1$), used by the Schönhage–Strassen algorithm, or Mersenne Number Transform ($m = 2k − 1$) use a composite modulus.

NTT is a special case of Fourier (DFT) https://en.m.wikipedia.org/wiki/Discrete_Fourier_transform_(general). It has no rounding, it is exact, very important here.

Such a transform exists when a primitive root of unity of the right order exists. See p.2 of this paper for an RWLE example.

Edit: Dyadic product is simply the term used in the SEAL manual to denote the termwise product in the Fourier (NTT) domain. So if the NTT coefficients are in the lists $(a(\lambda)),(b(\lambda))$ the dyadic product is the list $(a(\lambda) b(\lambda)).$

This is a somewhat unusual use of that term.

Related Question