Construction of Differentially Private Summaries over Fully Homomorphic Encryption

Shojiro Ushiyama, Tsubasa Takahashi, Masashi Kudo, Hayato Yamana

Introduction

Cloud-based database services offer immense utility for data analysis but introduce significant privacy risks for sensitive information. Ideally, a cloud server should be able to answer an analyst's queries without the server or the analyst ever accessing raw data. Previous state-of-the-art systems, such as Crypt$ε$, attempted to address this by combining Homomorphic Encryption (HE) and Differential Privacy (DP). However, these systems suffer from two critical vulnerabilities: privacy leakage due to temporary decryption during data sorting and poor accuracy resulting from naive, equal-width data partitioning that necessitates excessive DP noise.

This paper proposes a novel framework that constructs a "DP-summary" entirely over encrypted data. By utilizing a data-aware partitioning algorithm and bit-wise Fully Homomorphic Encryption (FHE), the system prevents raw data leakage while significantly improving the utility of query responses.

The Proposed Framework

The authors introduce a system architecture comprising Data Owners (DO), a Computation Server (CS), and a Decryption Server (DS). Unlike previous models that might expose intermediate plaintext, this architecture ensures that the CS only operates on ciphertexts and the DS only decrypts data that has already been protected by DP noise.

The proposed system architecture utilizing TFHE and optimized-width partitioning.

Key components of the framework include:

  1. Encryption: Data Owners encrypt their data using symmetric keys before transmission to the CS.
  2. Bit-wise FHE (TFHE): To support complex branching logic (e.g., finding minimums or absolute values) required for intelligent partitioning without decryption, the system employs Torus Fully Homomorphic Encryption (TFHE).
  3. Decryption Server (DS): A separate entity that only decrypts the final summary after DP noise has been applied, ensuring the analyst never sees raw data.

Constructing the DP-Summary

The core innovation lies in how the DP-summary is built. Instead of naive partitioning, the CS implements a data-aware portion of the DAWA (Data- and Workload-Aware) algorithm over ciphertexts. This approach groups similar histogram values into buckets to minimize the total noise required for a given privacy budget.

Illustration of the DP-summary construction process from encrypted histogram to differentially private output.

As shown in the process flow above, the system transforms an encrypted histogram into a differentially private summary through several homomorphic steps:

  • Smart Partitioning: The CS evaluates partition combinations homomorphically to find optimal bucket boundaries.
  • Noise Addition: Laplace noise is added to the partitioned clusters using homomorphic operations.
  • Plaintext Availability: Once decrypted, the summary is safe to store in plaintext. Analysts can then query this summary instantly and infinitely without further depleting the privacy budget.

Key Insights and Results

Privacy and Accuracy

By applying DP before any decryption occurs, the system achieves a tighter security guarantee than prior work. The authors found that the fixed-point arithmetic required by TFHE did not degrade accuracy; truncation errors were negligible compared to the intentional DP noise. Smart partitioning significantly outperformed naive methods by reducing the noise overhead in sparse data regions.

Computational Overhead

The primary trade-off for this enhanced security is performance. Constructing a DP-summary for a small dataset (domain size of 8, 16-bit data) required 12.5 hours on high-end hardware. The construction time scales linearly with bit size but exponentially ($O(2^n)$) with the domain size $n$, as the server must homomorphically search all possible partition combinations.

Conclusion and Future Work

This research demonstrates the feasibility of building differentially private summaries over FHE without intermediate decryption. While the current implementation provides a robust privacy-first model, its computational complexity limits its application to small-scale 1D histograms. Future work will focus on optimizing FHE operations and refining the algorithmic approach to improve scalability for larger, real-world datasets.

Summary updated

BibTeX
@inproceedings{ushiyama2021construction,
  author = {Shojiro Ushiyama and Tsubasa Takahashi and Masashi Kudo and Hayato Yamana},
  title = {{Construction of Differentially Private Summaries over Fully Homomorphic Encryption}},
  booktitle = {DEXA},
  year = {2021},
  url = {https://openreview.net/forum?id=r4I0vjw04Ok},
}
Figure