The papers CRYSTALS-Kyber and CRYSTALS-Dilithium both have been written by quite different authors. It seems that at least the key generation is very different from each other. CRYSTALS mainly seems to be a suite of algorithms based on the hardness of module lattices.

From CRYSTALS-Kyber:

CRYptographic SuiTe for Algebraic LatticeS – a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices.

Where the KEM part is obviously specific to Kyber, not to Dilithium

Which mathematical operations can be shared between implementations of both? What kind of percentage of these algorithms could use that shared implementation of (low level) primitives?

  • $\begingroup$ When I first started reading into these algorithms I was expecting that the CRYSTALS-projects were largely using the same kind of underlying implementation, but the papers don't even use the same identifiers (e.g. $\operatorname{KeyGen}$ vs just $\operatorname{Gen}$). $\endgroup$
    – Maarten Bodewes
    May 26, 2021 at 14:23
  • $\begingroup$ Inside, there are some overlapping modules. $\endgroup$
    – hola
    May 27, 2021 at 3:13
  • $\begingroup$ Yeah, I am thinking about looking at the ref & liboqs source code and answering myself, but I'm hoping that somebody has an answer ready. I think it would be useful for KEM and signatures to share implementation details for e.g. embedded devices and other HW implementations. $\endgroup$
    – Maarten Bodewes
    May 27, 2021 at 8:29
  • $\begingroup$ I am going through Kyber and Dilitihum, but it would take probably a few months to give a (reasonably) correct answer. :P $\endgroup$
    – hola
    May 27, 2021 at 10:39
  • 2
    $\begingroup$ If you can import it into a reasonable IDE, like Eclipse for C/C++ then you should get things like method lookup and such. In that case it should be relatively easy to dig down and get answers. It would be a challenge, but it should not take months :) $\endgroup$
    – Maarten Bodewes
    May 27, 2021 at 11:52


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.