Private Multi-Group Aggregation

Carolina Naim, Rafael G.L. D'Oliveira, Salim El Rouayheb

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study the differentially private multi-group aggregation (PMGA) problem. This setting involves a single server and n users. Each user belongs to one of k distinct groups and holds a discrete value representing his data. The goal is to design schemes that allow the server to find the aggregate (sum) of the values in each group (with high accuracy), under communication and local differential privacy constraints. The privacy constraint guarantees that the user's group remains private. This is motivated by applications where a user's group can reveal sensitive information, such as his religious and political beliefs, health condition, or race. We propose a novel scheme, dubbed Query and Aggregate (QA) for PMGA. The novelty of QA is that it is an interactive aggregation scheme. In QA, each user is assigned a random query matrix, to which he sends the server an answer based on his group and value. We characterize the QA scheme's performance in terms of accuracy (MSE), privacy, and communication. Private aggregation schemes for related settings in the literature are predominantly non-interactive and based on randomized response. We compare QA to the Randomized Group (RG) scheme, which adapts existing schemes to the PMGA setting. We observe that typically QA outperforms RG, in terms of utility vs. privacy, in the high privacy regime. Moreover, an attractive property of QA is that its communication cost per user does not depend on the number of groups.

Original languageEnglish (US)
Title of host publication2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781538682098
StatePublished - Jul 12 2021
Event2021 IEEE International Symposium on Information Theory, ISIT 2021 - Virtual, Melbourne, Australia
Duration: Jul 12 2021Jul 20 2021

Publication series

NameIEEE International Symposium on Information Theory - Proceedings


Conference2021 IEEE International Symposium on Information Theory, ISIT 2021
CityVirtual, Melbourne

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Applied Mathematics
  • Modeling and Simulation


Dive into the research topics of 'Private Multi-Group Aggregation'. Together they form a unique fingerprint.

Cite this