### Anonymous Permutation Routing

##### Abstract

The Non-Interactive Anonymous Router (NIAR) model was introduced by Shi and Wu [SW21] as an alternative to conventional solutions to the anonymous routing problem, in which a set of senders wish to send messages to a set of receivers. In contrast to most known approaches to support anonymous routing (e.g. mix-nets, DC-nets, etc.) which rely on a network of routers communicating with users via interactive protocols, the NIAR model assumes a $single$ router and is inherently $non$-$interactive$ (after an initial setup phase). In addition to being non-interactive, the NIAR model is compelling due to the security it provides: instead of relying on the honesty of some subset of the routers, the NIAR model requires anonymity even if the router (as well as an arbitrary subset of senders/receivers) is corrupted. In this paper, we present a protocol for the NIAR model that improves upon the results from [SW21] in two ways: - Improved computational efficiency (quadratic to near linear): Our protocol matches the communication complexity of [SW21] for each sender/receiver, while reducing the computational overhead for the router to polylog overhead instead of linear overhead. - Relaxation of assumptions: Security of the protocol in [SW21] relies on the Decisional Linear assumption in bilinear groups; while security for our protocol follows from the existence of any rate-1 oblivious transfer (OT) protocol (instantiations of this primitive are known to exist under DDH, QR and LWE [DGI19,GHO20]).

##### Metadata
Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Anonymous Routing Private-Information Retrieval Permutation Routing Non-Interactive Protocols
Contact author(s)
paul @ stealthsoftwareinc com
eyalk @ cs technion ac il
rafail @ cs ucla edu
History
2022-10-14: approved
2022-10-10: received
See all versions
Short URL
https://ia.cr/2022/1353
License

CC BY

BibTeX

@misc{cryptoeprint:2022/1353,
author = {Paul Bunn and Eyal Kushilevitz and Rafail Ostrovsky},
title = {Anonymous Permutation Routing},
howpublished = {Cryptology ePrint Archive, Paper 2022/1353},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1353}},
url = {https://eprint.iacr.org/2022/1353}
}

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