Analysis and Implementation of Module-Lattice-Based Key-Encapsulation Mechanism Standard

With current progress in quantum computing, there is concern that current digital encryption standards will soon be susceptible to attack. A machine capable of executing Shor’s algorithm (Shor, 1996) would render the Rivest-Shamir-Adleman (RSA) (Rivest et al., 1978) and Elliptic Curve Cryptography (ECC) (National Institute of Standards and Technology, 2013) schemes, two of the most common cryptographic algorithms, vulnerable. To prepare for this, NIST has released four cryptographic algorithms that are thought to be resistant to attack by quantum computers.

One of these draft standards is FIPS 203 (National Institute of Standards and Technology, 2023), Module-Lattice-Based Key-Encapsulation Mechanism Standard. A key-encapsulation mechanism (KEM) is a set of algorithms used to generate a secret key, shared by two parties, over a public channel. FIPS 203 uses the ML-KEM scheme. The security of this scheme relates to the Module Learning with Errors problem (Boudgoust et al., 2022).

We intend to study these algorithms and their effectiveness and efficiency from both a practical and theoretical standpoint. Using Python, we are implementing the encryption scheme outlined in FIPS-203. Following the completion of this implementation, we will conduct a formal analysis of this algorithm as a second phase of this investigation. Time complexity and space complexity of the algorithmic procedures will be measured experimentally to validate theoretical asymptotic complexity results. Our analysis will include the use of state exploration tools and techniques, theorem provers, model checkers, and type checking.

For more information: mabauer@eckerd.edu

Accessibility | Non-Discrimination | Privacy | Report It