Paper 2025/1067

Full Anonymity in the Asynchronous Setting from Peony Onion Encryption

Abstract

Onion routing is a popular and practical approach to anonymous communication, and the subject of a growing body of work on designing efficient schemes with provable anonymity, the strongest notion being full anonymity. However, all prior schemes achieving full anonymity assume a synchronous communication setting, which is unrealistic since real networks suffer from message loss and timing attacks. Recently, Ando, Lysyanskaya, and Upfal (TCC’24) made progress toward the asynchronous setting by introducing bruisable onion encryption and constructing an efficient protocol with the weaker guarantee of differential privacy. In this paper, we construct the first efficient fully anonymous onion routing protocol in the asynchronous setting. To do so, we address two main challenges: (1) we develop the first bruisable onion encryption scheme that does not leak information about the onion’s position on the routing path, and (2) we design an onion routing protocol using this primitive to achieve full anonymity, rather than only differential privacy. Along the way, we also give a new fully anonymous protocol in the synchronous setting, improving the state-of-the-art in both communication and round complexity. Both protocols are secure against an active adversary that corrupts a constant fraction of nodes (up to < 1 in the synchronous case, and < 1/2 in the asynchronous case), and rely on standard cryptographic assumptions (CCA-secure public-key encryption and collision-resistant hash functions).