CryptoDB
Anonymous Permutation Routing
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| Abstract: | The Non-Interactive Anonymous Router (NIAR) model was introduced by Shi and Wu \cite{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 by an honest-but-curious adversary. In this paper, we present a protocol for the NIAR model that improves upon the results from \cite{SW21} in two ways: - Improved computational efficiency (quadratic to near linear): Our protocol matches the communication complexity of \cite{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 \cite{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 which are known to exist under the DDH, QR and LWE assumptions \cite{DGI19,GHO20}). |
BibTeX
@inproceedings{tcc-2023-33650,
title={Anonymous Permutation Routing},
publisher={Springer-Verlag},
author={Paul Bunn and Eyal Kushilevitz and Rafail Ostrovsky},
year=2023
}