Paper 2022/1395
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).
Metadata
- Available format(s)
-
PDF
- 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
- 2022-10-14: received
- See all versions
- Short URL
- https://ia.cr/2022/1395
- License
-
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}
}
