msgX: Towards Sovereign Post-Quantum Messaging for Government Deployments of the Matrix Protocol
Abstract
This paper presents msgX, a secure messaging protocol for replacing Olm-based session distribution in governmental Matrix rooms, combining standardized and government-developed cryptography to support interoperability and digital sovereignty. To mitigate quantum threats, msgX integrates Post-Quantum Extended Diffie–Hellman (PQXDH), a modified Double Ratchet, and msgGX, a Megolm adaptation for scalable group encryption. In 14,040 Android runs across two devices, 30 each, and 234 parametrized configurations, a branch-level cost decomposition against Olm was performed, isolating the msgX-Γ and msgX-Σ profiles. The results show that each profile keeps new-member key agreement at O(1), preserves stable per-message latency, and incurs a one-time session-establishment overhead of approximately +38% (msgX-Γ) and +53% (msgX-Σ) relative to Olm. The protocol enables gradual migration from Olm without breaking Matrix federation.
References
Albrecht, M. R., Dowling, B., and Jones, D. (2024). Device-oriented group messaging: a formal cryptographic analysis of matrix’core. In 2024 IEEE Symposium on Security and Privacy (SP). IEEE.
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.
Barnes, R., Beurdouche, B., Robert, R., Millican, J., Omara, E., and Cohn-Gordon, K. (2023). The messaging layer security (mls) protocol. RFC 9420, Internet Engineering Task Force.
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.
Française, R. (2019). Tchap. [link].
Hodgson, M. and Chathi, H. (2023). A giant leap forwards for encryption with MLS. [link]. Published July 18, 2023. Accessed July 29, 2026.
Kret, E. and Schmidt, R. (2023). The pqxdh key agreement protocol. [link].
Li, H., Wu, Y., Huang, R., Mi, X., Hu, C., and Guo, S. (2023). Demystifying decentralized matrix communication network: Ecosystem and security. In 2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS), pages 260–267. IEEE.
Mahy, R. and Barnes, R. L. (2026). Ml-kem and hybrid cipher suites for messaging layer security. Internet-Draft draft-ietf-mls-pq-ciphersuites-04, Internet Engineering Task Force. Work in Progress.
Marlinspike, M. and Perrin, T. (2016). The x3dh key agreement protocol. Open Whisper Systems, 283(10):10.
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].
Matrix.org Foundation. Vodozemac: An implementation of Olm and Megolm in pure Rust. [link]. Accessed July 29, 2026.
Nist, G. M. D. (2024). Module-lattice-based key-encapsulation mechanism standard. Technical report, National Institute of Standards and Technology, Gaithersburg, MD.
Pacheco, R., Braga, D., Passos, I., Araújo, T., Lagrota, V., and Coutinho, M. (2022). libharpia: a new cryptographic library for brazilian elections. In Anais do XXII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 250–263. SBC.
Perrin, T. and Marlinspike, M. (2016). The double ratchet algorithm. GitHub wiki, 112(4).
Schmidt, R. and Connell, G. (2025). The ml-kem braid protocol. Signal Messenger Specification. Available at: [link].
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. Ieee.
