Paper 2023/1311

Are continuous stop-and-go mixnets provably secure?

Debajyoti Das, KU Leuven
Claudia Diaz, KU Leuven and Nym
Aggelos Kiayias, University of Edinburgh and IOG
Thomas Zacharias, University of Glasgow

This work formally analyzes the anonymity guarantees of continuous stop-and-go mixnets and attempts to answer the above question. Existing mixnet based anonymous communication protocols that aim to provide provable anonymity guarantees rely on round-based communication models --- which requires synchronization among all the nodes and clients, and difficult to achieve in practice. Continuous stop-and-go mixnets (e.g., Loopix and Nym) provide a nice alternative by adding a random delay for each message on every hop independent of all other hops and all other messages. The core anonymization technique of continuous mixnets combined with the fact that the messages are sent by the clients to the mixnet at different times makes it a difficult problem to formally prove security for such mixnet protocols; all existing analyses for such designs provide only experimental evaluations for anonymity. We are the first to close that gap and provide a formal analysis. We provide two indistinguishability based definitions (of sender anonymity), namely pairwise unlinkability and user unlinkability, tuned specifically for continuous stop-and-go mixnets. We derive the adversarial advantage as a function of the protocol parameters for the two definitions. We show that there is a fundamental lower bound on the adversarial advantage $\delta$ for pairwise unlinkability; however, strong user unlinkability (negligible adversarial advantage) can be achieved if the users message rate ($\lambda_u$) is proportional to message processing rate ($\lambda$) on the nodes.

Available format(s)
Publication info
privacyanonymityanonymous communicationmixnetspoisson mixingproof
Contact author(s)
ddas @ esat kuleuven be
cdiaz @ esat kuleuven be
aggelos kiayias @ ed ac uk
thomas zacharias @ glasgow ac uk
2023-09-04: approved
2023-09-03: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Debajyoti Das and Claudia Diaz and Aggelos Kiayias and Thomas Zacharias},
      title = {Are continuous stop-and-go mixnets provably secure?},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1311},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.