Making the Most of Parallel Composition in Differential Privacy

We show that the ‘optimal’ use of the parallel composition theorem corresponds to finding the size of the largest subset of queries that ‘overlap’ on the data domain, a quantity we call the maximum overlap of the queries. It has previously been shown that a certain instance of this problem, formulat...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Smith Josh, Asghar Hassan Jameel, Gioiosa Gianpaolo, Mrabet Sirine, Gaspers Serge, Tyler Paul
Formato:	article
Lenguaje:	EN
Publicado:	Sciendo 2022
Materias:	differential privacy parallel composition graphs Ethics BJ1-1725 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/2d316acc6e2445f09a898b07d3ad25d1
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:2d316acc6e2445f09a898b07d3ad25d1
record_format	dspace
spelling	oai:doaj.org-article:2d316acc6e2445f09a898b07d3ad25d12021-12-05T14:11:10ZMaking the Most of Parallel Composition in Differential Privacy2299-098410.2478/popets-2022-0013https://doaj.org/article/2d316acc6e2445f09a898b07d3ad25d12022-01-01T00:00:00Zhttps://doi.org/10.2478/popets-2022-0013https://doaj.org/toc/2299-0984We show that the ‘optimal’ use of the parallel composition theorem corresponds to finding the size of the largest subset of queries that ‘overlap’ on the data domain, a quantity we call the maximum overlap of the queries. It has previously been shown that a certain instance of this problem, formulated in terms of determining the sensitivity of the queries, is NP-hard, but also that it is possible to use graph-theoretic algorithms, such as finding the maximum clique, to approximate query sensitivity. In this paper, we consider a significant generalization of the aforementioned instance which encompasses both a wider range of differentially private mechanisms and a broader class of queries. We show that for a particular class of predicate queries, determining if they are disjoint can be done in time polynomial in the number of attributes. For this class, we show that the maximum overlap problem remains NP-hard as a function of the number of queries. However, we show that efficient approximate solutions exist by relating maximum overlap to the clique and chromatic numbers of a certain graph determined by the queries. The link to chromatic number allows us to use more efficient approximate algorithms, which cannot be done for the clique number as it may underestimate the privacy budget. Our approach is defined in the general setting of f-differential privacy, which subsumes standard pure differential privacy and Gaussian differential privacy. We prove the parallel composition theorem for f-differential privacy. We evaluate our approach on synthetic and real-world data sets of queries. We show that the approach can scale to large domain sizes (up to 1020000), and that its application can reduce the noise added to query answers by up to 60%.Smith JoshAsghar Hassan JameelGioiosa GianpaoloMrabet SirineGaspers SergeTyler PaulSciendoarticledifferential privacyparallel compositiongraphsEthicsBJ1-1725Electronic computers. Computer scienceQA75.5-76.95ENProceedings on Privacy Enhancing Technologies, Vol 2022, Iss 1, Pp 253-273 (2022)
institution	DOAJ
collection	DOAJ
language	EN
topic	differential privacy parallel composition graphs Ethics BJ1-1725 Electronic computers. Computer science QA75.5-76.95
spellingShingle	differential privacy parallel composition graphs Ethics BJ1-1725 Electronic computers. Computer science QA75.5-76.95 Smith Josh Asghar Hassan Jameel Gioiosa Gianpaolo Mrabet Sirine Gaspers Serge Tyler Paul Making the Most of Parallel Composition in Differential Privacy
description	We show that the ‘optimal’ use of the parallel composition theorem corresponds to finding the size of the largest subset of queries that ‘overlap’ on the data domain, a quantity we call the maximum overlap of the queries. It has previously been shown that a certain instance of this problem, formulated in terms of determining the sensitivity of the queries, is NP-hard, but also that it is possible to use graph-theoretic algorithms, such as finding the maximum clique, to approximate query sensitivity. In this paper, we consider a significant generalization of the aforementioned instance which encompasses both a wider range of differentially private mechanisms and a broader class of queries. We show that for a particular class of predicate queries, determining if they are disjoint can be done in time polynomial in the number of attributes. For this class, we show that the maximum overlap problem remains NP-hard as a function of the number of queries. However, we show that efficient approximate solutions exist by relating maximum overlap to the clique and chromatic numbers of a certain graph determined by the queries. The link to chromatic number allows us to use more efficient approximate algorithms, which cannot be done for the clique number as it may underestimate the privacy budget. Our approach is defined in the general setting of f-differential privacy, which subsumes standard pure differential privacy and Gaussian differential privacy. We prove the parallel composition theorem for f-differential privacy. We evaluate our approach on synthetic and real-world data sets of queries. We show that the approach can scale to large domain sizes (up to 1020000), and that its application can reduce the noise added to query answers by up to 60%.
format	article
author	Smith Josh Asghar Hassan Jameel Gioiosa Gianpaolo Mrabet Sirine Gaspers Serge Tyler Paul
author_facet	Smith Josh Asghar Hassan Jameel Gioiosa Gianpaolo Mrabet Sirine Gaspers Serge Tyler Paul
author_sort	Smith Josh
title	Making the Most of Parallel Composition in Differential Privacy
title_short	Making the Most of Parallel Composition in Differential Privacy
title_full	Making the Most of Parallel Composition in Differential Privacy
title_fullStr	Making the Most of Parallel Composition in Differential Privacy
title_full_unstemmed	Making the Most of Parallel Composition in Differential Privacy
title_sort	making the most of parallel composition in differential privacy
publisher	Sciendo
publishDate	2022
url	https://doaj.org/article/2d316acc6e2445f09a898b07d3ad25d1
work_keys_str_mv	AT smithjosh makingthemostofparallelcompositionindifferentialprivacy AT asgharhassanjameel makingthemostofparallelcompositionindifferentialprivacy AT gioiosagianpaolo makingthemostofparallelcompositionindifferentialprivacy AT mrabetsirine makingthemostofparallelcompositionindifferentialprivacy AT gaspersserge makingthemostofparallelcompositionindifferentialprivacy AT tylerpaul makingthemostofparallelcompositionindifferentialprivacy
_version_	1718371288552046592

Making the Most of Parallel Composition in Differential Privacy

Ejemplares similares