On Subset Retrieval and Group Testing Problems with Differential Privacy Constraints

Gonen, Mira; Langberg, Michael; Sprintson, Alex

Permalink

https://hdl.handle.net/2142/130305 Copy

Description

Title

On Subset Retrieval and Group Testing Problems with Differential Privacy Constraints

Author(s)

• Gonen, Mira
• Langberg, Michael
• Sprintson, Alex

Issue Date

2025-09-17

Keyword(s)

• Private information retrieval
• Group testing
• Differential privacy

Abstract

This paper focuses on the design and analysis of privacy-preserving techniques for group testing and infection status retrieval. Our work is motivated by the need to provide accurate information on the status of disease spread among a group of individuals while protecting the privacy of the infection status of any single individual involved. The paper is motivated by practical scenarios, such as controlling the spread of infectious diseases, where individuals might be reluctant to participate in testing if their outcomes are not kept confidential. The paper makes the following contributions. First, we introduce a differential privacy framework for the subset retrieval problem, which aims to securely share individuals’ infection status with third parties, such as administrators and decision-makers. We characterize the trade-off between the accuracy of subset retrieval and the degree of privacy guaranteed to the individuals. In particular, we establish tight lower and upper bounds on the achievable level of accuracy subject to the differential privacy constraints. We then formulate the differential privacy framework for the noisy group testing problem in which noise is added either before or after the pooling process. We establish a reduction between the private subset retrieval and noisy group testing problems and show that the converse and achievability schemes for subset retrieval carry over to differentially private group testing.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130305&&

Copyright and License Information

Copyright 2025 owned by the authors.

Owning Collections