International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 15 October 2022

Rex Fernando, Elaine Shi, Pratik Soni, Nikhil Vanjani
ePrint Report ePrint Report
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.
Expand

Additional news items may be found on the IACR news page.