A Hybrid Post-Quantum Extension for the Matrix Protocol: Experimental Evaluation and Systemic Impact

• Marcos Ortiz UFC
• Vinícius Lagrota CEPESC
• Gilvan Maia UFC
• Rodrigo Pacheco UFC
• Paulo Rego UFC

DOI: https://doi.org/10.5753/sbrc.2026.19881

Abstract

Quantum computing threatens E2EE messenger encryption, driving the adoption of post-quantum cryptography (PQC). This study evaluates the hybrid integration of CRYSTALS-Kyber into the Matrix protocol, extending the key agreement and the Double Ratchet. Experimental tests demonstrate that the primary bottleneck is bandwidth, with a +548% overhead in setup and +252% in key rotations, while the impact on CPU and user experience is negligible (≈16 ms to 100 ms). The cost of rotations scales quadratically, indicating that rigid security policies are inefficient and demand adaptive strategies to balance security and network consumption.

References

Auerbach, B., Dodis, Y., Jost, D., Katsumata, S., and Schmidt, R. (2025). How to compare bandwidth constrained two-party secure messaging protocols: a quest for a more efficient and secure post-quantum protocol. In Proceedings of the 34th USENIX Conference on Security Symposium, pages 6717–6736.

Aydeger, A., Zeydan, E., Yadav, A. K., Hemachandra, K. T., and Liyanage, M. (2024). Towards a quantum-resilient future: Strategies for transitioning to post-quantum cryptography. In 2024 15th International Conference on Network of the Future (NoF), pages 195–203. IEEE.

Barker, E. (2020). Recommendation for key management: Part 1 – general (sp 800-57 part 1, rev 5). Technical report, National Institute of Standards and Technology (NIST).

Cohn-Gordon, K., Cremers, C., Dowling, B., Garratt, L., and Stebila, D. (2016). A formal security analysis of the signal messaging protocol. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 1339–1353.

Dodis, Y., Jost, D., Katsumata, S., Prest, T., and Schmidt, R. (2025). Triple ratchet: A bandwidth efficient hybrid-secure signal protocol. In Annual Int. Conference on the Theory and Applications of Cryptographic Techniques, pages 302–331. Springer.

Duits, I. (2019). The post-quantum signal protocol: Secure chat in a quantum world. Master’s thesis, University of Twente.

Kret, E. and Schmidt, R. (2023). The pqxdh key agreement protocol. [link].

Martins, J. A., Rego, P. A., de Macêdo, J. A., Silva, F. A., and Lagrota, V. (2026). Matrix protocol: a comprehensive systematic mapping study. Journal of Cloud Computing, 15(1):20.

Martins, J. A. P., Rego, P. A. L., Macêdo, J. A. F. d., Andrade, R. M. C., Bonfim, M. S., Ivo, R. F., Costa, V. L. R. d., Pacheco, R. P., and Silva, F. A. P. d. (2025). Protocolo matrix: Conceitos, arquitetura, aplicações e desafios. In Jornada de Atualização em Informática 2025, pages 1–46. Sociedade Brasileira de Computação (SBC).

Matrix.org (2019). Olm: A cryptographic ratchet. [link]. libolm repository.

Matrix.org (2022). Megolm group ratchet. [link]. libolm repository.

Matrix.org (2024). Matrix specification. [link].

NIST (2022). Post-quantum cryptography standardization. Technical report, National Institute of Standards and Technology. Acesso em: [link].

Schmidt, R. and Connell, G. (2025). The ml-kem braid protocol. Signal Messenger Specification. Available at: [link].

Seufert, M., Wassermann, S., and Casas, P. (2023). Share and multiply: Modeling communication and generated traffic in private whatsapp groups. In Proceedings of the 23rd ACM Internet Measurement Conference, pages 642–657.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. 35th Annual Symposium on Foundations of Computer Science, pages 124–134.

Stebila, D. (2024). Security analysis of the imessage pq3 protocol. Cryptology ePrint Archive.