Cryptology ePrint Archive: Report 2021/1242

Non-Interactive Differentially Anonymous Router

Benedikt Bünz and Yuncong Hu and Shin’ichiro Matsuo and Elaine Shi

Abstract: A recent work by Shi and Wu (Eurocrypt'21) sugested a new, non-interactive abstraction for anonymous routing, coined Non-Interactive Anonymous Router (\NIAR). They show how to construct a \NIAR scheme with succinct communication from bilinear groups. Unfortunately, the router needs to perform quadratic computation (in the number of senders/receivers) to perform each routing.

In this paper, we show that if one is willing to relax the security notion to $(\epsilon, \delta)$-differential privacy, henceforth also called $(\epsilon, \delta)$-differential anonymity, then, a non-interactive construction exists with subquadratic router computation, also assuming standard hardness assumptions in bilinear groups. Morever, even when $1-1/\poly\log n$ fraction of the senders are corrupt, we can attain strong privacy parameters where $\epsilon = O(1/\poly\log n)$ and $\delta = \negl(n)$.

Category / Keywords: cryptographic protocols / anonymous routing, differential privacy, non-interactive

Date: received 18 Sep 2021

Contact author: yuncong_hu at berkeley edu, runting at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210920:115000 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]