[Resource Topic] 2022/1395: Non-Interactive Anonymous Router with Quasi-Linear Router Computation

Welcome to the resource topic for 2022/1395

Title:
Non-Interactive Anonymous Router with Quasi-Linear Router Computation

Authors: Rex Fernando, Elaine Shi, Pratik Soni, Nikhil Vanjani

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.

ePrint: https://eprint.iacr.org/2022/1395

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .