What is the purpose of the `reduce` function when performing matrix-vector multiplication?

[dieterml-ops]

Hello,

I am currently reading into Dilithium and during that, a question regarding the matrix-vector multiplication came up: I noticed that the matrix-vector multiplication w = Az is implemented like so:

1. Call polyvec_matrix_pointwise_montgomery(&w1, mat, &z);, where mat and z are already in NTT representation. This function performs coefficient wise multiplication and addition of the resulting polynomials without any reduction
2. A call to polyveck_reduce(&w1); follows
3. w1 is transformed back into coefficient representation: polyveck_invntt_tomont(&w1);

According to the comment, the reduce function reduces the coefficient to to representatives in [-6283009,6283007]. I am wondering: What is the purpose of this and how is this number chosen? If there is a paragraph in the paper which explains this, could you point me to it? Any help is very much appreciated!

Thank you very much

[gregorseiler]

Hi,

In our implementations we compute on 32-bit integers that represent the correct elements modulo q, but that don't usually lie in the standard intervals {-(q-1)/2,...,(q-1)/2} or {0,...,q-1}. The function polyveck_redude() reduces all coefficients of all polynomials in a polyveck to representatives in the interval that you cite. This is sometimes necessary to make sure that no overflow mod 2^32 can happen, or because certain functions have explicit requirements on the range of the input coefficients, which are documented in the comments before the definitions of the functions. In the example you mention it is the input requirement of the invntt function that lies behind the call to polyveck_reduoce(). The output range of polyveck_reduce() is a property of the particular modular reduction algorithm that we use (see reduce.c). This algorithm is tailor-made for the specific modulus q = 2^23 - 2^13 + 1 in Dilithium. In the paper this is not explained because every implementation is free to use a different way to implement the Zp arithmetic and this freedom is very important for optimized implementations on various platforms.

Hope this helps, Gregor

[dieterml-ops]

Hi @gregorseiler ,

Thanks, that helps a lot! Just one more question: Does that mean that the output range of the polyveck_invntt_tomont also does not follow the standard representation {-(q-1)/2,...,(q-1)/2} or {0,...,q-1}? I am asking because I am trying to reimplement the Matrix-vector multiplication in R_q (to learn), and I keep getting different results. Could you point me to the representation used in Dilithium for the element in Z_q?

Thank you so much!