International Association for Cryptologic Research

International Association
for Cryptologic Research


Onion Routing with Replies

Christiane Kuhn , Karlsruhe Institute of Technology
Dennis Hofheinz , ETH Z├╝rich
Andy Rupp , University of Luxembourg
Thorsten Strufe , Karlsruhe Institute of Technology
DOI: 10.1007/978-3-030-92075-3_20
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
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.
Video from ASIACRYPT 2021
  title={Onion Routing with Replies},
  author={Christiane Kuhn and Dennis Hofheinz and Andy Rupp and Thorsten Strufe},