Multiparty Reach and Frequency Histogram: Private, Secure, and Practical

Consider the setting where multiple parties each hold a multiset of users and the task is to estimate the reach (i.e., the number of distinct users appearing across all parties) and the frequency histogram (i.e., fraction of users appearing a given number of times across all parties). In this work w...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Ghazi Badih, Kreuter Ben, Kumar Ravi, Manurangsi Pasin, Peng Jiayu, Skvortsov Evgeny, Wang Yao, Wright Craig
Formato:	article
Lenguaje:	EN
Publicado:	Sciendo 2022
Materias:	reach frequency histogram sketching differential privacy multiparty computation Ethics BJ1-1725 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/ee61c3a3b0c04bec81eac61e29c523ec
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:ee61c3a3b0c04bec81eac61e29c523ec
record_format	dspace
spelling	oai:doaj.org-article:ee61c3a3b0c04bec81eac61e29c523ec2021-12-05T14:11:10ZMultiparty Reach and Frequency Histogram: Private, Secure, and Practical2299-098410.2478/popets-2022-0019https://doaj.org/article/ee61c3a3b0c04bec81eac61e29c523ec2022-01-01T00:00:00Zhttps://doi.org/10.2478/popets-2022-0019https://doaj.org/toc/2299-0984Consider the setting where multiple parties each hold a multiset of users and the task is to estimate the reach (i.e., the number of distinct users appearing across all parties) and the frequency histogram (i.e., fraction of users appearing a given number of times across all parties). In this work we introduce a new sketch for this task, based on an exponentially distributed counting Bloom filter. We combine this sketch with a communication-efficient multi-party protocol to solve the task in the multi-worker setting. Our protocol exhibits both differential privacy and security guarantees in the honest-but-curious model and in the presence of large subsets of colluding workers; furthermore, its reach and frequency histogram estimates have a provably small error. Finally, we show the practicality of the protocol by evaluating it on internet-scale audiences.Ghazi BadihKreuter BenKumar RaviManurangsi PasinPeng JiayuSkvortsov EvgenyWang YaoWright CraigSciendoarticlereachfrequency histogramsketchingdifferential privacymultiparty computationEthicsBJ1-1725Electronic computers. Computer scienceQA75.5-76.95ENProceedings on Privacy Enhancing Technologies, Vol 2022, Iss 1, Pp 373-395 (2022)
institution	DOAJ
collection	DOAJ
language	EN
topic	reach frequency histogram sketching differential privacy multiparty computation Ethics BJ1-1725 Electronic computers. Computer science QA75.5-76.95
spellingShingle	reach frequency histogram sketching differential privacy multiparty computation Ethics BJ1-1725 Electronic computers. Computer science QA75.5-76.95 Ghazi Badih Kreuter Ben Kumar Ravi Manurangsi Pasin Peng Jiayu Skvortsov Evgeny Wang Yao Wright Craig Multiparty Reach and Frequency Histogram: Private, Secure, and Practical
description	Consider the setting where multiple parties each hold a multiset of users and the task is to estimate the reach (i.e., the number of distinct users appearing across all parties) and the frequency histogram (i.e., fraction of users appearing a given number of times across all parties). In this work we introduce a new sketch for this task, based on an exponentially distributed counting Bloom filter. We combine this sketch with a communication-efficient multi-party protocol to solve the task in the multi-worker setting. Our protocol exhibits both differential privacy and security guarantees in the honest-but-curious model and in the presence of large subsets of colluding workers; furthermore, its reach and frequency histogram estimates have a provably small error. Finally, we show the practicality of the protocol by evaluating it on internet-scale audiences.
format	article
author	Ghazi Badih Kreuter Ben Kumar Ravi Manurangsi Pasin Peng Jiayu Skvortsov Evgeny Wang Yao Wright Craig
author_facet	Ghazi Badih Kreuter Ben Kumar Ravi Manurangsi Pasin Peng Jiayu Skvortsov Evgeny Wang Yao Wright Craig
author_sort	Ghazi Badih
title	Multiparty Reach and Frequency Histogram: Private, Secure, and Practical
title_short	Multiparty Reach and Frequency Histogram: Private, Secure, and Practical
title_full	Multiparty Reach and Frequency Histogram: Private, Secure, and Practical
title_fullStr	Multiparty Reach and Frequency Histogram: Private, Secure, and Practical
title_full_unstemmed	Multiparty Reach and Frequency Histogram: Private, Secure, and Practical
title_sort	multiparty reach and frequency histogram: private, secure, and practical
publisher	Sciendo
publishDate	2022
url	https://doaj.org/article/ee61c3a3b0c04bec81eac61e29c523ec
work_keys_str_mv	AT ghazibadih multipartyreachandfrequencyhistogramprivatesecureandpractical AT kreuterben multipartyreachandfrequencyhistogramprivatesecureandpractical AT kumarravi multipartyreachandfrequencyhistogramprivatesecureandpractical AT manurangsipasin multipartyreachandfrequencyhistogramprivatesecureandpractical AT pengjiayu multipartyreachandfrequencyhistogramprivatesecureandpractical AT skvortsovevgeny multipartyreachandfrequencyhistogramprivatesecureandpractical AT wangyao multipartyreachandfrequencyhistogramprivatesecureandpractical AT wrightcraig multipartyreachandfrequencyhistogramprivatesecureandpractical
_version_	1718371332005036032

Multiparty Reach and Frequency Histogram: Private, Secure, and Practical

Ejemplares similares