On the Complexity of Anonymous Communication Through Public Networks

Explore the complexities of anonymous communication through public networks in this 22-minute conference talk from the 2021 ITC Conference. Delve into the concept of onion routing, its widespread use in online anonymity, and the challenges it faces. Discover the first onion routing protocol that simultaneously achieves fault-tolerance, reasonable complexity, and anonymity in the presence of an active adversary. Learn about the protocol's ability to tolerate dropped onions, its polylogarithmic rounds and onion requirements, and its achievement of anonymity. Examine the introduction of two new security properties - mixing and equalizing - and their implications for anonymity. Follow the presentation's structure, covering encryption basics, practical approaches, security definitions, related work, and various constructions leading to the final II (Pi-butterfly) protocol.