Evaluating the Proof of Possession of KEM Keys Based on Verifiable Generation

• Gabriela Strieder Ramos UTFPR
• Andrei Filipim Esteves UTFPR
• Alexandre Augusto Giron UTFPR

DOI: https://doi.org/10.5753/sbseg_estendido.2025.14944

Abstract

In response to the threat that quantum computers pose to security, the migration to quantum-resistant cryptography using Key Encapsulation Mechanisms (KEMs) for Internet authentication is proposed, aiming for better performance. Thus, this work aimed to analyze the feasibility of PoPs for KEMs and compare their performance, focusing on the FrodoKEM algorithm. The comparative analysis between implementations in C and Go showed that, although C is faster, the main problem is the computational cost of the "Proof of Possession", which is orders of magnitude higher than the base mechanism. This problem could affect scalability and prevents its use in high-security scenarios demanding agility.

References

Agence Nationale de la Sécurité des Systèmes d’Information (2023). Anssi views on the post-quantum cryptography transition (2023 follow up). [link]. Acesso em: 20 mar. 2025.

Barnes, R., Hoffman-Andrews, J., McCarney, D., and Kasten, J. (2019). Automatic Certificate Management Environment (ACME). RFC 8555, RFC Editor.

Chair for Security Engineering (2025). Kem-nizkpop repository. [link].

Federal Office for Information Security (2023). Cryptographic mechanisms: recommendations and key lengths. [link]. Acesso em: 12 mar. 2025.

FrodoKEM (2025). Frodokem: Post-quantum cryptography based on lattices. [link].

Güneysu, T., Hodges, P., Land, G., Ounsworth, M., Stebila, D., and Zaverucha, G. (2022). Proof-of-Possession for KEM Certificates Using Verifiable Generation. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS ’22, page 1337–1351, New York, NY, USA. Association for Computing Machinery.

Microsoft Corporation (2025). Pqcrypto-lweke repository. [link]. Código-fonte oficial do FrodoKEM.

NIST (2022). PQC Standardization Process: Announcing four candidates to be standardized, plus fourth round candidates. [link]. Acessed: 2022-11-02.

Ramos, G. S., Esteves, A. F., and Giron, A. A. (2025). Repositório zkpop-go. [link]. Acesso em: 26 maio 2025.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134, Santa Fe, NM, USA. IEEE, IEEE.