Paper 2022/1395

Non-Interactive Anonymous Router with Quasi-Linear Router Computation

Rex Fernando, Carnegie Mellon University
Elaine Shi, Carnegie Mellon University
Pratik Soni, Carnegie Mellon University
Nikhil Vanjani, Carnegie Mellon University

Anonymous routing is an important cryptographic primitive that allows users to communicate privately on the Internet, without revealing their message contents or their contacts. Until the very recent work of Shi and Wu (Eurocrypt’21), all classical anonymous routing schemes are interactive protocols, and their security rely on a threshold number of the routers being honest. The recent work of Shi and Wu suggested a new abstraction called Non-Interactive Anonymous Router (NIAR), and showed how to achieve anonymous routing non-interactively for the first time. In particular, a single untrusted router receives a token which allows it to obliviously apply a permutation to a set of encrypted messages from the senders. While Shi and Wu’s scheme is efficient in other dimensions, one unsatisfying aspect of their construction is that the router takes time quadratic in the number of senders to obliviously route their messages. In this work, we show how to construct a non-interactive anonymous router scheme with sub-quadratic router computation, assuming the existence of subexponential indistinguishability obfuscation and one-way permutation. To achieve this, we devise new techniques for reasoning about a network of obfuscated programs.

Note: The revised version includes a comparison with the concurrent and independent work of Bunn, Kushilevitz, and Ostrovsky (

Available format(s)
Publication info
anonymous routing non-interactive digital signature schemes obfuscation
Contact author(s)
rex1fernando @ gmail com
runting @ cs cmu edu
psoni @ andrew cmu edu
nvanjani @ andrew cmu edu
2022-10-28: revised
2022-10-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rex Fernando and Elaine Shi and Pratik Soni and Nikhil Vanjani},
      title = {Non-Interactive Anonymous Router with Quasi-Linear Router Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1395},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.