Search Results

Documents authored by Lysyanskaya, Anna

Document
DOI: 10.4230/LIPIcs.ITC.2021.9
On the Complexity of Anonymous Communication Through Public Networks

Authors: Megumi Ando, Anna Lysyanskaya, and Eli Upfal

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

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.
Cite as

Megumi Ando, Anna Lysyanskaya, and Eli Upfal. On the Complexity of Anonymous Communication Through Public Networks. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 9:1-9:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ITC.2021.9},
  URN =		{urn:nbn:de:0030-drops-143282},
  doi =		{10.4230/LIPIcs.ITC.2021.9},
  annote =	{Keywords: Anonymity, privacy, onion routing}
}
Document
DOI: 10.4230/DagRep.9.1.88
Practical Yet Composably Secure Cryptographic Protocols (Dagstuhl Seminar 19042)

Authors: Jan Camenisch, Ralf Küsters, Anna Lysyanskaya, and Alessandra Scafuro

Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19042 "Practical Yet Composably Secure Cryptographic Protocols". The workshop's main aim was to enhance the community's understanding of (1) what a good model was for how various protocols and systems co-exist in a larger system; (2) how to model important tasks and security protocols in such a model; (3) how to prove security of protocols in such a model.
Cite as

Jan Camenisch, Ralf Küsters, Anna Lysyanskaya, and Alessandra Scafuro. Practical Yet Composably Secure Cryptographic Protocols (Dagstuhl Seminar 19042). In Dagstuhl Reports, Volume 9, Issue 1, pp. 88-103, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{camenisch_et_al:DagRep.9.1.88,
  author =	{Camenisch, Jan and K\"{u}sters, Ralf and Lysyanskaya, Anna and Scafuro, Alessandra},
  title =	{{Practical Yet Composably Secure Cryptographic Protocols (Dagstuhl Seminar 19042)}},
  pages =	{88--103},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{1},
  editor =	{Camenisch, Jan and K\"{u}sters, Ralf and Lysyanskaya, Anna and Scafuro, Alessandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.1.88},
  URN =		{urn:nbn:de:0030-drops-105710},
  doi =		{10.4230/DagRep.9.1.88},
  annote =	{Keywords: applied cryptography, cryptographic protocols, practical protocols, provably secure protocols, security models, universally composability}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.144
Practical and Provably Secure Onion Routing

Authors: Megumi Ando, Anna Lysyanskaya, and Eli Upfal

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In an onion routing protocol, messages travel through several intermediaries before arriving at their destinations; they are wrapped in layers of encryption (hence they are called "onions"). The goal is to make it hard to establish who sent the message. It is a practical and widespread tool for creating anonymous channels. For the standard adversary models - passive and active - we present practical and provably secure onion routing protocols. Akin to Tor, in our protocols each party independently chooses the routing paths for his onions. For security parameter lambda, our differentially private solution for the active adversary takes O(log^2 lambda) rounds and requires every participant to transmit O(log^{4} lambda) onions in every round.
Cite as

Megumi Ando, Anna Lysyanskaya, and Eli Upfal. Practical and Provably Secure Onion Routing. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 144:1-144:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ando_et_al:LIPIcs.ICALP.2018.144,
  author =	{Ando, Megumi and Lysyanskaya, Anna and Upfal, Eli},
  title =	{{Practical and Provably Secure Onion Routing}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{144:1--144:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.144},
  URN =		{urn:nbn:de:0030-drops-91482},
  doi =		{10.4230/LIPIcs.ICALP.2018.144},
  annote =	{Keywords: Anonymity, traffic analysis, statistical privacy, differential privacy}
}
Document
DOI: 10.4230/DagRep.1.9.76
Public-Key Cryptography (Dagstuhl Seminar 11391)

Authors: Marc Fischlin, Anna Lysyanskaya, Ueli Maurer, and Alexander May

Published in: Dagstuhl Reports, Volume 1, Issue 9 (2012)

Abstract
From September 25th till September 30th, 2011, the Dagstuhl Seminar 11391 about ``Public-Key Cryptography'' took place at Schloss Dagstuhl. The meeting hosted 33 international researchers and incited active discussions about recent developments in this area.
Cite as

Marc Fischlin, Anna Lysyanskaya, Ueli Maurer, and Alexander May. Public-Key Cryptography (Dagstuhl Seminar 11391). In Dagstuhl Reports, Volume 1, Issue 9, pp. 76-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{fischlin_et_al:DagRep.1.9.76,
  author =	{Fischlin, Marc and Lysyanskaya, Anna and Maurer, Ueli and May, Alexander},
  title =	{{Public-Key Cryptography (Dagstuhl Seminar 11391)}},
  pages =	{76--94},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{9},
  editor =	{Fischlin, Marc and Lysyanskaya, Anna and Maurer, Ueli and May, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.9.76},
  URN =		{urn:nbn:de:0030-drops-33685},
  doi =		{10.4230/DagRep.1.9.76},
  annote =	{Keywords: Fully-Homomorphic Encryption, Leakage-Resilience, Constructive Cryptography}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact