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.

By admin