QuMixnet: A Quantum-Safe Mixnet Protocol

Dibaj, Seyed Mohammad; Eghlidos, Taraneh; Pilaram, Hosein

doi:10.22042/isecure.2025.237326

QuMixnet: A Quantum-Safe Mixnet Protocol

Articles in Press

Document Type : Research Article

Authors

Seyed Mohammad Dibaj ¹

Taraneh Eghlidos ²

Hosein Pilaram ²

¹ Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

² Electronics Research Institute, Sharif University of Technology, Tehran, Iran

10.22042/isecure.2025.237326

Abstract

The emergence of quantum computing threatens the security of traditional
cryptographic primitives underpinning anonymous communication protocols
like mix networks (mixnets), necessitating quantum-resistant alternatives. This
paper introduces QuMixnet, a mixnet protocol designed to withstand quantum
attacks while ensuring robust anonymity and privacy. QuMixnet employs
post-quantum cryptographic primitives, utilizing CRYSTALS-Dilithium for
digital signatures to guarantee authenticity and CRYSTALS-Kyber for key
encapsulation to secure message encryption with symmetric ciphers (e.g.,
AES-GCM). Operating on a peer-to-peer (P2P) architecture, every node can
serve as a sender, receiver, or mix node, enhancing anonymity by obscuring
participant roles. Sender-determined routing ensures that only the sender knows
the full message path, with onion routing layered encryption across nodes. To
counter traffic analysis, QuMixnet implements message padding to a fixed size,
dummy messages for traffic covering, and batch processing with shuffling. A
security model, evaluated through formal security games, confirms resilience
of QuMixnet against adversaries with quantum capabilities, achieving strong
sender and receiver anonymity, communication anonymity, confidentiality, and
integrity. QuMixnet advances anonymous communication by offering a scalable,
quantum-safe solution that fortifies privacy against evolving threats.

Keywords

Mix networks

Post-quantumcryptography

Anonymous communication

Peer-to-peer networks

[1] David L Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84–90, 1981.

[2] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. IEEE, 1994.

[3] Lance Cottrell, Peter Palfrader, and Len Sassaman. Mixmaster protocol-version 2. Online specification, 2003.

[4] George Danezis, Roger Dingledine, and Nick Mathewson. Mixminion: Design of a type iii anonymous remailer protocol. In 2003 Symposium on Security and Privacy, 2003., pages 2–15. IEEE, 2003.

[5] Bassam Zantout, Ramzi Haraty, et al. I2p data communication system. In Proceedings of ICN, pages 401–409. Citeseer, 2011.

[6] Ania M Piotrowska, Jamie Hayes, Tariq Elahi, Sebastian Meiser, and George Danezis. The loopix anonymity system. In 26th usenix security symposium (usenix security 17), pages 1199– 1216, 2017.

[7] Claudia Diaz, Harry Halpin, and Aggelos Kiayias. The nym network. 2021.

[8] Claudia Diaz, Harry Halpin, and Aggelos Kiayias. Reward sharing for mixnets. 2022.

[9] HOPR Association. Hopr protocol overview. 2021. Accessed: 2025-07-07.

[10] 0 Knowledge Network. 0kn overview. 2024. Accessed: 2025-07-07.

[11] Simon Langowski, Sacha Servan-Schreiber, and Srinivas Devadas. Trellis: Robust and scalable metadata-private anonymous broadcast. Cryptology ePrint Archive, 2022.

[12] Ewa J Infeld, David Stainton, Leif Ryge, and Threebit Hacker. Echomix: a strong anonymity system with messaging. arXiv preprint arXiv:2501.02933, 2025.

[13] David Chaum, Debajyoti Das, Farid Javani, Aniket Kate, Anna Krasnova, Joeri De Ruiter, and Alan T Sherman. cmix: Mixing with minimal real-time asymmetric cryptographic operations. In Applied Cryptography and Network Security: 15th International Conference, ACNS 2017, Kanazawa, Japan, July 10-12, 2017, Proceedings 15, pages 557–578. Springer, 2017.

[14] Alfredo Rial and Ania M Piotrowska. Outfox: a packet format for a layered mixnet. arXiv preprint arXiv:2412.19937, 2024.

[15] L´eo Ducas, Eike Kiltz, Tancrede Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehl´e. Crystals-dilithium: A latticebased digital signature scheme. IACR TCHES, 2018(1):238–268, 2018.

[16] Joppe Bos, L´eo Ducas, Eike Kiltz, Tancr`ede Lepoint, Vadim Lyubashevsky, John M Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehl´e. Crystals-kyber: a cca-secure modulelattice-based kem. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pages 353–367. IEEE, 2018.

[17] National Institute of Standards and Technology. Post-quantum cryptography standardization. 2024. Accessed: 2025-07-07.

[18] George Danezis and Ian Goldberg. Sphinx: A compact and provably secure mix format. In 2009 30th IEEE Symposium on Security and Privacy, pages 269–282. IEEE, 2009.

[19] Diego F Aranha, Carsten Baum, Kristian Gjøsteen, and Tjerand Silde. Verifiable mixnets and distributed decryption for voting from lattice-based assumptions. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 1467–1481, 2023.

[20] Xavier Boyen, Thomas Haines, and Johannes Müller. A verifiable and practical lattice-based decryption mix net with external auditing. In European Symposium on Research in Computer Security, pages 336–356. Springer, 2020.

[21] Valeh Farzaliyev, Jan Willemson, and Jaan Kristjan Kaasik. Improved lattice-based mix-nets for electronic voting. IET Information Security, 17(1):18–34, 2023.

[22] Michael G Reed, Paul F Syverson, and David M Goldschlag. Anonymous connections and onion routing. IEEE Journal on Selected areas in Communications, 16(4):482–494, 2002.

[23] Morris Dworkin. Recommendation for block cipher modes of operation: Galois/counter mode (gcm) and gmac, 2007. NIST Special Publication (SP).

[24] Hao Zhang, Yonggang Wen, Haiyong Xie, Nenghai Yu, et al. Distributed hash table: Theory, platforms and applications. Springer, 2013.

[25] Alberto Montresor et al. Gossip and epidemic protocols. Wiley encyclopedia of electrical and electronics engineering, 1, 2017.