What is Kyber ?
Last updated
Last updated
Here is an interesting paper mentioning Post-Quantum Cryptography and Kyber.
Kyber is a lattice-based post-quantum key encapsulation mechanism (KEM) selected by NIST as PQC standard in the public key encryption category in 2022. The security of Kyber is based in a variant of the Learning With Errors (LWE) problem, called Ring Learning With Errors (R-LWE). We denote as and defines the lattice used in Kyber, where takes values 2, 3 or 4 depending on the three parameters sets presented in the Kyber submission. The other parameters involved are and .
Kyber submission consists in two public key cryptosystems Kyber.PKE and Kyber.KEM. Kyber.PKE is defined as the three algorithms key generation, encrypt and decrypt (see Ta-bles I, II), then these algorithms are used to define Kyber.KEM as key generation, encapsulation and decapsulation (see Table III). The transformation used is called FO transformation. Most of the attacks target the functions used in Kyber.PKE, but the attacks are against Kyber.KEM security. Kyber.PKE uses several functions, see [16], here are pre-sented the following functions: GenMatrix, Encode (E), De-code (D), Compress (Co) and Decompress (Dc), Also the hash and other auxiliar functions used in both Kyber.PKE and Kyber.KEM are denoted as and .
Table I Kyber.PKE.Keygen and Kyber.PKE.Encrypt
Table II Kyber.PKE.Decrypt
The following scheme shows how Kyber.KEM works, the algorithms Kyber.PKE.KeyGen, Kyber.PKE.Encrypt and Ky-ber.PKE.Decrypt are denoted as and respectively. Is important to highlight the re-encryption algorithm in the decapsulation (Table III) of Kyber.KEM as a common target of SCA. The re-encryption consists in the process of encypting again a decrypted message and checking if the ciphertext obtained is the same as the one received as input. Inside the re-encryption part of the algorithm the functions that are the primary target are the Encode and Decode functions. In this work we analyze three SCA (see Table IV) against Kyber.KEM, that use a side channel leakage to train an AI model. The attacks in [17] and [18], target both the re-encryption part of the decapsulation algorithm. In the case of [19] the target is the encapsulation, although still attacks the Encode function used in Kyber.PKE.Encrypt (see Table I).
Table III Kyber.KEM algorithms
And also I want to provide a definition of Kyber from its official website.
Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. Kyber is one of the finalists in the NIST post-quantum cryptography project. The submission lists three different parameter sets aiming at different security levels. Specifically, Kyber-512 aims at security roughly equivalent to AES-128, Kyber-768 aims at security roughly equivalent to AES-192, and Kyber-1024 aims at security roughly equivalent to AES-256.
The design of Kyber has its roots in the seminal LWE-based encryption scheme of Regev. Since Regev's original work, the practical efficiency of LWE encryption schemes has been improved by observing that the secret in LWE can come from the same distribution as the noise and also noticing that "LWE-like" schemes can be built by using a square (rather than a rectangular) matrix as the public key. Another improvement was applying an idea originally used in the NTRU cryptosystem to define the Ring-LWE and Module-LWE problems that used polynomial rings rather than integers. The CCA-secure KEM Kyber is built on top of a CPA-secure cryptosystem that is based on the hardness of Module-LWE.
Kyber's security is well-analyzed and based on a strong lattice-based cryptography framework. It offers excellent performance across software, hardware, and hybrid environments. Among the three structured lattice finalists (Kyber, Saber, NTRU), NIST chose Kyber for standardization, largely due to its superior efficiency, particularly in key generation, compared to NTRU. Additionally, there is more evidence supporting the MLWE problem, which Kyber is based on, than the MLWR and NTRU assumptions underlying Saber and NTRU, respectively.
I want to provide a definition of M-LWE based on this site:
The Module Learning With Errors problem (M-LWE) is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE, i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress towards narrowing this gap. More precisely, we prove that M-LWE with uniform η-bounded secret for any 1 ≤ η ≪ q and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of M-LWE, provided that the module rank d is at least logarithmic in the ring degree n. We also prove that the search version of M-LWE with large uniform secret and uniform η-bounded error is at least as hard as the standard M-LWE problem, if the number of samples m is close to the module rank d and with further restrictions on η. The latter result can be extended to provide the hardness of M-LWE with uniform η-bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.
As we're already know that Kyber was selected as a finalist. But there are also other KEMs nominee in the NIST Standardization. So, I asked ChatGPT, How does MLWE provide security comparing to the other problems ? Let's see some interesting points from ChatGPT.
Why M-LWE?
Strong Theoretical Foundation: M-LWE is an extension of the Learning with Errors (LWE) problem, which is well-studied and has a strong security foundation. The security of LWE (and thus MLWE) is tied to hard lattice problems like the Shortest Vector Problem (SVP) and the Shortest Independent Vectors Problem (SIVP), which are known to be hard even for quantum computers.
How it Works:
In MLWE, you work with modules over a ring (typically polynomials), which provides a structured form of LWE. The problem involves solving noisy linear equations over these modules, where the noise is added to prevent attackers from easily solving the equations.
Efficiency:
M-LWE-based schemes like Kyber are designed to be both secure and efficient. The structure of modules allows for smaller keys and faster operations compared to unstructured LWE, making Kyber particularly attractive for practical applications.
Why M-LWR?
Rounding vs. Noise: MLWR is similar to MLWE but replaces the addition of small random noise with a rounding operation. The rounding function introduces a small, deterministic error, which simplifies some computations.
How it Works:
Instead of adding a random noise vector (as in M-LWE), SABER introduces errors by rounding the entries of the result in a way that makes it hard to distinguish from random, while still being deterministic. This reduces the complexity and can lead to more efficient implementations.
Efficiency:
SABER’s use of rounding can lead to performance gains, particularly in terms of computation. However, the deterministic nature of rounding introduces concerns about security. While it is still considered secure, rounding might not provide as strong a security guarantee as the randomness used in M-LWE, which is why M-LWE is often seen as more robust.
Security Concerns:
The security reduction from worst-case lattice problems (like SIVP) to M-LWR is not as tight or as well-studied as for M-LWE. This means there is slightly less confidence in the long-term security of M-LWR compared to M-LWE.
Why NTRUEncrypt?
Historical Significance: NTRU is one of the oldest lattice-based cryptosystems and is based on a different type of lattice problem. The NTRU lattice is structured differently from the lattices used in LWE/M-LWE.
How it Works:
NTRU relies on polynomial arithmetic in a ring, where the security comes from the difficulty of finding short vectors in these structured lattices. The public key is a large polynomial, and encryption involves convolutions in the polynomial ring.
Efficiency:
NTRU has generally larger key sizes and slower key generation compared to Kyber (M-LWE) because of the structure and arithmetic it uses. While it is efficient in some respects, the operations required are more complex, which can slow down key generation and encryption.
Security Concerns:
The security of NTRU is well-understood, but the NTRU lattice structure has less supporting theoretical evidence than M-LWE. The reductions to worst-case lattice problems are not as strong, making M-LWE a more attractive option in terms of provable security. Additionally, because NTRU is not as widely studied in modern cryptographic contexts, there is less confidence in its long-term resistance to advanced attacks, especially quantum attacks.
Security: M-LWE provides a more robust and widely studied security foundation compared to MLWR and NTRUEncrypt. The noise in M-LWE introduces randomization that is harder to predict or attack, offering stronger resistance against both classical and quantum attacks.
Efficiency: Kyber’s use of M-LWE allows for efficient implementations with smaller key sizes and faster operations. SABER, while efficient, uses a rounding technique that, although fast, does not provide as strong a security guarantee as M-LWE. NTRU, though historically significant, does not match the efficiency of M-LWE based schemes due to its more complex operations and larger key sizes.
Theoretical Support: The reductions from M-LWE to hard lattice problems are tighter and more thoroughly researched than those for M-LWR and NTRUEncrypt. This gives Kyber a stronger theoretical basis, making it a more reliable choice for long-term security in the post-quantum era.
In summary, Kyber's use of M-LWE offers the best combination of security, efficiency, and theoretical support, making it the preferred choice over SABER and NTRU.
BIKE (Code-based)
Problem: Based on the hardness of decoding random linear codes.
Why M-LWE is Stronger: M-LWE benefits from smaller key sizes and better efficiency. Code-based schemes like BIKE typically have much larger keys and ciphertexts, making them less practical.
SIKE (Isogeny-based)
Problem: Based on the hardness of computing isogenies between elliptic curves.
Why M-LWE is Stronger: SIKE has very small key sizes but suffers from slow performance and recent vulnerabilities, as a classical attack recently broke SIKE. M-LWE, by contrast, has no known vulnerabilities and offers a better balance of security and performance.
HQC (Code-based)
Problem: Based on the hardness of decoding in the presence of random errors.
Why M-LWE is Stronger: Similar to BIKE, HQC suffers from larger key sizes and less efficiency compared to M-LWE. M-LWE based schemes like Kyber are more practical in a wide range of applications.
Classic McEliece (Code-based)
Problem: Based on the hardness of decoding a specific type of linear code.
Why M-LWE is Stronger: McEliece offers strong security but at the cost of extremely large public keys, making it impractical for many applications. M-LWE offers much smaller keys and better efficiency.
Key Takeaway: Kyber was selected by NIST primarily because of its strong security foundation in MLWE, backed by extensive theoretical and practical support, and its superior efficiency, particularly in comparison to SABER and NTRU.
Indistinguishability under non-adaptive and adaptive Chosen Ciphertext Attack (IND-CCA1, IND-CCA2) uses a definition similar to that of IND-CPA. However, in addition to the public key (or encryption oracle, in the symmetric case), the adversary is given access to a decryption oracle which decrypts arbitrary ciphertexts at the adversary's request, returning the plaintext. In the non-adaptive definition, the adversary is allowed to query this oracle only up until it receives the challenge ciphertext. In the adaptive definition, the adversary may continue to query the decryption oracle even after it has received a challenge ciphertext, with the caveat that it may not pass the challenge ciphertext for decryption (otherwise, the definition would be trivial).
The challenger generates a key pair PK, SK based on some security parameter k (e.g., a key size in bits), and publishes PK to the adversary. The challenger retains SK.
The adversary may perform any number of calls to the encryptions and decryption oracle based on arbitrary ciphertexts, or other operations.
The adversary is free to perform any number of additional computations or encryptions.
In the non-adaptive case (IND-CCA1), the adversary may not make further calls to the decryption oracle.
In the adaptive case (IND-CCA2), the adversary may make further calls to the decryption oracle, but may not submit the challenge ciphertext C.
Finally, the adversary outputs a guess for the value of b.
A scheme is IND-CCA1/IND-CCA2 secure if no adversary has a non-negligible advantage in winning the above game.
Eventually, the adversary submits two distinct chosen plaintexts M0,M1 to the challenger.
The challenger selects a bit b ∈ {0, 1} uniformly at random, and sends the "challenge" ciphertext C = E(PK, Mb) back to the adversary.
