CRYSTALS-Kyber
ML-KEM / Kyber: Post-Quantum Key Encapsulation Mechanism
Overview
ML-KEM (Kyber) is a post-quantum cryptographic algorithm based on module learning-with-errors (MLWE). It is a Key Encapsulation Mechanism (KEM) designed for secure key exchange and encryption resistant to attacks by quantum computers.
Full name: Module-LWE Key Encapsulation Mechanism
Also known as: Kyber (Crystals-Kyber)
Submitted to: NIST Post-Quantum Cryptography Standardization Project
Selected as: The sole KEM finalist for standardization in July 2022
Standardized as: ML-KEM by NIST in FIPS 203 (finalized 2024)
Design Goals
Post-quantum security: Resistant to attacks from quantum computers using Shor’s and Grover’s algorithms
High efficiency: Small key sizes, fast computation, and low memory usage
Drop-in KEM replacement: Easily replaces traditional schemes like RSA or Diffie-Hellman
Simplicity: Clean structure with only three main operations:
KeyGen,Encaps,Decaps
Core Operations
ML-KEM is a KEM not a full public-key encryption scheme so its job is to securely establish shared keys using encapsulation.
1. KeyGen() → (pk, sk)
Generates a public/private keypair
Public key
pkis used to encrypt (encapsulate)Secret key
skis used to decrypt (decapsulate)
2. Encaps(pk) → (ct, ss)
Encrypts a shared secret
ct: Ciphertext (to be sent to recipient)ss: Shared secret (for the sender to use)
3. Decaps(ct, sk) → ss'
Decrypts ciphertext using the private key
Returns the same shared secret
ss'(which should equal the sender’sssif the ciphertext is valid)
Parameter Sets
ML-KEM-512
128-bit (NIST Level 1)
800 bytes
800 bytes
1632 bytes
32 bytes
ML-KEM-768
192-bit (Level 3)
1184 bytes
1184 bytes
2400 bytes
32 bytes
ML-KEM-1024
256-bit (Level 5)
1568 bytes
1568 bytes
3168 bytes
32 bytes
Each variant provides a tradeoff between security level and bandwidth. In Cypher we use ML-KEM-768 for the perfect middle ground of security and performance and will be releasing a NPM package for mobile developers to allow them to implement Kyber 768 like we did for Cypher.
How It Works (Simplified)
ML-KEM is based on module learning-with-errors (MLWE), a hard lattice problem that even quantum computers cannot solve efficiently.
Public keys are short vectors over a polynomial ring.
Encapsulation involves sampling random secrets and adding small error terms (noise).
Decapsulation uses the secret key to reverse the operation and recover the shared secret.
A final hash step derives the session key.
Important Concepts:
Lattices: Mathematical structures resistant to quantum attacks.
Error terms (noise): Critical for security; ensures hardness of recovering the plaintext.
Rejection sampling and compression: Keeps ciphertext sizes small and leakage low.
Security Considerations
Quantum security: Based on LWE, believed to be secure against quantum attacks.
IND-CCA2: ML-KEM achieves indistinguishability under adaptive chosen ciphertext attack (IND-CCA2), critical for TLS and other secure protocols.
Error leakage mitigations: Uses hashing and compression techniques to mitigate side channels.
Side-channel resistance: Implementations must avoid timing attacks constant-time arithmetic is crucial.
References
Last updated