1
$\begingroup$

Can someone explain me the meaning of 1024 and 768 in Dilithium-1024x768 in the algorithm? And the meaning of 2 in Dilithium2 in the algorithm?

$\endgroup$
3
$\begingroup$

1024 and 768 refer to the dimension of the base "generator" matrix $A$, these numbers are multiples of 256, which is the size of the module ring.

If the terminology is a bit confusing so far, then let me explain a little:

  • $A$ is a component of the public key, it's computed from a random seed chosen during key generation. It's also used in signing and verification.

  • Dilithium (along with Kyber, Saber, and some others) uses a "modular" lattice. That is, instead of a polynomial ring, or a matrix of integers, they use a matrix of high-dimension polynomial ring (degree-256 in the case of Dilithium and Kyber, etc.). This greatly improves performance and the scalability of the security level.

Some may question: "didn't document say $(k,l) = (4,4)$ (or $(4,3)$ in earlier versions)?". That's true, and those numbers are referring to when you consider module ring as matrix element. If you expand the ring modules into 256-by-256 matrices, the full matrix will be 1024-by-768. And for those familiar with lattice-reduction attacks, 4 is obviously too small a dimension that can be easily attacked.

As for "2", I'm not certain. Maybe it just refers to the version of Dilithium submitted to NIST in the 2nd round.

$\endgroup$
2
  • $\begingroup$ I don't think so. If you see the official documentation $(k,l)$, the dimension of $A$, is (4,4). As for "2", means that Dilithium claimed NIST security level 2. Nonetheless, thanks for the participation. $\endgroup$ – jmr Feb 26 at 10:12
  • $\begingroup$ @JesúsMolinaRoldán When you multiply 4 by 256 you get 1024, and I said in the 1st paragraph 1024 and 768 are multiples of 256. $\endgroup$ – DannyNiu Feb 26 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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