Optimizing ML-KEM with OpenMP: A Multilevel Parallelization Study

• Vinícius Lagrota CEPESC https://orcid.org/0000-0003-3272-8613
• Tertuliano Souza Neto CEPESC https://orcid.org/0000-0002-4076-4609
• Thiago do Rêgo Sousa CEPESC
• Fábio Maia CISSA https://orcid.org/0000-0002-6272-4675

DOI: https://doi.org/10.5753/sbseg.2026.27028

Resumo

In this work, we present libcesarpq, a cryptographic library that integrates an optimized implementation of the post-quantum Key Encapsulation Mechanism ML-KEM. We perform a detailed analysis of the algorithm’s source code to identify opportunities for parallelization using OpenMP directives. We show that, since most core ML-KEM functions have very short execution time, the overhead introduced can severely limit performance gain. Therefore, we evaluate different parallelization strategies at both the core-layer functions and the API-layer, as well as the batched API-layer. The results are compared with the widely used post-quantum library liboqs in both single-threaded and multithreaded environments, showing comparable performance on the x86-64 platform and a performance advantage for libcesarpq on the optimized aarch64 platform.

Referências

Abbasi, M., Cardoso, F., Váz, P., Silva, J., and Martins, P. (2025). A practical performance benchmark of post-quantum cryptography across heterogeneous computing environments. Cryptography, 9(2):32.

Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., Stehlé, D., et al. (2019). Crystals-kyber algorithm specifications and supporting documentation. NIST PQC Round, 2(4):1–43.

Azevedo, B. L., Lagrota, V., and Ribeiro, M. V. (2025). Multicore implementation of ml-kem on embedded devices. In Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais (SBSeg), pages 675–691. SBC.

Becker, H., Hwang, V., Kannwischer, M. J., Yang, B.-Y., and Yang, S.-Y. (2022). Neon ntt: Faster dilithium, kyber, and saber on cortex-a72 and apple m1. IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 221–244.

Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., and Stehlé, D. (2018). Crystals-kyber: a cca-secure module-lattice-based kem. In 2018 IEEE European symposium on security and privacy (EuroS&P), pages 353–367. IEEE.

Chen, L. et al. (2016). Report on post-quantum cryptography. Technical Report 8105, NIST, Gaithersburg, MD.

Fredrickson, N. R., Afsahi, A., and Qian, Y. (2003). Performance characteristics of openmp constructs, and application benchmarks on a large symmetric multiprocessor. In Proceedings of the 17th annual international conference on Supercomputing, pages 140–149.

Gewehr, C., Luza, L., and Moraes, F. G. (2024). Hardware acceleration of crystals-kyber in low-complexity embedded systems with risc-v instruction set extensions. IEEE Access, 12:94477–94495.

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proc. 28th annual ACM symposium on Theory of computing, pages 212–219.

Kim, Y. and Seo, S. C. (2025). An optimized instantiation of post-quantum mqtt protocol on 8-bit avr sensor nodes. In Proceedings of the 20th ACM Asia Conference on Computer and Communications Security, pages 248–266.

Lagrota, V., Camponogara, Â., López, J., and Ribeiro, M. V. (2022). The feasibility of the crystals-kyber scheme for smart metering systems. IEEE Access, 10:131303–131317.

Lagrota, V., Filomeno, M. d. L., de MBA Dib, L., López, J., and Ribeiro, M. V. (2025). A quantum-resistant advanced metering infrastructure. In Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais (SBSeg), pages 32–48. SBC.

Langlois, A. and Stehlé, D. (2015). Hardness of the learning with errors problem over rings and modules. In Advances in Cryptology – EUROCRYPT 2015, volume 9056 of Lecture Notes in Computer Science, pages 464–494. Springer.

Nguyen, T.-H., Dang, T.-K., Dam, D.-T., Nguyen, K.-D., Duong, P.-P., Pham, C.-K., and Hoang, T.-T. (2025). An area-time efficient hardware architecture for ml-kem post-quantum cryptography standard. IEEE Access.

Ni, Z., Khalid, A., Liu, W., and O’neill, M. (2025). A highly hardware efficient ml-kem accelerator with optimised architectural layers. ACM Transactions on Embedded Computing Systems, 24(2):1–24.

NIST (2024). Module-lattice-based key-encapsulation mechanism standard (fips 203). Federal Information Processing Standards Publication FIPS 203, National Institute of Standards and Technology (NIST), Gaithersburg, MD, USA. Published August 13, 2024.

Pacheco, P. and Malensek, M. (2021). An introduction to parallel programming. Morgan Kaufmann.

Paiva, T. B., Simplicio Jr, M. A., Hafiz, S. M., Yildiz, B., Cominetti, E. L., and Ogawa, H. S. (2025). Tailorable codes for lattice-based kems with applications to compact ml-kem instantiations. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025(3):139–163.

Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 84–93. ACM.

Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In Proc. 35th Annu. Symp. Foundations of Computer Science, pages 124–134.

Wei, H., Li, W., Shen, S., Yang, H., and Zhao, Y. (2026). Optimized implementation of ml-kem on armv9-a with sve2 and sme. Cryptology ePrint Archive.