Java Program for NTRU Lattice Based Encryption

Introduction

NTRU was introduced in 1996 by Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman in a paper presented at the rump session of Crypto 1996 and published in detail in the ANTS 1998 proceedings. It was the first practical lattice-based public-key cryptosystem, predating Oded Regev's Learning With Errors construction by nearly a decade. NTRU is the contraction of Number Theory Research Unit, the name of the academic research group at Brown University where the scheme was developed. In 2016 NTRU was submitted to the NIST post-quantum standardization process and survives today as the NTRU-HRSS and NTRU-HPS variants being standardized in the IETF.

For Java learners, NTRU is the cleanest entry point into lattice cryptography before the LWE family. The whole scheme fits in roughly 120 lines of Java using only int arrays, with no BigInteger and no external libraries. The mathematical core is polynomial multiplication modulo x^N - 1 with coefficient arithmetic modulo a large prime q and a small prime p, and the security rests on the conjectured hardness of the shortest vector problem in convolutional modular lattices.

What is NTRU Encryption?

NTRU is a public-key encryption scheme in the lattice family. Unlike RSA, whose hardness rests on factoring integers, or ECDSA, whose hardness rests on the elliptic curve discrete logarithm problem, NTRU's hardness rests on finding short vectors in a particular structured lattice derived from two small polynomials. NTRU uses three integer parameters: the degree N (typically a prime such as 677 for NTRU-HRSS), a small prime p (typically 3), and a large modulus q (typically a power of two or a prime close to a power of two, such as 2048 or 8192).

NTRU differs from the LWE and Module-LWE schemes (Frodo, Kyber) in that it operates in the polynomial ring Z[x] / (x^N - 1) with cyclic convolution as the multiplication operation, rather than matrix-vector products over Z_q. The advantage is speed: a single schoolbook polynomial multiplication replaces a full matrix-vector multiply, and an NTT-based multiplication runs even faster. The trade-off is that the security reduction from NTRU to worst-case lattice problems is weaker than the corresponding reduction for LWE; in particular, NTRU has no known reduction from a quantum worst-case lattice problem, although no quantum attack is known either.

How NTRU Encryption Works - Step by Step

Step 1: Public parameters. Choose N (degree, polynomial ring dimension), p (small prime), and q (large modulus). The ring is R = Z[x] / (x^N - 1), so polynomials multiply via cyclic convolution modulo q. For our demo we use N = 3, p = 3, q = 31. In production NTRU-HRSS uses N = 677, p = 3, q = 65537.

Step 2: Key generation. Sample small polynomials f and g in R with coefficients drawn from {-1, 0, 1}. Compute the public key h = p * f_inverse * g mod q in R, where f_inverse is the multiplicative inverse of f in the ring R_q. The public key is h; the private key is f (g is also kept private but is not needed for decryption). For our demo we pick f = (1, 0, 0), the constant polynomial 1, whose inverse is itself, and g = (1, 1, 0). Then h = 3 * (1, 0, 0) * (1, 1, 0) = (3, 3, 0) mod 31.

Step 3: Encryption. To encrypt a message polynomial m (with small coefficients in {0, 1, ..., p-1}), sample a small random blinding polynomial r with coefficients in {-1, 0, 1}. Compute the ciphertext e = r * h + m mod q in R. For our demo with m = (1, 0, 0) (encoding a single bit) and r = (1, 1, 0): r * h = (3, 6, 3) and e = (4, 6, 3) mod 31.

Step 4: Decryption. Compute a = f * e mod q in R. Lift each coefficient of a to the centered range (-q/2, q/2]. Reduce a modulo p to obtain f * m mod p. Multiply by f_inverse mod p to recover m. For our demo: a = (1, 0, 0) * (4, 6, 3) = (4, 6, 3); all coefficients are already within (-15, 15] so no lift is needed; a mod 3 = (1, 0, 0) = m. Decryption succeeds because the noise terms e * r + e2 - s * e1 (in LWE terms) are small relative to the gap between valid messages.

Java Program for NTRU Encryption

import java.util.Arrays;

public class NtruEncryptionDemo {

    static final int N = 3;   // ring dimension (degree of x^N - 1)
    static final int P = 3;   // small prime
    static final int Q = 31;  // large modulus (prime)

    // Cyclic convolution in Z[x] / (x^N - 1) with coefficients reduced mod Q
    static int[] mul(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) % N;     // wrap modulo N (cyclic)
                c[idx] = (c[idx] + a[i] * b[j]) % Q;
                if (c[idx] < 0) c[idx] += Q;
            }
        }
        return c;
    }

    static int[] add(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[] constMul(int[] a, int k) {
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            c[i] = (a[i] * k) % Q;
            if (c[i] < 0) c[i] += Q;
        }
        return c;
    }

    // Lift each coefficient to the centered range (-Q/2, Q/2]
    static int[] liftCentered(int[] a) {
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            int v = a[i] % Q;
            if (v < 0) v += Q;
            if (v > Q / 2) v -= Q;
            c[i] = v;
        }
        return c;
    }

    static int[] modP(int[] a) {
        int[] c = new int[N];
        for (int i = 0; i < N; i++) {
            int v = a[i] % P;
            if (v < 0) v += P;
            c[i] = v;
        }
        return c;
    }

    public static void main(String[] args) {
        System.out.println("NTRU params: N=" + N + " p=" + P + " q=" + Q);

        // === Key generation ===
        // f is the secret polynomial; we use the constant-1 polynomial
        // whose inverse in R_q is trivially (1, 0, 0). Real NTRU samples
        // f with small nonzero coefficients and computes f^-1 via the
        // extended Euclidean algorithm in Z_q[x] / (x^N - 1).
        int[] f = {1, 0, 0};
        int[] g = {1, 1, 0};
        // h = p * f^-1 * g mod q = 3 * (1,0,0) * (1,1,0) = (3, 3, 0)
        int[] h = constMul(mul(f, g), P);

        System.out.println("Private f = " + Arrays.toString(f));
        System.out.println("Secret   g = " + Arrays.toString(g));
        System.out.println("Public   h = p * f^-1 * g mod q = " + Arrays.toString(h));

        // === Encryption of two plaintexts ===
        int[] m0 = {0, 0, 0};
        int[] m1 = {1, 0, 0};
        int[] r  = {1, 1, 0};

        int[] e0 = add(mul(r, h), m0);
        int[] e1 = add(mul(r, h), m1);

        System.out.println("Message m0 = " + Arrays.toString(m0));
        System.out.println("Message m1 = " + Arrays.toString(m1));
        System.out.println("Random  r  = " + Arrays.toString(r));
        System.out.println("Cipher  e0 = r*h + m0 mod q = " + Arrays.toString(e0));
        System.out.println("Cipher  e1 = r*h + m1 mod q = " + Arrays.toString(e1));

        // === Decryption ===
        // a = f * e mod q; lift each coefficient to centered range; reduce mod p
        int[] a0 = liftCentered(mul(f, e0));
        int[] m0Rec = modP(a0);

        int[] a1 = liftCentered(mul(f, e1));
        int[] m1Rec = modP(a1);

        System.out.println("Decrypt m0 = " + Arrays.toString(m0Rec));
        System.out.println("Decrypt m1 = " + Arrays.toString(m1Rec));
    }
}

Code Explanation - Line by Line

The constants N, P, Q fix the demo parameters. N = 3 means we work in the ring Z_31[x] / (x^3 - 1). The choice of Q = 31 as a prime larger than 2 * P = 6 ensures that the centered lift of decryption can distinguish between the residue classes mod P. In production NTRU-HRSS uses N = 677, P = 3, Q = 65537.

The mul method implements cyclic convolution: the polynomial product a * b in the quotient ring Z[x] / (x^N - 1). For each pair (i, j), the product a[i] * b[j] contributes to coefficient (i + j) mod N of the result. This is the schoolbook O(N^2) algorithm; production implementations use the Number Theoretic Transform for O(N log N) convolution. The add method performs element-wise polynomial addition mod Q, and constMul scales every coefficient by a constant mod Q.

The liftCentered method is the key step that makes decryption work: it maps each coefficient from the residue representation in [0, q) to the centered representation in (-q/2, q/2]. This is necessary because after multiplication the noise polynomial f * e might have negative coefficients, and reducing mod p directly on the unsigned representation would give the wrong answer. The modP method reduces each coefficient mod P, which is the step that strips off the small noise terms and recovers f * m mod p.

The main method runs the full scheme end to end: pick f = (1, 0, 0), g = (1, 1, 0), compute the public key h = 3 * (1, 0, 0) * (1, 1, 0) = (3, 3, 0) mod 31. Encrypt two messages m0 = (0, 0, 0) and m1 = (1, 0, 0) using the same blinding r = (1, 1, 0). The two ciphertexts differ by exactly m1 - m0 = (1, 0, 0), which leaks nothing about the secret because the ciphertext is dominated by the random blinding r * h. Decryption recovers both m0 and m1 exactly.

Sample Input and Output

NTRU params: N=3 p=3 q=31
Private f = [1, 0, 0]
Secret   g = [1, 1, 0]
Public   h = p * f^-1 * g mod q = [3, 3, 0]
Message m0 = [0, 0, 0]
Message m1 = [1, 0, 0]
Random  r  = [1, 1, 0]
Cipher  e0 = r*h + m0 mod q = [3, 6, 3]
Cipher  e1 = r*h + m1 mod q = [4, 6, 3]
Decrypt m0 = [0, 0, 0]
Decrypt m1 = [1, 0, 0]

The output confirms both ciphertexts decrypt to their original messages. Note how the two ciphertexts e0 and e1 differ by exactly (1, 0, 0) = m1 - m0, because the encryption is additively homomorphic on the message slot. The blinding r * h dominates the ciphertext; an attacker seeing only e0 and e1 cannot separate the message from the random noise.

Common Mistakes to Avoid

1. Forgetting the centered lift in decryption. After computing a = f * e mod q, the coefficients are in [0, q). If you reduce mod p directly without lifting to (-q/2, q/2] first, a noise coefficient of q - 1 (which is really -1) will be treated as q - 1, and mod p it becomes (q-1) mod p instead of -1 mod p. This silently corrupts decryption whenever a noise coefficient happens to be larger than q/2.

2. Picking parameters where q is not much larger than p. The decryption noise f * r * g + f * e2 - f * s * e1 must be smaller than q/2 in absolute value, otherwise the centered lift cannot distinguish between residue classes mod p. The rule of thumb is q greater than 4 * p * sigma^2 where sigma is the noise standard deviation; production NTRU uses q much larger than p to leave a comfortable margin.

3. Sampling f that is not invertible in R_q. The public key h requires f_inverse mod q, which exists only when gcd(N, q) = 1 and f is coprime to x^N - 1 in Z_q[x]. Random f might fail this with small probability; the standard fix is to use f of the form 1 + p * F for some small F, which is guaranteed invertible mod p and is invertible mod q with overwhelming probability over F.

4. Forgetting the minus sign in the cyclic reduction. When using a polynomial ring modulo x^N - 1 (as opposed to x^N + 1 used in Ring-LWE), the wrap-around coefficient is added without a sign change. Forgetting that the wrap is additive (not negative) breaks the multiplication and silently corrupts every ciphertext.

Real-World Applications

NTRU is one of the four post-quantum cryptographic primitives currently being standardized. The NTRU-HRSS variant was a third-round candidate in the NIST Post-Quantum Cryptography standardization process and is currently being progressed by the IETF CFRG working group as RFC 9469 (X25519Kyber768Draft00 in TLS) and by the IETF LAMPS working group in the context of X.509 certificate profiles for post-quantum signatures. While Kyber won the NIST KEM competition, NTRU remains attractive because of its smaller ciphertext size and simpler patent situation (NTRU's original patents expired in 2017).

Onyx by OnBoard Security is a commercial NTRU-based signature scheme used in automotive vehicle-to-everything (V2X) communication, where it provides long-term-quantum-safe authentication for safety-critical messages between cars and infrastructure. The IEEE 1609.2 standard for V2X security includes NTRU as an approved signature algorithm alongside ECDSA.

Google's CECPQ1 experiment in Chrome 2016 combined NTRU with X25519 in TLS to test the real-world performance of hybrid post-quantum key exchange. The experiment measured client-server handshake latency across millions of real users and informed subsequent design decisions for Kyber deployment in Chrome 2023.

The Open Quantum Safe (liboqs) library by the Open Quantum Safe project includes NTRU-HRSS as one of its supported KEM algorithms, used by researchers for benchmarking and by production systems experimenting with post-quantum readiness.

Conclusion

NTRU is the oldest practical lattice cryptosystem and remains competitive with the newer LWE and Module-LWE schemes. Our Java program demonstrated cyclic convolution, key generation, encryption with random blinding, and centered-lift decryption in roughly 100 lines. Next, study the Number Theoretic Transform for fast polynomial multiplication (essential at production parameter sizes), the NTRU-HRSS parameter derivation in the IETF draft, and the relationship between NTRU and the Ring-LWE and Module-LWE schemes (Kyber, NewHope) that build on the same polynomial-ring structure but with different noise distributions and security reductions.