I took a look at the implementation of Kyber, which can be found in this GitRepo. I made a small discovery in the indcpa.c in the function indcpa_keypair, starting at line 205, which I can't quite interpret. The line is given below.

  // matrix-vector multiplication
  for(i=0;i<KYBER_K;i++) {
    polyvec_basemul_acc_montgomery(&pkpv.vec[i], &a[i], &skpv);

What we do there, we perform a matrix-vector multiplication of the matrix a with the vector skpv, which is done via the first line in the loop. Then, in the next line, pkpv is converted into the Montgomery representation with poly_tomont. Why are we doing the latter?

My thoughts:

  • From the description of polyvec_basemul_acc_montgomery, see line 202 here, we got: "Pointwise multiply elements of a and b, accumulate into r, and multiply by 2^-16". If I remember correctly, the Montgomery factor was $2^{16}$, so if polyvec_basemul_acc_montgomery produces an output that is multiplied by $2^{-16}$, then we have to work with poly_tomont afterwards (because we multiply by $2^{16}$ again when converting to Montgomery representation) to get rid of the $2^{-16}$, right?

Further question:

  • In conext of polyvec_basemul_acc_montgomery, however, it is another question where the multiplication by $2^{-16}$ takes place...


Your Answer

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

Browse other questions tagged or ask your own question.