Dave Ishii - Problem Solving Blog

In the evolving landscape of post-quantum cryptography (PQC), CRYSTALS-Kyber and NTRU stand out as leading lattice-based key encapsulation mechanisms (KEMs).¹ While both are designed to withstand attacks from quantum computers, their underlying mathematical principles differ in key aspects. Kyber's security is based on the hardness of the Module Learning with Errors (MLWE) problem, while NTRU's security relies on the Shortest Vector Problem (SVP) in a specific polynomial ring.² This fundamental mathematical distinction leads to variations in their performance, security characteristics, and implementation.

Here's a deeper dive into the mathematical comparison of Kyber and NTRU:

Foundational Hard Problems: MLWE vs. SVP

The security of any cryptographic system rests on the difficulty of solving a particular mathematical problem.³ For Kyber and NTRU, these are:

• CRYSTALS-Kyber (MLWE): The Module Learning with Errors problem is a more structured and efficient variant of the Learning with Errors (LWE) problem. In essence, LWE involves distinguishing between a set of truly random linear equations and a set of linear equations with a small amount of "noise" or error added.⁴ The challenge lies in recovering the secret key from these noisy equations. The "module" aspect of MLWE allows for operations over matrices of polynomials, leading to smaller key and ciphertext sizes compared to standard LWE. The security of Kyber is directly tied to the presumed difficulty of solving the MLWE problem.⁵

• NTRU (SVP): The security of NTRU is based on the Shortest Vector Problem in a lattice.⁶ A lattice is a regular arrangement of points in space.⁷ The SVP asks to find the non-zero lattice point closest to the origin. In the context of NTRU, the lattice is constructed from the public key, and the secret key corresponds to a short vector in this lattice. Finding this short vector is computationally difficult, and this difficulty is the foundation of NTRU's security.

Mathematical Operations and Structure

The core operations in Kyber and NTRU are centered around polynomial arithmetic, but with different structures:⁸

• Kyber: Kyber operates over a polynomial ring, specifically a cyclotomic ring.⁹ The key generation, encapsulation, and decapsulation processes involve matrix and vector operations where the elements are polynomials.¹⁰ A key feature of Kyber is its use of the Number-Theoretic Transform (NTT) to perform polynomial multiplication efficiently.¹¹ This significantly speeds up the cryptographic operations. The process involves generating a public matrix A and a secret vector s. The public key is then t = As + e, where e is a small error vector.¹²

• NTRU: NTRU also operates in a polynomial ring.¹³ The key generation involves selecting two small polynomials, f and g. The public key h is then computed as the modular inverse of f multiplied by g. Encryption involves using the public key to create a ciphertext polynomial, and decryption uses the private key f to recover the original message. The core mathematical operation is polynomial multiplication in a truncated polynomial ring.¹⁴

A Comparative Look at Key Features

Feature	CRYSTALS-Kyber	NTRU
Underlying Problem	Module Learning with Errors (MLWE)	Shortest Vector Problem (SVP)
Mathematical Structure	Operations on matrices of polynomials in a cyclotomic ring.	Operations on polynomials in a truncated polynomial ring.
Key Generation	Involves generating a random matrix and a secret vector with small coefficients.	Involves selecting two small polynomials and computing a modular inverse.
Performance	Generally faster due to the efficient Number-Theoretic Transform (NTT) for polynomial multiplication.	Performance is also very good, but can be slightly slower than Kyber in some implementations.
Key & Ciphertext Size	Generally has a good balance of key and ciphertext sizes.	Historically has offered smaller key and ciphertext sizes, which can be advantageous in constrained environments.
Security Proofs	Has a strong security reduction to the underlying MLWE problem.	Security is well-understood and has been studied for a longer period.

NIST Standardization and Future Outlook

In the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography standardization process, Kyber was selected as the primary standard for public-key encryption and key establishment.¹⁵ NTRU was a strong contender and is considered a viable alternative.¹⁶ The choice of Kyber was influenced by its excellent performance and strong security proofs.¹⁷

However, the mathematical diversity offered by NTRU is also seen as a strength. Having strong alternatives based on different mathematical problems is crucial for long-term cryptographic resilience. Research and development continue for both algorithms, with ongoing efforts to optimize their performance and further analyze their security.

In conclusion, both Kyber and NTRU are robust post-quantum cryptographic algorithms rooted in the mathematics of lattices.¹⁸ Kyber's reliance on the MLWE problem and its efficient implementation have made it a leading standard.¹⁹ NTRU's foundation in the SVP and its long history of analysis make it a powerful and important alternative. The ongoing evolution of post-quantum cryptography will likely see continued use and refinement of both of these mathematically distinct but powerful approaches to securing our digital future.