License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.9
URN: urn:nbn:de:0030-drops-143282
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14328/
Ando, Megumi ;
Lysyanskaya, Anna ;
Upfal, Eli
On the Complexity of Anonymous Communication Through Public Networks
Abstract
Onion routing is the most widely used approach to anonymous communication online. The idea is that Alice wraps her message to Bob in layers of encryption to form an "onion" and routes it through a series of intermediaries. Each intermediary’s job is to decrypt ("peel") the onion it receives to obtain instructions for where to send it next. The intuition is that, by the time it gets to Bob, the onion will have mixed with so many other onions that its origin will be hard to trace even for an adversary that observes the entire network and controls a fraction of the participants, possibly including Bob. Despite its widespread use in practice, until now no onion routing protocol was known that simultaneously achieved, in the presence of an active adversary that observes all network traffic and controls a constant fraction of the participants, (a) anonymity; (b) fault-tolerance, where even if a few of the onions are dropped, the protocol still delivers the rest; and (c) reasonable communication and computational complexity as a function of the security parameter and the number of participants.
In this paper, we give the first onion routing protocol that meets these goals: our protocol (a) achieves anonymity; (b) tolerates a polylogarithmic (in the security parameter) number of dropped onions and still delivers the rest; and (c) requires a polylogarithmic number of rounds and a polylogarithmic number of onions sent per participant per round. We also show that to achieve anonymity in a fault-tolerant fashion via onion routing, this number of onions and rounds is necessary. Of independent interest, our analysis introduces two new security properties of onion routing - mixing and equalizing - and we show that together they imply anonymity.
BibTeX - Entry
@InProceedings{ando_et_al:LIPIcs.ITC.2021.9,
author = {Ando, Megumi and Lysyanskaya, Anna and Upfal, Eli},
title = {{On the Complexity of Anonymous Communication Through Public Networks}},
booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
pages = {9:1--9:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-197-9},
ISSN = {1868-8969},
year = {2021},
volume = {199},
editor = {Tessaro, Stefano},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14328},
URN = {urn:nbn:de:0030-drops-143282},
doi = {10.4230/LIPIcs.ITC.2021.9},
annote = {Keywords: Anonymity, privacy, onion routing}
}
|
Keywords: |
|
Anonymity, privacy, onion routing |
|
Collection: |
|
2nd Conference on Information-Theoretic Cryptography (ITC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
19.07.2021 |
