Paper 2020/215

Cryptographic Shallots: A Formal Treatment of Repliable Onion Encryption

Megumi Ando and Anna Lysyanskaya

Abstract

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.