FNP Kyber-1024 Post-Quantum Encryption

ELI5

Kyber is a way to encrypt messages using math problems that even quantum computers can’t solve. Regular encryption (RSA) uses the difficulty of factoring large numbers, which quantum computers could break in a few hours. Kyber uses lattice math instead, which stays hard even for quantum computers. Think of it like switching from a jigsaw puzzle (easy for quantum, hard for regular computers) to a Rubik’s cube variant (hard for both).

Technical Deep Dive

Why Post-Quantum Matters

Classical Cryptography (RSA-2048):

• Hardness: Integer factorization (2^112 classical security)
• Threat: Shor’s algorithm on quantum computer breaks in polynomial time
• NIST warning: “harvest now, decrypt later” attacks (adversaries collect encrypted messages today, decrypt when quantum arrives)

Post-Quantum (Kyber-1024):

• Hardness: Module-LWE (Learning With Errors) — lattice problem
• Threat: No known quantum algorithm; best quantum attack is Grover’s (2^64 work)
• Security: 128-bit quantum-resistant

Kyber-1024 Algorithm

Key Generation:

1. Sample random matrix A ∈ Z_q^{k×k} (k=4 for 1024 variant)
2. Sample secret s, e from small distribution
3. Compute public key pk = (A, t) where t = As + e
4. Secret key sk = s

Encapsulation (what client does):

Input: public key pk
1. Sample r, e₁, e₂ from small distribution
2. Compute u = A^T·r + e₁, v = t^T·r + e₂ + m
3. Output ciphertext (u, v) and shared secret m

Decapsulation (what server does with shared secret):

Input: secret key sk, ciphertext (u, v)
1. Compute m' = v - s^T·u
2. Output shared secret m'

The errors e, e₁, e₂ are small enough that noise rounds away, recovering m — but large enough to make the LWE problem hard.

Security Properties

IND-CCA2 (Indistinguishability under Chosen Ciphertext Attack):

• Attacker cannot distinguish encryptions of two chosen plaintexts
• Even if attacker can decrypt arbitrary ciphertexts (CCA)
• Resists adaptive attacks; proven in the QROM (Quantum Random Oracle Model)

Parameters (Kyber-1024):

• Public key size: 1,568 bytes
• Secret key size: 3,168 bytes
• Ciphertext size: 1,568 bytes
• Shared secret: 32 bytes
• Quantum security: 128 bits (Grover bound)

Key Rotation Strategy

FNP rotates Kyber keys yearly:

Year 1: Kyber-1024 key pair (A, pk)
Year 2: New Kyber-1024 key pair (A', pk')
Transition: Re-encapsulate all documents to new key

This limits exposure if a key is eventually compromised.

Key Terms

• Module-LWE → Lattice-based hardness assumption; quantum-resistant problem
• IND-CCA2 → Security notion: ciphertexts hide plaintext even against adaptive chosen-ciphertext attacks
• KEM (Key Encapsulation Mechanism) → Generates shared secret from public key; building block for symmetric encryption
• Ephemeral keys → Session-specific keys; long-term compromises don’t decrypt past sessions

Q&A

Q: Is Kyber-1024 actually hard, or just untested? A: It’s a NIST FIPS 203 standardized algorithm with peer-reviewed security proofs. Hardness is based on the Module-LWE problem, which has been studied for 15+ years. No polynomial-time attacks known, even for quantum computers.

Q: What happens if quantum computers become faster? A: The 128-bit security margin means quantum computers would need ~2^128 operations to break. Even exponential speedups (Grover) don’t close this gap. FNP can migrate to larger parameters (Kyber-512) if needed.

Q: Does every keystroke get a new Kyber ciphertext? A: No. FNP encapsulates once per session (at login), deriving a 32-byte shared secret. Insert/delete operations use symmetric encryption with that secret, not Kyber repeatedly.

Examples

Kyber is like a vault lock that uses the geometry of high-dimensional lattices instead of number factorization. Even if someone invents a magical tool for factoring (quantum computer), the lattice lock stays secure. It’s NIST’s approved way to protect secrets against future quantum theft.