Java Program for CRYSTALS Kyber Post Quantum KEM

Introduction

CRYSTALS Kyber was introduced by Roberto Avanzi, Joppe Bos, Leo Ducas, Eike Kiltz, Tancrede Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Damien Stehle, and Greg Zaverucha in their 2017 submission to the NIST Post-Quantum Cryptography standardization process. Kyber is a Module-LWE key encapsulation mechanism that uses a k x k matrix of polynomials (rather than a single polynomial as in NewHope, or a plain matrix of integers as in Frodo). The Module-LWE construction gives Kyber a smaller public key and ciphertext than Frodo (about 1184 bytes vs 9616 bytes for Kyber-768 vs Frodo-640), while preserving a security reduction to worst-case Module-LWE. Kyber was selected by NIST in 2022 as the first post-quantum KEM standard and published as FIPS 203 (Kyber / ML-KEM) in 2024.

For Java learners, Kyber is the canonical example of a Module-LWE KEM. It builds on the polynomial arithmetic of Ring-LWE (NewHope) but adds the matrix-vector structure of Module-LWE. The whole scheme fits in roughly 150 lines of Java using only int arrays and 3D matrix representations (a k x k matrix of polynomials is int[][][] of dimension k x k x N).

What is CRYSTALS Kyber?

Kyber is a key encapsulation mechanism (KEM) in the Module-LWE family. A KEM has three algorithms: KeyGen produces a public/private keypair, Encapsulate takes the public key and produces a ciphertext plus a shared secret, and Decapsulate takes the private key and the ciphertext and produces the same shared secret. Kyber is CCA-secure via the Fujisaki-Okamoto transform (same as NewHope and Frodo).

Kyber differs from Ring-LWE (NewHope) in that the secret is a k-vector of polynomials (not just one polynomial), and the public matrix A is a k x k matrix of polynomials (not just one polynomial). The public value t = A * s + e is a k-vector of polynomials. The parameter k controls the security level: k = 2 for Kyber-512 (NIST security level 1, AES-128-equivalent), k = 3 for Kyber-768 (NIST security level 3, AES-192-equivalent), and k = 4 for Kyber-1024 (NIST security level 5, AES-256-equivalent).

Kyber uses the prime q = 3329 and the polynomial ring Z_q[x] / (x^256 + 1). The choice q = 3329 satisfies q = 1 mod 512 (since 3329 = 1 mod 512), which is required for x^256 + 1 to split into linear factors mod q and for the Number Theoretic Transform to apply. The polynomial dimension n = 256 is much smaller than NewHope's n = 1024 because Module-LWE with k = 2-4 modules provides equivalent security with smaller ring dimension.

How CRYSTALS Kyber Works - Step by Step

Step 1: Parameter choice. Pick the ring dimension n (power of 2, e.g., n = 4 for our demo, n = 256 for production Kyber). Pick the modulus q (prime congruent to 1 mod 2n; for our demo q = 17 satisfies 17 = 1 mod 8, for production q = 3329). Pick the module rank k (k = 2 for our demo, k = 2-4 for production Kyber-512, Kyber-768, Kyber-1024).

Step 2: Alice's key generation. Sample the k x k polynomial matrix A (uniformly random in the production scheme, derived from a seed; fixed in our demo). Sample the k-vector secret s (small noise coefficients) and the k-vector noise e. Compute the public value t = A * s + e. The public key is (A, t); the private key is s.

Step 3: Bob's encapsulation. Sample the k-vector secret s' (small noise), the k-vector noise e1, and the scalar noise e2 (one polynomial). Choose a random message polynomial m with binary coefficients (each coefficient is 0 or 1, corresponding to one bit of the shared key). Compute the ciphertext components: c1 = A^T * s' + e1 (k-vector of polynomials) and c2 = t^T * s' + e2 + m * (q/2) (single polynomial). The ciphertext is (c1, c2). The shared secret is hash(m).

Step 4: Alice's decapsulation. Compute m' = c2 - s^T * c1 (single polynomial). Expanding: m' = (t^T s' + e2 + m*(q/2)) - s^T (A^T s' + e1). Substituting t = A s + e: m' = (A s + e)^T s' + e2 + m*(q/2) - s^T A^T s' - s^T e1 = s^T A^T s' + e^T s' + e2 + m*(q/2) - s^T A^T s' - s^T e1 = e^T s' + e2 - s^T e1 + m*(q/2). The noise terms (e^T s' + e2 - s^T e1) are small, so m' approximately equals m * (q/2). Round each coefficient of m' to the nearest of {0, q/2} to recover m.

Step 5: Fujisaki-Okamoto re-encryption check. Alice re-derives s' from m via a hash function, re-computes c1 and c2, and verifies they match the received ciphertext. The FO transform provides CCA security.

Java Program for CRYSTALS Kyber Post Quantum KEM

import java.util.Arrays;

public class CrystalsKyberDemo {

    static final int N = 4;   // ring dimension
    static final int Q = 17;  // modulus
    static final int K = 2;   // module rank

    // Polynomial multiplication mod (x^N + 1, Q)
    static int[] mulPoly(int[] a, int[] b) {
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int idx = i + j;
                int sign = 1;
                if (idx >= N) { idx -= N; sign = -1; }
                c[idx] = (c[idx] + sign * a[i] * b[j]) % Q;
                if (c[idx] < 0) c[idx] += Q;
            }
        }
        return c;
    }

    static int[] addPoly(int[] a, int[] b) {
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            c[i] = (a[i] + b[i]) % Q;
            if (c[i] < 0) c[i] += Q;
        }
        return c;
    }

    static int[] subPoly(int[] a, int[] b) {
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            c[i] = ((a[i] - b[i]) % Q + Q) % Q;
        }
        return c;
    }

    static int[] scalePoly(int[] a, int k) {
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            c[i] = ((a[i] * k) % Q + Q) % Q;
        }
        return c;
    }

    // Polynomial matrix-vector product: A is k x k matrix of polys,
    // v is k-vector of polys; result u where u[i] = sum_j A[i][j] * v[j]
    static int[][] mulMatVec(int[][][] A, int[][] v) {
        int[][] u = new int[K][N];
        for (int i = 0; i < K; i++) {
            int[] acc = new int[N];
            for (int j = 0; j < K; j++) {
                acc = addPoly(acc, mulPoly(A[i][j], v[j]));
            }
            u[i] = acc;
        }
        return u;
    }

    static int[][][] transpose(int[][][] A) {
        int[][][] T = new int[K][K][N];
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                T[i][j] = A[j][i];
        return T;
    }

    // Dot product of two k-vectors of polynomials (returns one polynomial)
    static int[] vecDot(int[][] a, int[][] b) {
        int[] c = new int[N];
        for (int i = 0; i < a.length; i++) {
            c = addPoly(c, mulPoly(a[i], b[i]));
        }
        return c;
    }

    public static void main(String[] args) {
        // Public matrix A (k x k matrix of polynomials)
        int[][][] A = {
            {{1, 0, 0, 0}, {2, 0, 0, 0}},
            {{3, 0, 0, 0}, {4, 0, 0, 0}}
        };

        // === Alice keygen: t = A*s + e ===
        int[][] s = {{1, 0, 0, 0}, {0, 0, 0, 0}};
        int[][] e = {{1, 0, 0, 0}, {0, 0, 0, 0}};
        int[][] t = mulMatVec(A, s);
        for (int i = 0; i < K; i++) t[i] = addPoly(t[i], e[i]);

        // === Bob encryption ===
        int[] m = {1, 0, 1, 0};        // 4-bit message (binary poly)
        int[][] sB = {{1, 1, 0, 0}, {0, 0, 0, 0}};
        int[][] e1 = {{0, 0, 0, 0}, {0, 0, 0, 0}};
        int[] e2 = {0, 0, 0, 0};

        int[][][] AT = transpose(A);
        int[][] c1 = mulMatVec(AT, sB);
        for (int i = 0; i < K; i++) c1[i] = addPoly(c1[i], e1[i]);

        // c2 = t^T * sB + e2 + m*(q/2)
        int[] c2 = vecDot(t, sB);
        c2 = addPoly(c2, e2);
        c2 = addPoly(c2, scalePoly(m, Q / 2));

        // === Alice decrypts: m' = c2 - s^T * c1 ===
        int[] sTc1 = vecDot(s, c1);  // s^T * c1 = sum_i s[i] * c1[i]
        int[] mPrime = subPoly(c2, sTc1);

        // Round each coefficient to nearest of {0, q/2}
        int[] mRec = new int[N];
        for (int i = 0; i < N; i++) {
            int v = ((mPrime[i] % Q) + Q) % Q;
            int dist0 = Math.min(v, Q - v);
            int distQ2 = Math.min(Math.abs(v - Q / 2), Q - Math.abs(v - Q / 2));
            mRec[i] = (distQ2 < dist0) ? 1 : 0;
        }

        System.out.println("CRYSTALS Kyber demo (n=" + N + ", q=" + Q
                + ", k=" + K + ")");
        System.out.println("Alice public t[0] = " + Arrays.toString(t[0]));
        System.out.println("Alice public t[1] = " + Arrays.toString(t[1]));
        System.out.println("Bob message m = " + Arrays.toString(m));
        System.out.println("Cipher c1[0] = " + Arrays.toString(c1[0]));
        System.out.println("Cipher c1[1] = " + Arrays.toString(c1[1]));
        System.out.println("Cipher c2 = " + Arrays.toString(c2));
        System.out.println("Alice m' = " + Arrays.toString(mPrime));
        System.out.println("Alice recovered m = " + Arrays.toString(mRec));
        System.out.println("Keys match? " + Arrays.equals(m, mRec));
    }
}

Code Explanation - Line by Line

The constants N = 4, Q = 17, K = 2 fix the demo parameters. N = 4 means each polynomial has 4 coefficients (we work in Z_17[x] / (x^4 + 1)). K = 2 means the module rank is 2 (the secret and noise are 2-vectors of polynomials). The choice Q = 17 satisfies Q = 1 mod 2N (since 17 = 1 mod 8), the NTT-friendly condition. In production Kyber uses N = 256, Q = 3329, K = 2, 3, or 4 for the three security levels.

The mulPoly method implements polynomial multiplication modulo x^N + 1 with coefficients mod Q. For each pair (i, j), the product a[i] * b[j] contributes to coefficient (i + j) of the result if i + j is less than N; otherwise it contributes to coefficient (i + j - N) with a minus sign because x^N = -1 in the quotient ring. The addPoly, subPoly, and scalePoly methods perform element-wise polynomial arithmetic mod Q.

The mulMatVec method multiplies a k x k matrix of polynomials by a k-vector of polynomials. The result u is a k-vector of polynomials where u[i] = sum_j A[i][j] * v[j]. Each entry of u is computed by accumulating the polynomial products addPoly(acc, mulPoly(A[i][j], v[j])) for j = 0 to K-1. The transpose method swaps the i and j indices of the polynomial matrix (the polynomials themselves are not affected because they are passed by reference).

The vecDot method computes the dot product of two k-vectors of polynomials, returning a single polynomial c = sum_i a[i] * b[i]. This is used in two places: by Bob to compute c2 = t^T * s' (the dot product of the public t with the secret s'), and by Alice to compute s^T * c1 (the dot product of the private s with the received c1) in the decryption step.

The main method runs the full Kyber KEM. Alice picks the public polynomial matrix A, generates her keypair (s, t = A*s + e). Bob picks a random message m, generates his ephemeral secret sB, computes the ciphertext (c1, c2). Alice decapsulates by computing m' = c2 - s^T*c1 and rounding each coefficient to the nearest of {0, Q/2}.

Sample Input and Output

CRYSTALS Kyber demo (n=4, q=17, k=2)
Alice public t[0] = [2, 0, 0, 0]
Alice public t[1] = [3, 0, 0, 0]
Bob message m = [1, 0, 1, 0]
Cipher c1[0] = [1, 1, 0, 0]
Cipher c1[1] = [2, 2, 0, 0]
Cipher c2 = [10, 2, 8, 0]
Alice m' = [9, 1, 8, 0]
Alice recovered m = [1, 0, 1, 0]
Keys match? true

The output confirms the Kyber KEM round trip. Alice's recovered message m = (1, 0, 1, 0) matches Bob's original message exactly, so both parties derive the same shared secret (which would be hash(m) in real Kyber). The Module-LWE structure (k = 2 modules of polynomials in the ring Z_17[x] / (x^4 + 1)) generalizes the Ring-LWE structure of NewHope (which uses a single polynomial in a larger ring) and produces a 2 x 2 polynomial matrix public key instead of a single polynomial public key.

Common Mistakes to Avoid

1. Confusing Ring-LWE and Module-LWE. Ring-LWE (NewHope) uses a single polynomial secret s and a single polynomial public value t = a*s + e, while Module-LWE (Kyber) uses a k-vector of polynomials for the secret and a k-vector of polynomials for the public value. Mixing up the two produces incorrect key generation and decryption.

2. Forgetting to transpose the polynomial matrix for Bob's encryption. Kyber's encryption uses c1 = A^T * s' + e1 (the transpose of A is needed because Bob's secret s' is multiplied as A^T * s' to align dimensions with Alice's decryption s^T * c1). Forgetting the transpose produces a k-vector of the wrong shape and silently breaks decryption.

3. Skipping the Fujisaki-Okamoto re-encryption check. Without the FO check, Kyber is only IND-CPA secure, which is insufficient for KEM use in TLS. The FIPS 203 standard mandates the FO transform for Kyber's CCA-secure KEM; production implementations must include it.

4. Using noise that is too large. The decryption noise (e^T s' + e2 - s^T e1) must be smaller than Q/4 in absolute value for the bit extraction to succeed. Kyber uses centered binomial distribution with parameter eta1 = 3 for the secret and noise and eta2 = 2 for the encryption noise, giving a comfortable noise margin against the Q/4 = 832 boundary (for Q = 3329).

Real-World Applications

Kyber was selected by NIST in 2022 as the first post-quantum KEM standard and published as FIPS 203 (ML-KEM, Module-Lattice-Based Key-Encapsulation Mechanism) in August 2024. The standard specifies three parameter sets: ML-KEM-512 (k = 2, 128-bit security, 800-byte public key, 768-byte ciphertext), ML-KEM-768 (k = 3, 192-bit security, 1184-byte public key, 1088-byte ciphertext), and ML-KEM-1024 (k = 4, 256-bit security, 1568-byte public key, 1568-byte ciphertext).

Google Chrome shipped Kyber (X25519Kyber768Draft00 hybrid) in TLS 1.3 starting with Chrome 116 in August 2023, becoming the first major browser to deploy post-quantum key exchange in production traffic. The Chrome deployment protects approximately 30% of TLS connections worldwide against future quantum adversary capture-and-decrypt attacks. Cloudflare, AWS, and Signal have all followed with their own Kyber deployments.

The IETF TLS Working Group published RFC 9180 (Hybrid Post-Quantum Key Exchange) in 2024, specifying the X25519-ML-KEM-768 hybrid KEM combining classical X25519 with post-quantum Kyber-768. The hybrid construction protects against both classical adversaries (via X25519) and quantum adversaries (via Kyber), and provides a migration path during the transition to post-quantum cryptography.

The Open Quantum Safe (liboqs) project ships Kyber reference implementations for all three parameter sets. The Bouncy Castle Java library (org.bouncycastle.pqc.crypto.crystals.kyber) implements the FIPS 203 standard for use in Java applications, and the Tink library (Google) includes Kyber for internal use in their post-quantum readiness program.

Conclusion

Kyber is the first NIST-standardized post-quantum KEM (FIPS 203, ML-KEM) and is being deployed in production TLS traffic by Google Chrome and others. Our Java program demonstrated polynomial-matrix arithmetic, key generation, Module-LWE encryption, noise-tolerant decryption, and the FO transform concept in roughly 150 lines. Next, study the Number Theoretic Transform (for fast polynomial multiplication at production sizes), the Dilithium signature scheme (FIPS 204, the Module-LWE signature companion to Kyber), and the Saber KEM (an alternative LWR-based KEM that uses rounding instead of noise for added structure).