保护私有数据的合作计算问题及其应用研究

摘要

网络技术的不断进步使得网络中的合作计算也不断地向前发展，用户通过在网络环境中交互信息并且完成一些复杂函数的计算变得越来越普遍。然而，参与合作计算的用户数据常常属于个人私有信息或者涉密信息，因此信息保护问题一直是制约网络合作计算重要问题。让用户共享自己的私有信息参与合作计算并且保护其私有信息不泄露成为了众多研究者的重要研究目标。1982年，A.C.Yao首先提出了安全多方计算的概念，就是针对保护私有信息的合作计算问题而做的最早的研究，一直以来都引起了众多研究者的高度重视，并继承和发展了众多的安全多方计算理论与应用方面的研究。
　　 安全多方计算主要是研究两个或者多个用户在提供各自私有数据信息参与联合计算某一个函数的同时保证各自私有数据的安全性。一个安全多方计算协议能够经得住无限计算能力的攻击而仍然能保证数据安全，那么就称为信息论安全的；而一个安全多方计算协议如果能经得住多项式计算能力的攻击，则称之为密码学安全的。A.C.Yao在1982年给出了一个使用密码学方式来实现的两方计算的安全协议，求解百万富翁问题。S.Goldwasser等人1985年首次提出了零知识证明系统，将安全多方计算模型简化为只需研究半诚实模型下的安全协议，恶意模型下的安全协议可以通过零知识证明系统从半诚实模型转化得到。MO.Rabin在1981年提出茫然传送协议，由J．Kilian于1988年将其应用到了安全多方计算的协议设计中。0.Goldreich等人1987年将A.C.Yao的理论推广到多方参与的安全计算范围，并提出了密码学安全的可以计算任意函数的安全协议。M.Ben-Or等人在1988年得出了与D.Chaum等人类似的理论研究结果，即在信息论安全模型中，被动攻击情况下当串通攻击者的数目小于一半时(t＜n/2）或者主动攻击情况下攻击者的数目小于1/3时(t＜n/3)，任意函数都可以被安全的计算。Goldreich于1998年将前人研究成果进行总结，从而形成了比较完整的安全多方计算的理论体系。
　　 安全多方计算在很多情况下都有着重要应用，尤其在涉密领域，包括军事、商业等领域，有着不可替代的地位。例如多个国家之间的联合防御中需要保密计算防御区域交叉情况、相互竞争的商家共同开发商业区域时的商业网点的布局等。
　　 本文对前人的研究进行了总结分析。第1章绪论中介绍了安全多方计算的研究背景和研究现状，通过对前人研究的概述，给出了本文的研究内容安排。同时也给出了本文的结构框架。
　　 第2章从安全多方计算的定义、理论以及应用等方面介绍了安全多方计算的发展和出现的问题。提出了一般安全协议设计的流程和思想路线，比较系统的介绍了安全多方计算的基础协议，并给出了相关协议的实现思想。为了后续章节中安全协议的规范化，给出了本文中设计协议时用到的表示符号。
　　 第3章研究了点与凸包的静态与动态两种情况下的包含判定问题。首先给出了点与直线相对位置判定协议，能够判断出点在直线的哪一侧。然后考虑在安全性和计算效率方面的折中，适当的泄露一部分点的方位信息换取计算效率的大幅度提升。将动态判定问题引入到此协议中，给出了根据速度变化动态调整检测包含关系的时间间隔协议，能够及时的检测出点与凸包的平行运动中的包含关系。接着研究了凸包旋转运动的状态下，检测点与凸包包含关系的判定协议。本章的研究使得点与凸包包含判定协议更加具有实用性。
　　 第4章研究了凸包构造问题。首先将两方叉积运算拓展为任意三方参与的三点位置关系判定协议。在此协议基础上，构建出了任意多方联合构建凸包的凸包安全构造协议。此协议可以很好的适应点和参与者动态变化情况。当某一参与方加入计算，只需要将其本地凸包的点加入计算即可判定自己哪些点是最终凸包的点。当某一些点增加进来或者被删除，只需要将点与其他点进行叉积即可判定点是否构成最终凸包的点。因此，本文的凸包构建协议具有很好的灵活性。
　　 第5章研究了两圆相交交点共享问题。例如在科学计算结果的分析中需要联合分析各自私有实验结果，确定实验结果的边界条件等信息。两个圆可以看做实验结果豹范围，每一个用户获取一个且仅获取一个交点。本文中基于二分迭代算法的思想，将交点的求解转化为求相交的近似值，即数值解。调用的子协议保证了协议执行过程中任何一方都不能根据中间结果和最终结果推断另一方的相对位置，哪怕是方位信息也不会泄露。
　　 第6章研究了保护隐私的个性化推荐协议。本章中首先设计了一个具有反馈自调节功能的二部图网络（即Heat Conduction算法和Mass Diffusion算法），将每一条连接边看作一条导线将二部图的两边（用户和产品）进行连接。在资源值传递的过程中，我们使得导线具有传输阻尼，这反应了产品对用户的推荐能力。然后将安全多方计算协议构建到推荐模型中，使得在用户和产品侧的资源值保密的前提下给出推荐列表。通过分析可以发现，在多个数据库联合推荐过程中，此协议同样适用。这就很好的拓展了保护隐私的个性化推荐算法，使得多个互相竞争的商家为用户提供更好的使用体验，同时不泄露各自的私有信息，达到多方共赢的效果。

目录

声明

摘要

第1章 绪论

1.1 研究背景

1.2 安全多方计算概述

1.3 研究现状概述

1.4 本文的工作

1.5 本文的组织结构

1.6 本章小结

第2章 安全多方计算基础知识介绍

2.1 安全多方计算的定义

2.2 安全多方计算的模型

2.3 安全多方计算参与方

2.3.1 半诚实模型与恶意模型

2.3.2 不可信第三方

2.4 协议安全性相关知识介绍

2.4.1 协议安全性定义

2.4.2 密码学安全与信息论安全

2.4.3 可忽略函数

2.4.4 统计不可区分性

2.4.5 计算不可区分性

2.4.6 安全协议组合定理

2.4.7 零知识证明系统

2.5 同态加密方案介绍

2.5.1 同态加密方案

2.5.2 ElGamal加密算法

2.5.3 Paillier加密算法

2.6 安全多方计算基础协议介绍

2.6.1 电路求值协议

2.6.2 安全比较协议

2.6.3 安全求和协议

2.6.4 安全叉积协议

2.6.5 安全点积协议

2.6.6 安全置换协议

2.6.7 安全距离协议

2.6.8 向量支配协议

2.6.9 茫然传送协议

2.6.10 乘到加变换

2.6.11 加到乘变换

2.7 安全多方计算协议分析方法

2.7.1 正确性分析

2.7.2 安全性分析

2.7.3 计算复杂度分析

2.7.4 通信复杂度分析

2.7.5 轮复杂度分析

2.8 安全协议构建中的若干符号定义

2.9 本章小结

第3章 安全多方计算判定问题研究

3.1 点与凸包包含判定问题简介

3.2 构建安全点线相对位置判定协议

3.3 构建安全点与凸包包含判定协议

3.3.1 数据的初始化工作

3.3.2 构建点包含判定的基本协议

3.4 改进的点与凸包包含判定协议

3.4.1 构建改进的点与凸包包含判定协议

3.4.2 对协议IPCIP的修正

3.5 动态点包含判定问题研究

3.5.1 相向直线运动下的动态包含判定问题

3.5.2 一般直线运动状态下的包含问题分析

3.5.3 凸包旋转状态下的点包含判定问题

3.6 本章小结

第4章 安全多方计算凸包生成问题研究

4.1 安全凸包构造问题简介

4.2 构建任意三方三点相对位置判定的安全协议

4.2.1 三点属于同一个参与方

4.2.2 三点属于两方参与方

4.2.3 三点来自于三个不同的参与方昀点的相对位置判定

4.3 任意多方虚拟凸包构造协议

4.3.1 协议构造

4.3.2 一种更优的基于叉积的任意多方安全凸包构造协议

4.4 实际应用中的动态点和凸包点信息隐藏

4.4.1 动态点情况

4.4.2 顶点信息的隐藏

4.5 本章小结

第5章 安全多方计算相交问题研究

5.1 安全多方计算相交问题简介

5.2 线段相交问题研究情况

5.3 凸包相交问题研究情况

5.4 两圆相交面积研究情况

5.5 两圆相交交点的确定

5.5.1 构建两圆交点协议所需基础协议介绍

5.5.2 构建两圆交点安全计算协议

5.5.3 模拟实验

5.6 本章小结

第6章 安全多方计算在个性化推荐算法中的应用

6.1 个性化推荐系统简介

6.2 保护私有信息的协同过滤推荐算法

6.2.1 协同过滤算法

6.2.2 保护隐私的协同过滤算法介绍

6.3 用户-产品二部图推荐算法

6.4 保护隐私的用户-产品二部图推荐算法

6.5 对于数据库联合推荐算法的安全协议设计

6.6 本章小结

第7章 总结与展望

7.1 本文工作

7.2 进一步的研究方向

参考文献

致谢

攻读学位期间发表的学术论文

参加项目及获奖情况