网络计算中的私有数据保护问题及其应用研究

论文摘要

随着网络技术的发展,网络计算已成为最主要的合作计算方式之一。但是由于网络计算的输入数据常常涉及到机密或者隐私信息,而参与其中的各方常常不是完全信任的甚至是相互竞争的关系。此时参与者仅仅希望获得最终的结果,而并不想泄漏自己的私有数据。在实际中这种参与者之间既有合作需求又互不信任的情况相当普遍,私有数据的保护问题已成为阻碍网络计算发展的最大障碍,所以怎样在网络计算中保护参与者的私有数据一直是世界研究者的重要课题。安全多方计算针对的正是这方面的需求,它由A.C.Yao于上世纪80年代首先提出,并很快受到世界研究者的重视。在多方参与的网络计算中,安全多方计算技术能够在保证各个参与者不泄漏各自私有输入信息的情况下,使各方获得期望的正确计算结果。Yao,Goldreich等人很快证明了采用基于电路构造的电路求值协议,可以获得任意此类问题的安全多方计算意义下的解。另一方面,Ben-Or、Chaum等人研究了网络计算存在恶意参与者攻击的情况下的安全计算问题,并利用零知识证明理论,给出了保证安全性的攻击者数目的上限。由于效率低下,通用的电路求值协议只具有理论意义,无法用来解决具有大量输入数据的实际问题。安全多方计算的先驱之一Goldreich指出,对特定实际问题,需要专门的应用协议以达到较高的计算性能。当前,安全多方计算已经广泛的应用到大量的实际问题领域,在包括数据挖掘、计算几何、统计分析等等在内的应用领域均采用它的理论和技术来设计安全协议,完成保护私有数据的合作计算。安全多方计算应用协议的一般设计分析过程是:首先基于安全多方计算的基础协议和通用技术进行设计技术,然后基于安全多方计算理论进行协议分析。这样安全多方计算理论可以由研究者研究完善,安全多方计算基础协议与通用技术可以由研究者和工程人员设计分析,而大量的实际的应用协议可以由一般的设计人员进行设计分析。这样层次结构大大简化了实际应用领域协议设计与分析的难度。本文首先对前人的工作进行了总结分析。第1章绪论中介绍了安全多方计算的背景知识、安全多方计算的基本思想以及当前安全多方计算理论实践的不足之处,这正是本文工作的立足点和创新点。第2章给出了安全多方计算较为详细的介绍,其中包括安全定义、参与者行为等基本概念,茫然传送、零知识系统、电路求值协议等基本理论。第2章同时介绍了安全多方计算实践,对当前协议设计中常用的基础协议和通用技术进行了总结分析,并介绍了其中几个重要的基础协议的实现技术。第3章着重介绍我们在安全多方计算理论中的研究成果。众所周知,当前的安全多方计算理论描述的是完美的安全性,在效率上的考虑不多。但是在大量的实际应用并不需要零信息泄露,只要有恰当的安全性即可,而对效率有很高的要求。此时,对效率和安全性进行折衷的“可接受的安全”更具有应用价值。本文对这个问题进行了深入的讨论,将信息泄露量作为一个参数加入到协议安全性的证明中去,提出了一系列的概念,包括偏序关系的约束、用于协议间安全性比较的信息自由量概念等。另一方面,本文提出了加乘变换这一通用协议设计技术,采用这一技术可以解决一系列的安全多方计算问题。第4章和第5章介绍了我们在计算几何方面的成果。我们首先以计算几何中的基础协议安全叉积协议实现了百万富翁协议,这是计算几何作为方法学的例子。然后我们提出了解决一般的碰撞检测问题的通用安全计算协议,并采用自适应技术和安全多方计算的理论完整解决了两圆碰撞检测问题,并对解决方案进行了分析和实验。第5章实现了保护私有信息的范围查询问题。范围查询问题是计算几何中的重要问题,有着广泛的应用背景。该问题根据结果的不同分为两类:返回的结果是满足条件的点的数目或者返回的结果是满足条件的点集。第一类问题比较复杂,我们根据不同的效率和安全性提出了两种解决方案。第二类问题相对简单,我们也进行了相应的讨论。第6章介绍了我们在聚类分析方面的成果。聚类分析方向上的工作主要集中于解决分布式情况下DBSCAN算法的私有数据保护问题。数据挖掘中多方共享数据的方式主要有垂直划分和水平划分两种形式。我们也主要对这两种情况进行分析,并实现了基于垂直划分和水平划分的保护私有信息的DBSCAN算法。我们对算法的时间复杂性和通信复杂性进行了详细的分析。其中水平划分的DBSCAN算法调用了计算几何中的范围查询算法。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景
• 1.2 安全多方计算概述
• 1.3 研究目标与研究方法
• 1.4 本文的工作
• 1.5 本文结构
• 1.6 本章小结
• 第2章 安全多方计算概述
• 2.1 安全理论基本概念
• 2.2 组合定理
• 2.3 茫然传送
• 2.4 电路求值协议简介
• 2.5 零知识证明系统
• 2.6 数据伪装技术
• 2.6.1 数据混乱
• 2.6.2 线性隐藏
• 2.6.3 Z+V隐藏
• 2.6.4 同态加密
• 2.6.5 可交换加密
• 2.6.6 公钥密码
• 2.7 基础协议
• 2.7.1 安全求和协议
• 2.7.2 安全比较协议
• 2.7.3 安全点积协议
• 2.7.4 安全置换协议
• 2.7.5 集合相关的安全协议
• 2.7.6 安全叉积协议
• 2.7.7 安全距离协议
• 2.8 协议评价标准
• 2.9 本章小结
• 第3章 有信息泄漏的安全性分析
• 3.1 传统的安全性定义
• 3.2 可接受安全
• 3.3 信息泄露理论
• 3.4 信息泄露理论应用实例
• 3.5 加乘变换
• 3.5.1 乘到加变换
• 3.5.2 加到乘变换
• 3.6 本章小结
• 第4章 私有数据保护技术在计算几何中的应用
• 4.1 计算几何概述
• 4.2 保护私有信息的计算几何
• 4.3 利用叉积协议实现百万富翁协议
• 4.3.1 叉积协议与百万富翁协议的对应关系
• 4.3.2 合适的二维点积协议
• 4.3.3 协议安全性分析
• 4.3.4 协议的实现细节
• 4.3.5 协议复杂度
• 4.4 碰撞检测问题
• 4.4.1 解决框架
• 4.4.2 安全判定两圆相交协议
• 4.4.3 获取下一个检测点的安全协议
• 4.4.4 保护私有信息的两圆碰撞检测协议
• 4.4.5 实验结果
• 4.5 本章小结
• 第5章 范围搜索问题
• 5.1 范围搜索问题定义
• 5.2 保护私有信息的欧几里得距离平方协议
• 5.3 完美安全的第一类范围搜索协议
• 5.4 有微小信息泄漏量的第一类范围搜索协议
• 5.5 保护私有信息的第二类范围搜索协议
• 5.6 本章小结
• 第6章 私有数据保护技术在聚类中的应用
• 6.1 数据挖掘简介
• 6.2 数据挖掘中的数据伪装技术
• 6.2.1 数据搅乱
• 6.2.2 数据交换
• 6.2.3 数据改写
• 6.3 数据聚类
• 6.4 基于垂直划分的DBSCAN算法
• 6.4.1 问题描述
• 6.4.2 安全求交协议
• 6.4.3 基于垂直划分的regionQuery协议
• 6.4.4 协议分析
• 6.5 基于水平划分的DBSCAN算法
• 6.5.1 解决方案
• 6.5.2 协议分析
• 6.6 本章小结
• 第7章 总结与展望
• 7.1 本文工作
• 7.2 进一步的研究方向
• 参考文献
• 致谢
• 在读期间完成的学术论文
• 在读期间参加的科研项目