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

摘要

在如今的大数据时代，数据分析与挖掘已经成为从海量数据中提取出有用信息的一种必要技术手段。然而，目前存在的一个障碍是数据分析者可能并不完全拥有数据，甚至数据完全不在数据分析者手中。而将己方的私有信息透漏给不可信的第三方，由第三方对集中数据集进行分析与挖掘又会对数据持有者的利益造成不可预知的损害。这就会大幅度降低合作计算的可能性。幸运的是，安全多方计算技术的出现使得弥合上述看似矛盾的事实成为可能。其目的在于能够让互相不信任的各个参与方在均不泄露本身私有信息的前提下，通过合作计算来完成对整体数据集的分析与挖掘，以得到更精确的分析结果，从而实现共赢。安全两方计算是安全计算领域里的核心内容。它不仅可以直接应用于实际生活中，同时也是构建多方协议的基础。然而，到目前为止，很多安全两方计算中的关键问题尚未得到很好的解决，这也直接导致了很多数据分析与挖掘算法难以实现隐私化的目标。本文针对安全两方计算中第k小值查询这一关键问题进行深入研究，衍生出三个基本理论问题。并结合这些理论问题的解决方案，实现出三个可实际应用的隐私保护系统。本文的主要创新点列举如下:
　　1.基于安全第k小值查询这一核心问题，我们衍生出三个基础问题，分别为安全静态k-近邻查询问题、安全动态k-近邻查询问题以及安全McAfee选择问题，并给出这些问题的形式化定义。
　　2.基于给出的安全静态k-近邻查询问题的解决方案，我们设计了一个完整的隐私保护协同Web服务质量预测框架，这个框架可以有效消除个性化推荐与用户隐私信息泄露之间的矛盾性。我们通过结合同态加密以及Yao协议来完成Zheng等人所提出基础方案中算法的隐私保护实现形式，这也使得我们所提框架的预测精确性可以完全与Zheng等人方法在不考虑任何隐私信息泄露情况下一致的推荐精确性。我们通过采用FasterGC框架来实现服务质量预测协议中诸多算法的优化，使得所提出的隐私保护技术框架不仅仅具有理论意义，而且完全满足在现实生活中的应用。
　　3.我们设计垂直数据分布下的第k小值查询算法，该算法可以有效得出与查询点与数据集其他点中第k小的距离分片，而且所需的通信复杂度仅为O(n)。再利用所得的分片值分别与置换后的距离序列中每个元素做比较，我们可以得到置换后的k近邻集合，该集合的元素不会包含任何隐私信息。设计出协议来计算数据点中所有元素的k-distance值，并给出查找所有点o∈Nk(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的基础上实现了所提协议的系统，并通过衡量实际运行时间来确保所提方案的高效性。

目录

声明

摘要

表格索引

插图索引

算法索引

第一章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 本文研究内容与组织结构

1．4 本章小结

第二章 基础知识

2．1 通用协议

2．1．1 茫然传送

2．1．2 Yao协议

2．1．3 电路构建

2．2 数据分布

2．3 基础协议与相关概念

2．3．1 加法同态加密系统

2．3．2 加法秘密分享

2．3．3 安全洗牌协议

2．4 形式化安全与攻击者模型

2．5 本章小结

第三章 安全k-近邻查询

3．1 引言

3．2 垂直数据分布下的安全kNN查询

3．3 水平数据分布下的安全kNN查询

3．4 安全kNN查询问题形式化定义

3．5 已有方案的局限性

3．6 本章小节

第四章 基于k-近邻的隐私保护推荐系统

4．1 引言

4．2 协同Web服务质量预测

4．3 系统架构

4．3．1 实例

4．4 隐私保护服务质量评分值预测方法

4．4．1 相似度值计算

4．4．2 安全Top-K查询

4．4．3 服务质量预测值计算

4．5 安全性分析

4．6 实验

4．6．1 复杂度分析

4．6．2 运行时间

4．7 相关工作

4．8 本章小结

第五章 基于k-近邻的隐私保护数据挖掘

5．1 引言

5．2 问题形式化描述

5．2．1 Yao协议的应用

5．2．2 安全性要求

5．3 隐私保护LOF离群点检测协议

5．3．1 构建距离矩阵

5．3．2 安全k-NN查询协议-动态

5．3．3 查找所需的k距离值

5．3．4 安全计算LOF得分值

5．4 分析

5．4．1 安全性分析

5．4．2 计算与通信开销分析

5．4．3 扩展性分析

5．5 实验

5．6 本章小节

第六章 基于k-近邻的安全双边拍卖

6．1 引言

6．2 相关工作

6．3 问题陈述

6．3．1 McAfee双边拍卖机制

6．3．2 TRUST

6．3．3 安全双边拍卖

6．4 安全McAfee’s选择

6．4．1 数据外包

6．4．2 利用排序决策最终交易价格

6．4．3 利用选择决策交易价格

6．4．4 安全置换协议

6．5 应用

6．5．1 McAfee机制

6．5．2 TRUST

6．6 分析

6．6．1 计算复杂度分析

6．6．2 安全性分析

6．7 实验

6．8 本章小节

第七章 总结

参考文献

致谢

在读期间发表的学术论文与取得的研究成果

参加的科研项目