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 Poly Onions and show that it can be used to realize our definitions.