一种基于随机投影的本地差分隐私高维数值型数据收集算法

doi:10.11959/j.issn.2096-0271.2020001

大数据 ›› 2020, Vol. 6 ›› Issue (1): 3-11.doi: 10.11959/j.issn.2096-0271.2020001

• 专题：大数据隐私保护 • 上一篇下一篇

一种基于随机投影的本地差分隐私高维数值型数据收集算法

孙慧中,杨健宇,程祥,苏森

北京邮电大学网络与交换技术国家重点实验室，北京 100876

出版日期:2020-01-15 发布日期:2020-02-21
作者简介:孙慧中（1998- ），女，北京邮电大学网络与交换技术国家重点实验室硕士生，主要研究方向为隐私保护和机器学习|杨健宇（1994- ），男，北京邮电大学网络与交换技术国家重点实验室博士生，主要研究方向为隐私保护|程祥（1984- ），男，北京邮电大学副教授、博士生导师，主要研究方向为数据挖掘、知识工程、隐私保护等。其研究成果已发表在包括IEEE ICDE、IEEE ICDM、AAAI、IJCAI、EMNLP、IEEE TKDE、IEEE TDSC、IEEE TSC等在内的国际会议和期刊上。主持与大数据隐私保护相关的国家自然科学基金青年科学基金项目1项、国家自然科学基金项目面上项目1项，并作为科研骨干参与多项国家级和部级科研项目|苏森（1971- ），男，北京邮电大学教授，计算机学院执行院长，中国计算机学会理事，服务计算专业委员会秘书长，“数字中国产业发展联盟”副理事长。2005年入选教育部“新世纪优秀人才支持计划”，2017年入选国家“万人计划”科技创新领军人才。目前主要研究方向为智能数据服务、数据隐私保护、社交网络分析。获国家科技进步奖二等奖1次，中国通信学会科技进步奖一等奖1次，教育部科技进步奖二等奖1次
基金资助:
国家自然科学基金资助项目(61872045)

A high-dimensional numeric data collection algorithm for local difference privacy based on random projection

Huizhong SUN,Jianyu YANG,Xiang CHENG,Sen SU

State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China

Online:2020-01-15 Published:2020-02-21
Supported by:
The National Natural Science Foundation of China(61872045)

摘要/Abstract

摘要：

对满足本地差分隐私的高维数值型数据收集问题进行了研究。设计了一种基于随机投影技术的满足本地差分隐私的高维数值型数据收集算法Multi-RPHM，在满足本地差分隐私的条件下，该算法处理维度较高的数据时能够保证所收集的数据的高效用。从理论上证明了该算法满足ε-本地差分隐私的要求。在合成数据集上进行的实验结果验证了该算法的有效性。

关键词: 高维数值型数据, 隐私保护, 本地差分隐私, 随机投影

Abstract:

The problem of high-dimensional data collection satisfying local differential privacy was studied.A new locally differentially private algorithm called Multi-RPHM was proposed based on the random projection technology,which achieved the high utility of the collected high-dimensional numeric data while satisfying the local differential privacy.The algorithm was formally proved to meet ε-local differential privacy.The effectiveness of the algorithm was comfirmed through experiments on synthetic datasets.

Key words: high-dimensional numeric data, privacy protection, local differential privacy, random projection

中图分类号:

TP309

孙慧中, 杨健宇, 程祥, 苏森. 一种基于随机投影的本地差分隐私高维数值型数据收集算法[J]. 大数据, 2020, 6(1): 3-11.

Huizhong SUN, Jianyu YANG, Xiang CHENG, Sen SU. A high-dimensional numeric data collection algorithm for local difference privacy based on random projection[J]. Big Data Research, 2020, 6(1): 3-11.

图/表 5

表1

图1?

图2

图3

图4

参考文献 17

[1]	DWORK C , . Differential p rivacy[C]// ICALP,July 10-14,2006,Venice,Italy. Heidelberg:Springer, 2006: 1-12.
[2]	DWORK C , MCSHERRY F , NISSIM K ,et al. Calibrating noise to sensitivity in private data analysis[C]// TCC,March 4-7,2006,New York,USA. Heidelberg:Springer, 2006: 265-284.
[3]	DWORK C , . Differential privacy:a survey of results[C]// TAMC,April 25-29,2008,Xi’an,China. Heidelberg:Springer, 2008: 1-19.
[4]	SWEENY L . K-anonymity:a model for protecting privacy[J]. International Journal on Uncertainty,Fuzziness and Knowledge Based Systems, 2012,10(5): 557-570.
[5]	MACHANAVAJJHALA A , KIFER D , GEHRKE J ,et al. L-diversity:privacy beyond K-anonymity[J]. ACM Transactions on Knowledge Discovery from Data, 2007,1(1):24.
[6]	KASIVISWANATHAN P S , LEEHK , NISSIM K ,et al. What can we learn privately[C]// FOCS,October 25-28,2008,Philadelphia,USA. Piscataway:IEEE Press, 2008: 531-540.
[7]	叶青青, 孟小峰, 朱敏杰 ,等. 本地化差分隐私研究综述[J]. 软件学报, 2018,29(7): 1981-2005.
	YE Q Q , MENG X F , ZHU M J ,et al. Survey on local differential privacy[J]. Journal of Software, 2018,29(7): 1981-2005.
[8]	ERLINGSSON ú , PIHUR V , KOROLOVA A . RAPPOR:randomized aggregatable privacypreserving ordinal response[C]// CCS,November 3-7,2014,Scottsdale,USA. New York:ACM Press, 2014: 1054-1067.
[9]	KAIROUZ P , BONAWITZ K , RAMAGE D . Discrete distribution estimation under local privacy[J]. Proceedings on Privacy Enhancing Technologies, 2016: 84-104.
[10]	BASSILY R , SMITH A . Local,private,efficient protocols for succinct histograms[C]// STOC,June 14-17,2015,Portland,USA. New York:ACM Press, 2015: 127-135.
[11]	WARNER S L . Randomized response:a survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965,60(309): 63-69.
[12]	NGUYêN T T , XIAO X K , YANG Y ,et al. Collecting and analyzing data from smart device users with local differential privacy[J]. Computer Science, 2016,arXiv:1606.05053
[13]	QIN Z , YANG Y , YU T ,et al. Heavy hitter estimation over set-valued data with local differential privacy[C]// CCS,October 24-28,2016,Vienna,Austria. New York:ACM Press, 2016: 192-203.
[14]	WANG N , XIAO X K , YANG Y ,et al. Collecting and analyzing multidimensional data with local differential privacy[C]// ICDE,April 8-11,2019,Macao,China. Piscataway:IEEE Press, 2019: 638-649.
[15]	DUCHI J C , WAINWRIGHT M J , JORDAN M I ,et al. Minimax optimal procedures for locally private estimation[J]. American Statistical Association, 2018,113(521): 182-201.
[16]	MCSHERRY F , . Privacy integrated queries:an extensible platform for privacy preserving data analysis[C]// SIGMOD,June 29-July 2,2009,Providence,USA. New York:ACM Press, 2009: 19-30.
[17]	JOHNSON W B , LINDENSTRAUSS J . Extensions of Lipschitz mappings into a Hilbert space[J]. Contemporary Mathematics, 1984,26(189-206):1.

符号	说明
A	属性集合
d	A中的属性个数
A_j	第j个属性
n	用户的数量
u_i	第i个用户
t_i	u_i的元组
t_i[A_j]	t_i中A_j的取值
z[A_j]	A_j的真实均值
z^*[A_j]	A_j的估计均值
x_i	u_i的低维数据元组
R_d×q	投影维度为q的投影矩阵

一种基于随机投影的本地差分隐私高维数值型数据收集算法

A high-dimensional numeric data collection algorithm for local difference privacy based on random projection

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 17

相关文章 15

Metrics

推荐阅读 0

[1]	张传尧, 司世景, 王健宗, 肖京. 联邦元学习综述[J]. 大数据, 2023, 9(2): 122-146.
[2]	吴建汉, 司世景, 王健宗, 肖京. 联邦学习攻击与防御综述[J]. 大数据, 2022, 8(5): 12-32.
[3]	阮雯强, 徐铭辛, 涂新宇, 宋鲁杉, 韩伟力. 数据租赁——数据流通的新方式[J]. 大数据, 2022, 8(5): 3-11.
[4]	李懿, 王劲松, 张洪玮. 基于区块链与函数加密的隐私数据安全共享模型研究[J]. 大数据, 2022, 8(5): 33-44.
[5]	朱智韬, 司世景, 王健宗, 肖京. 联邦推荐系统综述[J]. 大数据, 2022, 8(4): 105-132.
[6]	王健宗, 孔令炜, 黄章成, 陈霖捷, 刘懿, 卢春曦, 肖京. 联邦学习隐私保护研究进展[J]. 大数据, 2021, 7(3): 130-149.
[7]	乐洁玉, 罗超洋, 丁静姝, 李卿. 教育大数据隐私保护机制与技术研究[J]. 大数据, 2020, 6(6): 52-63.
[8]	汪靖伟, 郑臻哲, 吴帆, 陈贵海. 基于区块链的数据市场[J]. 大数据, 2020, 6(3): 21-35.
[9]	王平, 张玉书, 何兴, 仲盛. 基于安全压缩感知的大数据隐私保护[J]. 大数据, 2020, 6(1): 12-22.
[10]	卢文雄, 王浩宇. 基于同源策略的移动应用细粒度隐私保护技术[J]. 大数据, 2020, 6(1): 23-34.
[11]	王智慧, 周旭晨, 朱云. 数据自治开放模式下的隐私保护[J]. 大数据, 2018, 4(2): 42-49.
[12]	祝烈煌, 董慧, 沈蒙. 区块链交易数据隐私保护机制[J]. 大数据, 2018, 4(1): 46-56.
[13]	李康, 孙毅, 张珺, 李军, 周继华, 李忠诚. 零知识证明应用到区块链中的技术挑战[J]. 大数据, 2018, 4(1): 57-65.
[14]	李树栋, 贾焰, 吴晓波, 李爱平, 杨小东, 赵大伟. 从全生命周期管理角度看大数据安全技术研究[J]. 大数据, 2017, 3(5): 3-19.
[15]	李海英. 大数据的法律挑战和建议[J]. 大数据, 2016, 2(2): 100-107.