Verifying and optimizing post-quantum cryptography at Amazon

Amazon has open-sourced mlkem-native, a production-ready C implementation of the NIST-standardized ML-KEM (formerly Kyber) post-quantum cryptography algorithm. Developed by the company's Automated Reasoning Group and AWS Cryptography teams, the project directly addresses the threat of 'store now, decrypt later' attacks by providing a cryptographically secure foundation for the quantum computing era. The implementation uniquely bridges the gap between the simplicity and auditability of the reference code and the performance potential outlined in academic research.

To achieve this, engineers employed automated reasoning tools like CBMC (for C code verification) and SLOTHY (for superoptimization of assembly). These tools provided mathematical proof of memory safety, type safety, and functional correctness, even as the team applied aggressive, platform-specific assembly optimizations. This formal verification process resolves the classic tension in cryptographic engineering between security, performance, and maintainability, ensuring the optimized code is as trustworthy as the simpler reference.

The performance results are significant: mlkem-native executes key operations 2.0 to 2.4 times faster than the standard ML-KEM reference implementation across different Amazon EC2 instance types. This translates to a lower computational 'tax' for customers adopting quantum-resistant cryptography. The project was developed in collaboration with the Linux Foundation's Post-Quantum Cryptography Alliance (PQCA), underscoring its role as a foundational, high-assurance component for the broader open-source ecosystem preparing for the post-quantum transition.