CryptoDB
Non-Interactive Anonymous Router
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | EUROCRYPT 2021 |
| Abstract: | Anonymous routing is one of the most fundamental online privacy problems and has been studied extensively for decades. Almost all known approaches that achieve anonymous routing (e.g., mix-nets, DC-nets, and numerous other systems) rely on multiple servers or routers to engage in some interactive protocol; and anonymity is guaranteed in the threshold model, i.e., if one or more of the servers/routers behave honestly. Departing from all prior approaches, we propose a novel non-interactive abstraction called a Non-Interactive Anonymous Router (NIAR), that works even with a 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 token that “encrypts” the permutation mapping the senders to receivers. In every time step, the senders can each 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 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 break the privacy of honest parties, including who is talking to who, and the messages they exchange. We show how to construct a communication-efficient NIAR scheme with provable security guarantees based on the SXDH assumption in suitable bilinear groups and assuming Random Oracles (RO); further, the RO assumption can be removed if we allow a public key that is as large as the number of time steps supported. We also define a paranoid notion of security that achieves 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. We show that a com- pelling application of NIAR is to realize a Non-Interactive Anonymous Shuffler (NIAS), where an untrusted server or data analyst can only de- crypt a shuffled 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. |
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30824,
title={Non-Interactive Anonymous Router},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-77883-5_17},
author={Elaine Shi and Ke Wu},
year=2021
}