Paper 2024/020

EROR: Efficient Repliable Onion Routing with Strong Provable Privacy

Michael Klooß, Aalto University
Andy Rupp, University of Luxembourg, KASTEL SRL
Daniel Schadt, Karlsruhe Institute of Technology
Thorsten Strufe, Karlsruhe Institute of Technology
Christiane Weis, NEC Laboratories Europe

To provide users with anonymous access to the Internet, onion routing and mix networks were developed. Assuming a stronger adversary than Tor, Sphinx is a popular packet format choice for such networks due to its efficiency and strong protection. However, it was recently shown that Sphinx is susceptible to a tagging attack on the payload in some settings. The only known packet formats which prevent this attack rely on advanced cryptographic primitives and are highly inefficient, both in terms of packet sizes and computation overhead. In this paper, we provide the first packet format that protects against the tagging attack with an acceptable overhead. At the cost of doubling the payload size, we are able to build a provably private solution from basic cryptographic primitives. Our implementation demonstrates that our solution is as computationally efficient as Sphinx, beating previous schemes by a large margin. For our security proof, we first strengthen the state-of-the-art proof strategy, before applying it to our solution to demonstrate that not only the tagging attack is prevented, but our scheme is provably private.

Available format(s)
Cryptographic protocols
Publication info
Anonymous CommunicationOnion RoutingMix NetsTagging AttackPacket Format
Contact author(s)
michael klooss @ aalto fi
andy rupp @ rub de
daniel schadt @ kit edu
thorsten strufe @ kit edu
christiane weis @ neclab eu
2024-01-08: approved
2024-01-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michael Klooß and Andy Rupp and Daniel Schadt and Thorsten Strufe and Christiane Weis},
      title = {{EROR}: Efficient Repliable Onion Routing with Strong Provable Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2024/020},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.