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.
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)