Homomorphic Encryption-Friendly Privacy-Preserving Partitioning Algorithm for Differential Privacy

Shojiro Ushiyama*, Tsubasa Takahashi, Masashi Kudo, Hayato Yamana

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This study addresses the privacy problems of data provided by multiple data owners for range query processing on the cloud. Although existing methods preserve data privacy against the cloud or data analysts who receive query responses, protecting data privacy from both remains a challenge. Combining differential privacy (DP) and homomorphic encryption (HE) to construct differentially private outputs over encrypted raw data is a promising way to avoid data privacy leakage to the cloud with encryption while protecting data privacy from data analysts with DP. Although DP adopts several partitioning algorithms to achieve small noise, partitioning cannot be executed once the data is encrypted. In this paper, we propose a new HE-friendly privacy-preserving partitioning algorithm satisfying DP. Although HE enables operations over encrypted data, the execution time of such primitive arithmetic operations is approximately 109 times slower than without encryption. Therefore, it is mandatory to reduce the calculation complexity. The proposed partitioning method, which only compares every next-to-each-other data to merge, achieves O(n) calculation complexity, where n is the domain size of the input histograms, whereas the greedy algorithm requires O(2n). The experimental evaluation showed that the execution time of the proposed algorithm for 4,096-domain-size data was approximately 4 h and 35 min, which was acceptable when creating a data summary for the range query processing system and not targeting on-the-fly adoption of DP. Additionally, we confirmed that the accuracy of the proposed algorithm was equivalent to that of the state-of-the-art partitioning algorithm.

Original languageEnglish
Title of host publicationProceedings - 2022 IEEE International Conference on Big Data, Big Data 2022
EditorsShusaku Tsumoto, Yukio Ohsawa, Lei Chen, Dirk Van den Poel, Xiaohua Hu, Yoichi Motomura, Takuya Takagi, Lingfei Wu, Ying Xie, Akihiro Abe, Vijay Raghavan
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages11
ISBN (Electronic)9781665480451
Publication statusPublished - 2022
Event2022 IEEE International Conference on Big Data, Big Data 2022 - Osaka, Japan
Duration: 2022 Dec 172022 Dec 20

Publication series

NameProceedings - 2022 IEEE International Conference on Big Data, Big Data 2022


Conference2022 IEEE International Conference on Big Data, Big Data 2022


  • TFHE
  • differential privacy
  • homomorphic encryption
  • partitioning

ASJC Scopus subject areas

  • Modelling and Simulation
  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management
  • Safety, Risk, Reliability and Quality
  • Control and Optimization


Dive into the research topics of 'Homomorphic Encryption-Friendly Privacy-Preserving Partitioning Algorithm for Differential Privacy'. Together they form a unique fingerprint.

Cite this