Aggregation of Time-Series Data Under Differential Privacy

摘要

In this work, we investigate the problem of statistical data analysis while preserving user privacy in the distributed and semi-honest setting. Particularly, we study properties of Private Stream Aggregation (PSA) schemes, first introduced by Shi et al. in 2011. A PSA scheme is a secure multiparty protocol for the aggregation of time-series data in a distributed network with a minimal communication cost. We show that in the non-adaptive query model, secure PSA schemes can be built upon any key-homomorphic weak pseudo-random function (PRF) and we provide a tighter security reduction. In contrast to the aforementioned work, this means that our security definition can be achieved in the standard model. In addition, we give two computationally efficient instantiations of this theoretic result. The security of the first instantiation comes from a key-homomorphic weak PRF based on the Decisional Diffie-Hellman problem and the security of the second one comes from a weak PRF based on the Decisional Learning with Errors problem. Moreover, due to the use of discrete Gaussian noise, the second construction inherently maintains a mechanism that preserves (ε, δ)-differential privacy in the final data-aggregate. A consequent feature of the constructed protocol is the use of the same noise for security and for differential privacy. As a result, we obtain an efficient prospective post-quantum PSA scheme for differentially private data analysis in the distributed model.