Paper 2017/1107
Hardness of Non-Interactive Differential Privacy from One-Way Functions
Abstract
A central challenge in differential privacy is to design computationally efficient non-interactive algorithms that can answer large numbers of statistical queries on a sensitive dataset. That is, we would like to design a differentially private algorithm that takes a dataset
Note: Update on 5/22/24: We thank Mark Zhandry for pointing out a bug in our previous construction of two-message functional encryption (section 6) which appeared in the CRYPTO 2018 version of the paper, and suggesting the fix that we implemented in the current updated version. While the construction is more complex, the final results and parameters remain unchanged.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in CRYPTO 2018
- Keywords
- differential privacyone-way functionstraitor tracingfunctional encryption
- Contact author(s)
- danwichs @ gmail com
- History
- 2024-05-23: last of 3 revisions
- 2017-11-20: received
- See all versions
- Short URL
- https://ia.cr/2017/1107
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/1107, author = {Lucas Kowalczyk and Tal Malkin and Jonathan Ullman and Daniel Wichs}, title = {Hardness of Non-Interactive Differential Privacy from One-Way Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/1107}, year = {2017}, url = {https://eprint.iacr.org/2017/1107} }