### Non-Interactive Anonymous Router with Quasi-Linear Router Computation

##### Abstract

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 (https://eprint.iacr.org/2022/1353).

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
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
History
2022-10-28: revised
See all versions
Short URL
https://ia.cr/2022/1395

CC BY

BibTeX

@misc{cryptoeprint:2022/1395,
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{https://eprint.iacr.org/2022/1395}},
url = {https://eprint.iacr.org/2022/1395}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.