Optimizing ML-KEM-768: Compressing Public Keys to Conquer Network Constraints

In the realm of post-quantum cryptography, the ML-KEM-768 algorithm stands as a robust contender, yet its implementation presents a subtle but significant challenge: the size of its public keys. When operating within the constraints of IPv6 networks, where the minimum MTU is 1280 octets, the 1184-octet public keys of ML-KEM-768 leave precious little room for other protocol necessities. This article explores an elegant compression technique that reduces these keys by 24 octets, potentially unlocking more efficient cryptographic exchanges in resource-constrained environments.

The fundamental issue lies in the traditional encoding of ML-KEM-768 public keys. As the author explains, these keys consist of three polynomials, each containing 256 coefficients, with each coefficient stored in 12 bits. The modulus q equals 3329, which translates to approximately 11.70087316 bits. This discrepancy between the theoretical minimum storage requirement and the actual implementation creates an inefficiency—each coefficient consumes 12 bits, wasting about 0.3 bits per coefficient. While this may seem negligible individually, the cumulative effect across all coefficients presents an opportunity for optimization.

The compression technique draws from established cryptographic research, specifically referencing eprint 2016/461, "NTRU Prime: reducing attack surface at low cost" by Bernstein, Chuengsatiansup, Lange, and Vredendaal. Although NTRU Prime and ML-KEM are distinct cryptographic schemes, the underlying compression principle applies universally. The core insight lies in merging adjacent elements of Z/q rather than encoding each element separately using ⌈log₂(q)⌉ bits.

The implementation groups coefficients into sets of four, encoding each group as a single integer using Horner's method: c₃·q³ + c₂·q² + c₁·q + c₀, which resides in the range [0, q⁴). This approach requires ⌈4·log₂(q)⌉ = 47 bits per group, representing a more efficient packing than the traditional 48 bits (4 coefficients × 12 bits) required by the standard encoding.

The provided code implementation in Hare demonstrates both the packing and unpacking functions. The ek768_pack function transforms a standard 1184-octet key into a compressed 1160-octet representation, while ek768_unpack reverses this process. The implementation carefully handles the conversion between the two representations, including error checking for invalid coefficients. Notably, the seed ρ, which occupies the final 32 octets of the key and is considered indistinguishable from random, remains unchanged during the compression process.

This compression technique offers several practical implications. For IoT devices, embedded systems, and other resource-constrained environments, the 24-octet reduction could enable more efficient key exchange protocols, potentially reducing latency or increasing the amount of additional protocol material that can be transmitted within a single packet. The approach maintains the security properties of the original keys while optimizing their representation for network transmission.

However, the author appropriately includes a crucial disclaimer: "I am not a cryptographer. There may be serious bugs or side channels!" This caution highlights the importance of thorough cryptographic review before adopting such techniques in production systems. The compression algorithm, while mathematically sound, introduces additional implementation complexity that could potentially introduce vulnerabilities if not carefully implemented.

The hare-xcrypto implementation serves as a valuable reference for developers interested in exploring this approach, though it comes with the explicit warning of "no security guarantees." For organizations considering this compression technique, a comprehensive security assessment would be essential, including careful side-channel analysis and validation against established cryptographic standards.

As post-quantum cryptography continues its transition from theoretical research to practical deployment, such optimization techniques will play an increasingly important role. The ability to reduce key sizes without compromising security represents a significant step toward making these advanced cryptographic schemes viable across a broader range of applications and network environments.

For those interested in exploring further, the NTRU Prime paper provides the theoretical foundation for this approach, while the hare-xcrypto implementation offers a concrete example of the compression technique in action.