International Association for Cryptologic Research

International Association
for Cryptologic Research


Megumi Ando


Cryptographic Shallots: A Formal Treatment of Repliable Onion Encryption 📺
Megumi Ando 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 --- a layer per intermediary --- and sends the resulting “onion” to the first intermediary. Each intermediary “peels off'”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., 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. Moreover, the security definitions that existed even for one-way onion routing were found to have significant flaws. In this paper, we (1) propose an ideal functionality for a repliable onion encryption scheme; (2) give a game-based definition for repliable onion encryption and show that it is sufficient to realize our ideal functionality; and finally (3), our main result is a construction of repliable onion encryption that satisfies our definitions.


Anna Lysyanskaya (1)