Skip to main content

​
FNP - Cryptography - Kyber-1024 Post-Quantum Encryption

​
Summary (Explain Like I’m 5)

Imagine you and your friend need to exchange secret messages through a public mailbox (anyone can see what goes in, but not read the contents). Problem with old encryption (RSA): If a quantum computer ever exists, it can break RSA instantly. Kyber-1024 solves this: It uses a different kind of math problem (lattices instead of prime factorization) that even quantum computers struggle with. Simple version: You send a “locked box” (public key) to your friend. They put a shared secret inside and seal it. Only you can open it (with your secret key). Future quantum computers can’t pick the lock.

​
Technical Deep Dive

Kyber is a Module-Learning-With-Errors (MLWE) based Key Encapsulation Mechanism. It’s standardized in NIST FIPS 203. Design Parameters (Kyber-1024 variant):
ParameterValuePurpose
k (module rank)4Security parameter (k=1 → Kyber-512, k=3 → Kyber-768, k=4 → Kyber-1024)
n (poly degree)256NTT-friendly; working in Z_q[x]/(x^256 + 1)
q (modulus)3329Prime satisfying q ≡ 1 (mod 2n), enables NTT
η₁ (secret noise)2Centered binomial for secret key error distribution
η₂ (encaps noise)2Centered binomial for encapsulation error
d_u (u compress)10 bitsCompress u component in ciphertext
d_v (v compress)4 bitsCompress v component in ciphertext
Key Encapsulation Protocol: 
KeyGen() → (ek, dk):
  1. Sample: A ← U(Z_q^{k×k}) [uniform random matrix]
  2. Sample: s ← η₁^k [small secret vector]
  3. Sample: e ← η₁^k [small error vector]
  4. Compute: t = A·s + e mod q
  5. ek = (encode(t), seed_A) [public key: 1568 bytes]
  6. dk = (encode(s), ek, H(ek), z) [secret key: 2400 bytes]

Encaps(ek) → (ss, ct):
  1. Sample: m ← {0,1}^32 [message: 32 random bytes]
  2. Sample: y ← η₂^k, e₁ ← η₂^k, e₂ ← η₂ [errors]
  3. Compute: u = A^T·y + e₁ mod q [k polynomials]
  4. Compute: v = ⟨t, y⟩ + e₂ + ⌊q/2⌋·m mod q
  5. Compress: u_c = compress(u, d_u), v_c = compress(v, d_v)
  6. ct = (u_c, v_c) [ciphertext: 1408 bytes]
  7. ss = PRF(m, H(ct)) [shared secret: 32 bytes]
  Return (ss, ct)

Decaps(dk, ct) → ss:
  1. Decompress: u = decompress(u_c), v = decompress(v_c)
  2. Compute: m' = decode(⌊q/2⌋ - ⟨s, u⟩ + v mod q)
  3. ss = PRF(m', H(ct))
  Return ss
Security: IND-CCA2 (indistinguishable ciphertexts under chosen-ciphertext attack). Quantum Security: 128 bits (NIST hardness estimate: 2^256 classical → 2^128 quantum via Grover’s algorithm). NTT Arithmetic: 
Polynomial multiplication in Z_q[x]/(x^256+1):
  Classical: O(n²) = O(65,536) operations
  NTT: O(n log n) = O(2048) operations

  (a * b) = iNTT(NTT(a) ⊙ NTT(b))  [⊙ = element-wise multiply]

Efficiency: 256-dimensional polynomial multiplication ≈ 3.4ms on modern CPU

​
Mermaid Diagrams

​
Key Terms

  • MLWE → Module-Learning-With-Errors; lattice hardness assumption with module structure
  • KEM → Key Encapsulation Mechanism; wraps encryption to achieve IND-CCA2 security
  • NTT → Number-Theoretic Transform; FFT over finite field; enables O(n log n) polynomial multiplication
  • IND-CCA2 → Indistinguishability under Chosen-Ciphertext Attack; strongest semantic security notion
  • Quantum-Resistant → Secure against known quantum algorithms (Grover’s, Shor’s algorithm family)
  • Lattice Problem → Hard problem in lattice theory (SVP, LWE); resists quantum computers
  • Polynomial Ring → Z_q[x]/(x^256+1); arithmetic in ring of polynomials with mod q coefficients
  • Post-Quantum → Cryptography designed to resist quantum computer attacks

​
Q/A

Q: Why switch from RSA to Kyber if RSA works fine today? A: RSA is broken by Shor’s algorithm on quantum computers. Kyber is based on lattice problems that don’t have known quantum speedups. Since quantum computers could appear in 10-20 years, we must migrate now (harvest-now-decrypt-later threat). Q: How big are Kyber keys compared to RSA? A: Kyber-1024: 1568 bytes public key. RSA-3072: ~400 bytes. Kyber is ~4x larger but acceptable for most applications. Trade-off: key size vs. quantum security. Q: If the ciphertext is 1408 bytes, why is it just 1408 bytes when you need to encapsulate a 32-byte secret? A: Kyber doesn’t encrypt the 32-byte secret directly. Instead: (1) Sample random m ← ^32, (2) Encapsulate m into 1408-byte ciphertext, (3) Derive shared secret ss = PRF(m, H(ct)). The ciphertext contains m hidden in a lattice problem - impossible to recover without secret key. Q: What does “compression” mean in d_u=10 and d_v=4? A: Polynomials in Z_q have coefficients mod 3329. Full precision ≈ 12 bits per coefficient. d_u=10 means store only 10 bits per coefficient for u, d_v=4 means 4 bits per coefficient for v. Lossy compression: small error introduced but security maintained (verifiable by IND-CCA2 proof). Q: Is Kyber proven to be quantum-safe? A: Not proven; based on hardness of MLWE. Lattice problems have resisted 30+ years of cryptanalysis. No known quantum algorithm breaks MLWE better than Grover (generic). NIST selected Kyber after 6-year evaluation process, so it’s conservative estimate.

​
Example / Analogy

Puzzle Lock Analogy: Traditional RSA:
  • Merchant gives you a puzzle: “Factor this 2048-bit number”
  • You can’t solve it (takes 2^128 operations)
  • Quantum computer laughs: “I’ll solve it in polynomial time” ✗
Kyber-1024:
  • Merchant gives you a harder puzzle: “Find short vector in 1024-dimensional lattice”
  • You can’t solve it (takes 2^128 operations classically)
  • Quantum computer tries Grover: “Still 2^64 operations!” ✓ (still hard!)
  • Quantum computer tries Shor variants: “No known algorithm breaks MLWE” ✓
Real-world FNP Scenario: In your encrypted document editing system:
  1. Server generates Kyber keypair, publishes public key
  2. Each client wants to send edits using content encryption
  3. Client A encrypts character content:
    • Encaps(server_pk) → (shared_secret, ciphertext)
    • Encrypt character with AES(shared_secret)
    • Send (ciphertext, encrypted_character) to server
  4. Server decrypts:
    • Decaps(sk, ciphertext) → shared_secret
    • Decrypt character with AES(shared_secret)
    • Store encrypted_character in document
Why it matters: If this system is deployed today and quantum computers appear in 2035, adversaries can’t retroactively decrypt all stored characters (unlike RSA). Kyber ensures forward secrecy.
Cross-References: System Overview, FNP Protocol Flow, M²-ORE Encryption, Halo2 Circuits Category: Cryptography | Post-Quantum | Key Exchange | NIST Standard Difficulty: Advanced ⭐⭐⭐⭐ Updated: 2025-11-28