Paper 2020/215

Cryptographic Shallots: A Formal Treatment of Repliable Onion Encryption

Megumi Ando and Anna Lysyanskaya


Onion routing is a popular, efficient and scalable method for enabling anonymous communications. To send a message m to Bob via onion routing, Alice picks several intermediaries, wraps m in multiple layers of encryption — one per intermediary — and sends the resulting “onion” to the first intermediary. Each intermediary “peels” a layer of encryption and learns the identity of the next entity on the path and what to send along; finally Bob learns that he is the recipient, and recovers the message m. Despite its wide use in the real world (e.g., Tor, Mixminion), the foundations of onion routing have not been thoroughly studied. In particular, although two-way communication is needed in most instances, such as anonymous Web browsing, or anonymous access to a resource, until now no definitions or provably secure constructions have been given for two-way onion routing. In this paper, we propose an ideal functionality for a repliable onion encryption scheme and provide a construction that UC-realizes it.

Available format(s)
Publication info
Anonymityprivacyonion routing
Contact author(s)
mando @ cs brown edu
anna @ cs brown edu
2020-05-29: revised
2020-02-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Megumi Ando and Anna Lysyanskaya},
      title = {Cryptographic Shallots: A Formal Treatment of Repliable Onion Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/215},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.