安全两方计算关键技术及应用研究

发布时间：2017-09-15 19:26

  本文关键词：安全两方计算关键技术及应用研究

  更多相关文章： 安全两方计算 隐私保护 数据挖掘 频谱拍卖 安全k-近邻查询 Yao协议

【摘要】：在如今的大数据时代,数据分析与挖掘已经成为从海量数据中提取出有用信息的一种必要技术手段。然而,目前存在的一个障碍是数据分析者可能并不完全拥有数据,甚至数据完全不在数据分析者手中。而将己方的私有信息透漏给不可信的第三方,由第三方对集中数据集进行分析与挖掘又会对数据持有者的利益造成不可预知的损害。这就会大幅度降低合作计算的可能性。幸运的是,安全多方计算技术的出现使得弥合上述看似矛盾的事实成为可能。其目的在于能够让互相不信任的各个参与方在均不泄露本身私有信息的前提下,通过合作计算来完成对整体数据集的分析与挖掘,以得到更精确的分析结果,从而实现共赢。安全两方计算是安全计算领域里的核心内容。它不仅可以直接应用于实际生活中,同时也是构建多方协议的基础。然而,到目前为止,很多安全两方计算中的关键问题尚未得到很好的解决,这也直接导致了很多数据分析与挖掘算法难以实现隐私化的目标。本文针对安全两方计算中第k小值查询这一关键问题进行深入研究,衍生出三个基本理论问题。并结合这些理论问题的解决方案,实现出三个可实际应用的隐私保护系统。本文的主要创新点列举如下： 1.基于安全第k小值查询这一核心问题,我们衍生出三个基础问题,分别为安全静态k-近邻查询问题、安全动态k-近邻查询问题以及安全McAfee选择问题,并给出这些问题的形式化定义。 2.基于给出的安全静态k-近邻查询问题的解决方案,我们设计了一个完整的隐私保护协同Web服务质量预测框架,这个框架可以有效消除个性化推荐与用户隐私信息泄露之间的矛盾性。我们通过结合同态加密以及Yao协议来完成Zheng等人所提出基础方案中算法的隐私保护实现形式,这也使得我们所提框架的预测精确性可以完全与Zheng等人方法在不考虑任何隐私信息泄露情况下一致的推荐精确性。我们通过采用FasterGC框架来实现服务质量预测协议中诸多算法的优化,使得所提出的隐私保护技术框架不仅仅具有理论意义,而且完全满足在现实生活中的应用。 3.我们设计垂直数据分布下的第k小值查询算法,该算法可以有效得出与查询点与数据集其他点中第k小的距离分片,而且所需的通信复杂度仅为O(n)。再利用所得的分片值分别与置换后的距离序列中每个元素做比较,我们可以得到置换后的k近邻集合,该集合的元素不会包含任何隐私信息。设计出协议来计算数据点中所有元素的k-distance值,并给出查找所有点o∈Nκ(p)的k-distance分片值的高效方法。该类问题也是动态k近邻查询的核心问题,而且到目前为止并没有有效的解决方法。我们证明所设计的协议是在半诚实模型下是通用可组合安全的。同时还分析出,对于在具有n条数据集的数据库O上进行安全LOF查询协议,所需的通信和计算开销均为O(n2),相对于在不考虑安全情况下的分布式LOF算法运行所需的O(n2)的计算开销以及O(n)的通信开销来说,是完全可以被接受的。 4.基于Yao协议以及Batcher排序网络,我们设计出了一个安全McAfee选择问题的高效解决方案。该方案的主要开销是O(nlog2n)次的对称加密操作,其在竞拍者数量相对较小时运行效率很高。针对竞拍者数量较多的情况,我们给出了一个更高效的安全McAfee选择问题解决方案,该方案主要基于安全洗牌以及安全选择,同时将主要开销降低至O(n)次对称加密操作。基于设计出的安全McAfee选择问题解决方案,我们设计了关于McAfee拍卖机制以及TRUST这两个拍卖方案的安全协议。我们形式化证明了所提协议满足半诚实模型下安全性定义标准,并且分析了计算及通信复杂度。另外,我们在FasterGC的基础上实现了所提协议的系统,并通过衡量实际运行时间来确保所提方案的高效性。
【关键词】：安全两方计算 隐私保护 数据挖掘 频谱拍卖 安全k-近邻查询 Yao协议
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP311.13;TP309
【目录】：

• 摘要5-7
• ABSTRACT7-9
• 目录9-12
• 表格索引12-13
• 插图索引13-15
• 算法索引15-16
• 第一章 绪论16-22
• 1.1 研究背景与意义16-18
• 1.2 国内外研究现状18-19
• 1.3 本文研究内容与组织结构19-21
• 1.4 本章小结21-22
• 第二章 基础知识22-34
• 2.1 通用协议22-30
• 2.1.1 茫然传送22-23
• 2.1.2 Yao协议23-25
• 2.1.3 电路构建25-30
• 2.2 数据分布30
• 2.3 基础协议与相关概念30-33
• 2.3.1 加法同态加密系统30-32
• 2.3.2 加法秘密分享32
• 2.3.3 安全洗牌协议32-33
• 2.4 形式化安全与攻击者模型33
• 2.5 本章小结33-34
• 第三章 安全k-近邻查询34-38
• 3.1 引言34
• 3.2 垂直数据分布下的安全kNN查询34-35
• 3.3 水平数据分布下的安全kNN查询35-36
• 3.4 安全kNN查询问题形式化定义36-37
• 3.5 已有方案的局限性37
• 3.6 本章小结37-38
• 第四章 基于k-近邻的隐私保护推荐系统38-60
• 4.1 引言38-39
• 4.2 协同Web服务质量预测39-42
• 4.3 系统架构42-45
• 4.3.1 实例43-45
• 4.4 隐私保护服务质量评分值预测方法45-52
• 4.4.1 相似度值计算45-49
• 4.4.2 安全Top-K查询49-50
• 4.4.3 服务质量预测值计算50-52
• 4.5 安全性分析52-53
• 4.6 实验53-58
• 4.6.1 复杂度分析53-56
• 4.6.2 运行时间56-58
• 4.7 相关工作58-59
• 4.8 本章小结59-60
• 第五章 基于k-近邻的隐私保护数据挖掘60-76
• 5.1 引言60-62
• 5.2 问题形式化描述62-64
• 5.2.1 Yao协议的应用62-63
• 5.2.2 安全性要求63-64
• 5.3 隐私保护LOF离群点检测协议64-70
• 5.3.1 构建距离矩阵64-65
• 5.3.2 安全k-NN查询协议-动态65-66
• 5.3.3 查找所需的k距离值66-67
• 5.3.4 安全计算LOF得分值67-70
• 5.4 分析70-73
• 5.4.1 安全性分析70-72
• 5.4.2 计算与通信开销分析72
• 5.4.3 扩展性分析72-73
• 5.5 实验73-74
• 5.6 本章小节74-76
• 第六章 基于k-近邻的安全双边拍卖76-94
• 6.1 引言76-78
• 6.2 相关工作78-79
• 6.3 问题陈述79-80
• 6.3.1 McAfee双边拍卖机制79
• 6.3.2 TRUST79-80
• 6.3.3 安全双边拍卖80
• 6.4 安全McAfee’s选择80-86
• 6.4.1 数据外包80
• 6.4.2 利用排序决策最终交易价格80-82
• 6.4.3 利用选择决策交易价格82-85
• 6.4.4 安全置换协议85-86
• 6.5 应用86-87
• 6.5.1 McAfee机制86-87
• 6.5.2 TRUST87
• 6.6 分析87-90
• 6.6.1 计算复杂度分析87-88
• 6.6.2 安全性分析88-90
• 6.7 实验90-91
• 6.8 本章小节91-94
• 第七章 总结94-96
• 参考文献96-102
• 致谢102-104
• 在读期间发表的学术论文与取得的研究成果104-106
• 参加的科研项目106

【共引文献】

中国期刊全文数据库 前10条

1 ;Secure multi-party computation protocol for sequencing problem[J];Science China(Information Sciences);2011年08期

2 杨勇;;一种恶意模型下高效的两方安全计算协议[J];计算机工程与科学;2013年03期

3 姜波;张晓筱;潘伟丰;;基于二部图的服务推荐算法研究[J];华中科技大学学报(自然科学版);2013年S2期

4 林祥云;刘小青;唐明董;曹步清;刘建勋;;Web服务QoS与用户位置的相关性实证研究[J];计算机工程与科学;2013年09期

5 李桥;周莹莲;黄胜;马翔;;对随机投影算法的离群数据挖掘技术研究[J];计算机工程与应用;2013年24期

6 王学文;杨兆建;丁华;段雷;石瑞敏;李怀文;;煤矿装备云制造资源服务平台研究与应用[J];煤炭学报;2013年10期

7 陈国彬;张广泉;;基于线性规划QoS感知的Web服务组合模型[J];控制工程;2013年06期

8 高恩阳;刘伟军;王天然;;一种基于线性规划的孤立点检测方法[J];控制工程;2013年06期

9 徐彦蛟;李顺东;王道顺;吴春英;;基于椭圆曲线公钥系统的不经意传输协议[J];计算机科学;2013年12期

10 赵青松;徐焕良;;基于随机化混淆电路的委托计算[J];计算机工程;2013年12期

中国重要会议论文全文数据库 前4条

1 黄丽伟;曹景龙;吕克伟;;抵御一般混合敌手的RSA可验证签名方案[A];第26次全国计算机安全学术交流会论文集[C];2011年

2 朱洪亮;赵凯;辛阳;罗群;杨义先;;基于Schnorr体制的改进的零知识证明系统[A];2006通信理论与技术新进展——第十一届全国青年通信学术会议论文集[C];2006年

3 初佃辉;尉爱平;徐晓飞;王忠杰;;面向陆海联运的服务选择组合优化模型及算法[A];山东计算机学会2013学术年会论文集[C];2013年

4 杨彦武;;信息服务发展研究[A];2010-2011控制科学与工程学科发展报告[C];2011年

中国博士学位论文全文数据库 前10条

1 杨勇;基于身份密码体制的若干安全性问题研究[D];山东大学;2011年

2 秦波;基于对的群体密码学研究[D];西安电子科技大学;2008年

3 荆巍巍;安全多方计算中若干基础协议及应用的研究[D];中国科学技术大学;2008年

4 张京良;可追踪匿名签名及在电子商务中的应用[D];西安电子科技大学;2008年

5 刘文;几类特殊的安全多方计算问题的研究[D];北京邮电大学;2009年

6 马敏耀;安全多方计算及其扩展问题的研究[D];北京邮电大学;2010年

7 郑强;不同模型下若干安全多方计算问题的研究[D];北京邮电大学;2010年

8 赵洋;安全多方计算及其应用协议研究[D];电子科技大学;2009年

9 蓝天;安全的分布式电子商务交易模式研究[D];电子科技大学;2009年

10 曾兵;一个抗隐蔽敌手的n选t不经意传输框架[D];华中科技大学;2012年

中国硕士学位论文全文数据库 前10条

1 袁先平;若干数据库的安全查询协议研究[D];安徽大学;2011年

2 廖卫民;口令认证密钥交换新协议[D];广州大学;2006年

3 杨方圆;安全多方计算的研究[D];山东大学;2007年

4 董涛;安全多方计算的应用研究[D];解放军信息工程大学;2007年

5 张雪征;安全多方计算协议的研究与应用[D];西华大学;2008年

6 王小妹;安全多方计算的协议研究[D];北京邮电大学;2008年

7 浦明松;基于RSA分布式计算的安全多方计算协议研究[D];北京邮电大学;2008年

8 黄丽伟;[D];首都师范大学;2008年

9 邱梅;安全多方排序协议的研究[D];北京邮电大学;2009年

10 廖干才;若干离散问题的安全多方计算协议研究[D];北京邮电大学;2009年

，

本文编号：858438