Paper 2022/392

Poly Onions: Achieving Anonymity in the Presence of Churn

Megumi Ando, Miranda Christ, Anna Lysyanskaya, and Tal Malkin

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. In this paper, we initiate a formal treatment of onion routing in a setting with multiple runs over a dynamic network with churn. We provide the following contributions. -We define the cryptographic primitive of poly onion encryption, which is appropriate for a setting with churn. This primitive is inspired by duo onions, introduced by Iwanik, Klonowski, and Kutylowski (Communications and Multimedia Security, 2005) towards improving onion delivery rate. We generalize the idea, change it to add auxiliary helpers towards supporting better security, and propose formal definitions. -We construct an instantiation of poly onion encryption based on standard cryptographic primitives (CCA secure public key encryption with tags, PRP, MAC, and secret sharing). Our construction is secure against an active adversary, and is parameterized to allow flexible instantiations supporting a range of corruption thresholds and churn limits. -We formally model anonymous onion routing for multiple runs in the setting with churn, including a definition of strong anonymity, where the adversary has CCA-like access to oracles for generating and processing onions. -We prove that if an onion routing protocol satisfies a natural condition we define ("simulatability"), then strong single-run anonymity implies strong multiple-run anonymity. This condition is satisfied by existing onion routing schemes, such as the $\Pi_p$ protocol of Ando, Lysyanskaya, and Upfal (ICALP 2018). As a consequence, these schemes are anonymous also for multiple runs (although not when there is churn). -We provide an anonymous routing protocol, "Poly $\Pi_p$," and prove that it is anonymous in the setting with churn, against a passive adversary. We obtain this construction by using an instance of our poly onion encryption within the $\Pi_p$ protocol.