蔡剑平，吴英杰，王晓东

福州大学数学与计算机科学学院，福州350116

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0481-14



基于矩阵机制的差分隐私连续数据发布方法*

蔡剑平，吴英杰+，王晓东

福州大学数学与计算机科学学院，福州350116

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0481-14

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant No. 61300026 (国家自然科学基金); the Natural Science Foundation of Fujian Province under Grant No. 2014J01230 (福建省自然科学基金).

Received 2015-06,Accepted 2015-08.

CNKI网络优先出版: 2015-08-27, http://www.cnki.net/kcms/detail/11.5602.TP.20150827.1411.002.html

摘要：现有绝大多数差分隐私算法只考虑数据的一次静态发布，而实际许多数据分析应用却涉及连续数据发布。为此，提出了一种基于矩阵机制的差分隐私连续数据发布方法。该方法的核心思想是首先利用树状数组构建连续数据发布问题的策略矩阵，然后对策略矩阵进行优化以提高发布数据的精确性。随后，进一步针

对现有基于矩阵机制的优化算法复杂度极高的问题，提出了时间复杂度为O(lg N)的快速对角阵优化算法（fast diagonal matrix optimization algorithm，FDA），以有效应用于大规模的连续数据发布。通过实验比较分析了FDA算法与同类算法所发布数据的精确度，结果表明FDA算法是有效可行的。

关键词：差分隐私；矩阵机制；树状数组；连续发布

1　引言

随着数字技术的发展，数据越来越多地充斥于现实生活当中。数据给人们生活带来的好处不言而喻，人们不仅可以利用数据进行评估、分析和预测，还可以从中寻找有价值的信息，如啤酒与尿布的故事。然而，在享受数据带来的好处的同时，也应该注意到数据中包含的个人隐私信息可能存在隐私泄露的风险。特别是当攻击者带有恶意时，他就有可能利用已掌握的知识分析所发布的数据，并从中挖掘出数据所对应用户的隐私信息。……