A Comparative Study of LWE-Based Post-Quantum Key Encapsulation and Traditional RSA

Abstract: Public-key key establishment protects almost all secure communication on the internet, and RSA remains one of its most widely deployed mechanisms. RSA’s security rests on the difficulty of integer factorisation, a problem that Shor’s quantum algorithm solves in polynomial time on a sufficiently large quantum computer. In response, NIST standardised the lattice-based ML-KEM (FIPS 203), whose security is derived from the Learning With Errors (LWE) problem. This paper presents a comparative study of LWE-based post-quantum key encapsulation and traditional RSA. The study compares the two families on security foundation, quantum resistance, key and ciphertext sizes, and computational cost. To support the comparison with measured data, a Module-LWE key encapsulation mechanism following the ML-KEM-512, ML-KEM-768 and ML-KEM-1024 parameter sets was implemented and benchmarked against RSA-2048, RSA-3072 and RSA-4096 with OAEP padding on the same machine; the study also measures decryption noise margins and end-to-end hybrid encryption. In the experiments, all 900 LWE round trips decapsulated correctly and tampered ciphertexts were rejected. RSA-2048 public keys and ciphertexts were about 2.7 and 3.0 times smaller than those of ML-KEM-512, and RSA encapsulation was far faster; however, RSA key generation was roughly 40 to 300 times slower than LWE key generation, even though the LWE code was an unoptimised Python prototype. The results indicate that LWE-based schemes trade larger messages for quantum resistance and fast key generation, and support a gradual, hybrid migration from RSA.

Keywords: Learning With Errors (LWE), post-quantum cryptography, ML-KEM, RSA, Module-LWE, key encapsulation, quantum resistance