差分隐私二维数据流统计发布

Differentially private statistical publication for two-dimensional data stream

目前关于差分隐私数据流统计发布的研究仅考虑一维数据流,其方法无法直接用于解决二维数据流统计发布中可能存在的隐私泄露问题。针对此问题,首先提出面向固定长度二维数据流的差分隐私统计发布算法——PTDSS算法。该算法通过单次线性扫描数据流,以较低空间消耗计算出满足一定条件的二维数据流元组的统计频度,并经过敏感度分析添加适量的噪声使其满足差分隐私要求;接着在PTDSS算法的基础上,利用滑动窗口机制,设计出面向任意长度二维数据流的差分隐私连续统计发布算法——PTDSS-SW。理论分析与实验结果表明,所提算法可安全地实现二维数据流统计发布的隐私保护,同时统计发布结果的相对误差在10%~95%。

Current research on statistical publication of differential privacy data stream only considers one-dimensional data stream. However, many applications require privacy protection publishing two-dimensional data stream, which makes traditional models and methods unusable. To solve the issue, firstly, a differential privacy statistical publication algorithm for fixed-length two-dimensional data stream, call PTDSS, was proposed. The tuple frequency of the two-dimensional data stream under certain condition was calculated by a one-time linear scan to the data stream with low-cost space. Basing on the result of sensitivity analysis, a certain amount of noise was added into the statistical results so as to meet the differential privacy requirement. After that, a differential privacy continuous statistical publication algorithm for any length two-dimensional data stream using sliding window model, called PTDSS-SW, was presented. The theoretical analysis and experimental results show that the proposed algorithms can safely preserve the privacy in the statistical publication of two-dimensional data stream and ensure the relative error of the released data in the range of 10% to 95%.