International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Poly Onions: Achieving Anonymity in the Presence of Churn

Megumi Ando , MITRE
Miranda Christ , Columbia University
Anna Lysyanskaya , Brown University
Tal Malkin , Columbia University
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
Abstract: Onion routing is a popular approach towards anonymous communication. Practical implementations are widely used (for example, Tor has millions of users daily), but are vulnerable to various traffic correlation attacks, and the theoretical foundations, despite recent progress, still lag behind. In particular, all works that model onion routing protocols and prove their security only address a single run, where each party sends and receives a single message of fixed length, once. Moreover, they all assume a static network setting, where the parties are stable throughout the lifetime of the protocol. In contrast, real networks have a high rate of churn (nodes joining and exiting the network), real users want to send multiple messages, and realistic adversaries may observe multiple runs of the protocol. We initiate a formal treatment of onion routing in a setting with multiple runs over a dynamic network with churn. We provide definitions of both security and anonymity in this setting, and constructions that satisfy them. In particular, we define a new cryptographic primitive called \emph{Poly Onions} and show that it can be used to realize our definitions.
  title={Poly Onions: Achieving Anonymity in the Presence of Churn},
  author={Megumi Ando and Miranda Christ and Anna Lysyanskaya and Tal Malkin},