FrodoKEM

FrodoKEM is a post-quantum key encapsulation mechanism based on the Frodo family of lattice-based public-key encryption schemes. It relies on the hardness of standard Learning with Errors (LWE) problems and was developed to provide a conservative, quantum-resistant foundation for key exchange without relying on more specialized or potentially vulnerable lattice structures.

In operation, FrodoKEM follows a public-key cryptosystem workflow adapted for encapsulation. Key generation produces a public key consisting of a large random matrix A and an accompanying short error term, while the private key contains the corresponding secret used for decryption. To establish a shared secret, the encapsulation algorithm uses the recipient’s public key to generate a noisy common value and a ciphertext; a reconciliation step then converts the noisy value into a uniformly random key. The decapsulation algorithm uses the private key to recover the same shared secret from the ciphertext.

The scheme provides several parameter sets, notably FrodoKEM-640, FrodoKEM-976, and FrodoKEM-1344, which vary in dimension and noise parameters to balance security level and performance. As a result, public-key and ciphertext sizes grow with the parameter set, making FrodoKEM relatively heavier than some other post-quantum KEMs, although this reflects its conservative design choices.

FrodoKEM is designed to be resistant to quantum attacks through assumptions anchored in standard LWE, avoiding reliance on structured lattice problems. It has been studied and implemented in research contexts and was part of the broader NIST post-quantum cryptography evaluation process, alongside other lattice-based KEMs.

See also: post-quantum cryptography, lattice-based cryptography, Learning with Errors, NIST PQC.