Frequency Estimation of Evolving Data Under Local Differential Privacy
| Autor: | Arcolezi, Héber H., Carlos Antonio Pinzón, Catuscia Palamidessi, Sébastien Gambs |
|---|---|
| Přispěvatelé: | Pinzón, Carlos, Privacy and Utility Allied - HYPATIA - - H2020 Pilier ERC2019-10-01 - 2024-09-30 - 835294 - VALID, Concurrency, Mobility and Transactions (COMETE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratory for Research on Technology for ECommerce (LATECE Laboratory - UQAM Montreal), Université du Québec à Montréal = University of Québec in Montréal (UQAM), Supported also by the Canada Research Chair program as well as a Discovery Grant from NSERC, European Project: 835294,H2020 Pilier ERC,HYPATIA(2019) |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] Computer Science - Cryptography and Security [INFO.INFO-DC] Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB] [INFO]Computer Science [cs] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] [INFO] Computer Science [cs] Cryptography and Security (cs.CR) [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR] |
| Zdroj: | HAL EDBT 2023-26th International Conference on Extending Database Technology EDBT 2023-26th International Conference on Extending Database Technology, May 2023, Ioánnina, Greece. pp.512-525, ⟨10.48786/edbt.2023.44⟩ |
| DOI: | 10.48550/arxiv.2210.00262 |
| Popis: | Collecting and analyzing evolving longitudinal data has become a common practice. One possible approach to protect the users' privacy in this context is to use local differential privacy (LDP) protocols, which ensure the privacy protection of all users even in the case of a breach or data misuse. Existing LDP data collection protocols such as Google's RAPPOR and Microsoft's dBitFlipPM can have longitudinal privacy linear to the domain size k, which is excessive for large domains, such as Internet domains. To solve this issue, in this paper we introduce a new LDP data collection protocol for longitudinal frequency monitoring named LOngitudinal LOcal HAshing (LOLOHA) with formal privacy guarantees. In addition, the privacy-utility trade-off of our protocol is only linear with respect to a reduced domain size $2\leq g \ll k$. LOLOHA combines a domain reduction approach via local hashing with double randomization to minimize the privacy leakage incurred by data updates. As demonstrated by our theoretical analysis as well as our experimental evaluation, LOLOHA achieves a utility competitive to current state-of-the-art protocols, while substantially minimizing the longitudinal privacy budget consumption by up to k/g orders of magnitude. Comment: Accepted at EDBT 2023. Updated structure and correcting privacy loss of dBitFlipPM |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|