International Association
for Cryptologic Research

Onion routing is a popular practical approach to anonymous communication, and the subject of a growing body of foundational theoretical work aiming to design efficient schemes with provable anonymity, the strongest notion of which is full anonymity.

Unfortunately, all previous schemes that achieve full anonymity assume the synchronous communication setting, which is unrealistic as real networks may experience message loss and timing attacks that render such schemes insecure. Recently, Ando, Lysyanskaya, and Upfal (TCC '24) took a first step towards addressing the asynchronous setting by constructing an efficient onion routing protocol with the strictly weaker guarantee of differential privacy. Their scheme relies on a new primitive called bruisable onion encryption.

In this paper, we construct the first efficient fully anonymous onion routing protocol in the asynchronous setting. To do so, we overcome two main technical challenges: First, we develop the first bruisable onion construction that does not leak information about the onion's position on the routing path. Second, we design an onion routing protocol that uses such bruisable onion encryption to achieve full anonymity (rather than just differential privacy). Along the way, we develop a new fully anonymous onion routing protocol in the synchronous setting, which improves on the state of the art in terms of communication complexity and round complexity.

Both our protocols are secure against an active adversary corrupting a constant fraction of the nodes (up to <1 for the synchronous protocol, and <1/2 for the asynchronous protocol) and rely on standard cryptographic assumptions (CCA-secure public key encryption and collision-resistant hash functions).