2026-07-20T07:30:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18345 2024-03-06T11:01:43Z ddc:004 open_access

Differentially Private Aggregation via Imperfect Shuffling Ghazi, Badih Kumar, Ravi Manurangsi, Pasin Nelson, Jelani Zhou, Samson Differential privacy private summation shuffle model In this paper, we introduce the imperfect shuffle differential privacy model, where messages sent from users are shuffled in an almost uniform manner before being observed by a curator for private aggregation. We then consider the private summation problem. We show that the standard split-and-mix protocol by Ishai et. al. [FOCS 2006] can be adapted to achieve near-optimal utility bounds in the imperfect shuffle model. Specifically, we show that surprisingly, there is no additional error overhead necessary in the imperfect shuffle model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Badih Ghazi and Ravi Kumar and Pasin Manurangsi and Jelani Nelson and Samson Zhou 2023 Is Part Of LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2023.17 urn:nbn:de:0030-drops-183453 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.17 eng https://creativecommons.org/licenses/by/4.0/legalcode