CRYSTALS

The "Cryptographic Suite for Algebraic Lattices" (CRYSTALS) encompasses two cryptographic primitives: Kyber, an IND-CCA2-secure key-encapsulation mechanism (KEM); and Dilithium, a strongly EUF-CMA-secure digital signature algorithm. Both algorithms are based on hard problems over module lattices, are designed to withstand attacks by large quantum computers, and have been submitted to the NIST post-quantum cryptography project.

Module Lattices

Module lattices can be thought of as lattices that lie between the ones used in the definitions of the LWE problem, and those used for the Ring-LWE problem. If the ring underlying the module has a sufficiently high degree (like 256), then these lattices inherit all the efficiency of the ones used in the Ring-LWE problem, and additionally have the following advantages, when used in our cryptographic algorithms:

• The only operations required for Kyber and Dilithium for all security levels are variants of Keccak, additions/multiplications in Z_q for a fixed q, and the NTT (number theoretic transform) for the ring Z_q[X]/(X²⁵⁶+1).
  This means that increasing/decreasing the security level involves virtually no re-implementation of the schemes in software or hardware. Changing a few parameters is all that one needs to convert an optimized implementation for one security level into an optimized implementation for a different one.
• The lattices used in Kyber and Dilithium have less algebraic structure than those used for Ring-LWE and are closer to the unstructured lattices used in LWE.  It is therefore conceivable that if algebraic attacks against Ring-LWE appear (there are none that we are aware of at this point), then they may be less effective against schemes like Kyber and Dilithium.

News

• 2019-05-21: New paper on Kyber on Cortex-M4
• 2019-03-30: CRYSTALS round-2 versions are submitted and online.
• 2017-12-30: CRYSTALS website is online

Credits

The design and implementation of Kyber and Dilithium have been supported by

• the European Commission through the ICT program under contract ICT-645622 (PQCRYPTO);
• the European Commission through the ICT program under contract ICT-644729 (SAFEcrypto);
• the Swiss National Science Foundation through the 2014 transfer ERC Starting Grant  CRETP2-166734 (FELICITY);
• the Netherlands Organization for Scientific Research (NWO) through Veni grant 639.021.645 (Cryptanalysis of Lattice-based Cryptography);
• the European Commission through the ERC Starting Grant ERC-2013-StG-335086 (LATTAC);
• the European Commission through the ERC Consolidator Grant ERC-2013-CoG-615073 (ERCC);
• the European Commission through the ERC Starting Grant ERC-2018-StG-805031 (EPOQUE);
• the DFG through the Cluster of Excellence 2092 (CASA).

Institutions involved in the design of Kyber and Dilithium: