Cryptology ePrint Archive: Report 2021/435

Non-Interactive Anonymous Router

Elaine Shi and Ke Wu

Abstract: Anonymous routing is one of the most fundamental online privacy problems and has been studied extensively for decades. Almost all known approaches for anonymous routing (e.g., mix-nets, DC-nets, and others) rely on multiple servers or routers to engage in some {\it interactive} protocol; and anonymity is guaranteed in the {\it threshold} model, i.e., if one or more of the servers/routers behave honestly.

Departing from all prior approaches, we propose a novel {\it non-interactive} abstraction called a Non-Interactive Anonymous Router (NIAR), which works even with a {\it single untrusted router}. In a NIAR scheme, suppose that $n$ senders each want to talk to a distinct receiver. A one-time trusted setup is performed such that each sender obtains a sending key, each receiver obtains a receiving key, and the router receives a {\it token} that ``encrypts'' the permutation mapping the senders to receivers. In every time step, each sender can encrypt its message using its sender key, and the router can use its token to convert the $n$ ciphertexts received from the senders to $n$ {\it transformed ciphertexts}. Each transformed ciphertext is delivered to the corresponding receiver, and the receiver can decrypt the message using its receiver key. Imprecisely speaking, security requires that the untrusted router, even when colluding with a subset of corrupt senders and/or receivers, should not be able to compromise the privacy of honest parties, including who is talking to who, and the message contents.

We show how to construct a communication-efficient NIAR scheme with provable security guarantees based on the standard Decisional Linear assumption in suitable bilinear groups. We show that a compelling application of NIAR is to realize a Non-Interactive Anonymous Shuffler (NIAS), where an untrusted server or data analyst can only decrypt a permuted version of the messages coming from $n$ senders where the permutation is hidden. NIAS can be adopted to construct privacy-preserving surveys, differentially private protocols in the shuffle model, and pseudonymous bulletin boards.

Besides this main result, we also describe a variant that achieves fault tolerance when a subset of the senders may crash. Finally, we further explore a paranoid notion of security called full insider protection, and show that if we additionally assume sub-exponentially secure Indistinguishability Obfuscation and as sub-exponentially secure one-way functions, one can construct a NIAR scheme with paranoid security.

Category / Keywords: foundations / anonymous routing, functional encryption, non-interactive

Original Publication (with major differences): IACR-EUROCRYPT-2021

Date: received 2 Apr 2021, last revised 2 Apr 2021

Contact author: runting at gmail com

Available format(s): PDF | BibTeX Citation

Note: This is the full version containing additional constructions and proofs that were omitted from the conference version.

Version: 20210406:072257 (All versions of this report)

Short URL: ia.cr/2021/435


[ Cryptology ePrint archive ]