[FEATURE REQUEST] Add Learning With Errors (LWE) encryption (Regev) #7630

What would you like to Propose?

I would like to add an educational implementation of Learning With Errors (LWE) public-key encryption (Regev, 2005) to the ciphers package.

LWE is the foundation of lattice-based cryptography and the mathematical basis of ML-KEM (Kyber), standardized by NIST as FIPS 203. The repository currently has no lattice-based algorithms, so this would be the first one and a natural complement to the existing hash-based signatures (Lamport, Winternitz).

Issue details

Algorithm: LWE encryption (Regev, 2005)

Problem statement: Given many noisy linear equations b = A·s + e (mod q) with a small random error e, recovering the secret s is believed to be hard, even for quantum computers. Regev's scheme uses this hardness to encrypt single bits.

How it works:

• Key generation: sample a secret s ∈ Z_q^n, a random matrix A ∈ Z_q^{m×n} and a small error vector e. The public key is (A, b = A·s + e), and the private key is s.
• Encryption of a bit: pick a random binary vector r ∈ {0,1}^m, then compute u = rᵀ·A and v = r·b + bit·⌊q/2⌋ (mod q). The ciphertext is (u, v).
• Decryption: compute d = v − u·s (mod q). If d is closer to q/2 than to 0, the bit is 1; otherwise it is 0.
• Messages: a byte[] is encrypted bit by bit (MSB first).

Parameters (toy): n = 32, q = 3329 (the ML-KEM modulus), m = 128, errors uniform in [-3, 3]. The accumulated noise is at most m·3 = 384 < q/4, so decryption is always correct.

Proposed API (com.thealgorithms.ciphers.LWEEncryption):

• LWEEncryption(), which performs key generation
• Ciphertext encryptBit(int bit) / int decryptBit(Ciphertext ciphertext)
• Ciphertext[] encrypt(byte[] message) / byte[] decrypt(Ciphertext[] ciphertexts)

Scope:

• No external dependencies; only java.security.SecureRandom
• JUnit 5 tests: bit and byte roundtrips, randomized encryption, wrong-key decryption, bit ordering, input validation and immutability
• Only two new files (implementation + test)

Additional Information

This is intended for educational purposes only. The parameters are far too small to be secure, and real schemes use discrete Gaussian noise and much larger dimensions. This will be clearly stated in the Javadoc.

A possible follow-up would be a simplified Ring-LWE implementation over Z_q[x]/(x^n + 1), which is closer to the actual structure of ML-KEM.

References:

• https://en.wikipedia.org/wiki/Learning_with_errors
• O. Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography", STOC 2005
• FIPS 203 (ML-KEM): https://csrc.nist.gov/pubs/fips/203/final