Efficient and Secure Quantile Aggregation of Private Data Streams
- 3 May 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Forensics and Security
- Vol. 18 (15566013) , 3058-3073
Abstract
Computing the quantile of a massive data stream has been a crucial task in networking and data management. However, existing solutions assume a centralized model where one data owner has access to all data. In this paper, we put forward a study of secure quantile aggregation between private data streams, where data streams owned by different parties would like to obtain a quantile of the union of their data without revealing anything else about their inputs. To this end, we designed efficient cryptographic protocols that are secure in the semi-honest setting as well as the malicious setting. By incorporating differential privacy, we further improve the efficiency by 1.1× to 73.1×. We implemented our protocol, which shows practical efficiency to aggregate real-world data streams efficiently.Keywords
Funding Information
- National Key Research and Development Program of China (2022YFB3102500)
- National Natural Science Foundation of China (61802270, U19A2081)
- National Key Research and Development Program of China (2022YFB2702000)
- National Natural Science Foundation of China (62022018, 61932019, 61802021)
This publication has 40 references indexed in Scilit:
- GraphSC: Parallel Secure Computation Made Easy2015
- Efficient, Oblivious Data Structures for MPC2014
- Quantiles over data streams2013
- Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams2012
- Medians and beyond2004
- Power-conserving computation of order-statistics over sensor networks2004
- Finding Frequent Items in Data Streams2002
- The space complexity of approximating the frequency moments1996
- Finding repeated elementsScience of Computer Programming, 1982
- Counting large numbers of events in small registersCommunications of the ACM, 1978