Paper 2021/1242

Non-Interactive Differentially Anonymous Router

Benedikt Bünz, Yuncong Hu, 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)$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
anonymous routingdifferential privacynon-interactive
Contact author(s)
yuncong_hu @ berkeley edu
runting @ gmail com
History
2021-09-20: received
Short URL
https://ia.cr/2021/1242
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1242,
      author = {Benedikt Bünz and Yuncong Hu and Shin’ichiro Matsuo and Elaine Shi},
      title = {Non-Interactive Differentially Anonymous Router},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1242},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1242}},
      url = {https://eprint.iacr.org/2021/1242}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.