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.

Intro
Encryption hides message content ...
A practical approach: onion routing [Cha81]
The idea: onions "mix" at honest nodes
Definition of security for an anonymous channel
Related work
A solution in the passive adversary setting [ALU18]
but II, isn't anonymous in the active adversary setting
Attacks highlight necessary (and sufficient) properties for anonymity
Tool for mixing: checkpoint onions [ALU18]
Tool for equalizing: merging onions
A stepping stone construction: II (Pi-tree)
II, plus a butterfly network
IIA, plus a stretched butterfly network
Our final construction: II (Pi-butterfly)
Conclusion