Cryptology ePrint Archive: Report 2021/1178

Onion Routing with Replies

Christiane Kuhn and Dennis Hofheinz and Andy Rupp and Thorsten Strufe

Abstract: Onion routing (OR) protocols are a crucial tool for providing anonymous internet communication. An OR protocol enables a user to anonymously send requests to a server. A fundamental problem of OR protocols is how to deal with replies: ideally, we would want the server to be able to send a reply back to the anonymous user without knowing or disclosing the user's identity.

Existing OR protocols do allow for such replies, but do not provably protect the payload (i.e., message) of replies against manipulation. Kuhn et al. (IEEE S&P 2020) show that such manipulations can in fact be leveraged to break anonymity of the whole protocol.

In this work, we close this gap and provide the first framework and protocols for OR with protected replies. We define security in the sense of an ideal functionality in the universal composability model, and provide corresponding (less complex) game-based security notions for the individual properties.

We also provide two secure instantiations of our framework: one based on updatable encryption, and one based on succinct non-interactive arguments (SNARGs) to authenticate payloads both in requests and replies. In both cases, our central technical handle is an implicit authentication of the transmitted payload data, as opposed to an explicit, but insufficient authentication (with MACs) in previous solutions. Our results exhibit a new and surprising application of updatable encryption outside of long-term data storage.

Category / Keywords: cryptographic protocols / Privacy, Anonymity, Updatable Encryption, SNARGs, Onion Routing, Mix Networks

Original Publication (with major differences): IACR-ASIACRYPT-2021

Date: received 14 Sep 2021

Contact author: christiane kuhn at kit edu

Available format(s): PDF | BibTeX Citation

Version: 20210914:180230 (All versions of this report)

Short URL: ia.cr/2021/1178


[ Cryptology ePrint archive ]