若干多方保密计算问题的研究

论文摘要

多方保密计算又称安全多方计算或者多方安全计算,是一个涉及计算理论、密码学、分布式系统、数论、近世代数等学科的综合性研究领域,其丰富的理论研究内容和广泛的实际应用前景使它一诞生便引起了众多研究人员的密切关注。自1982年姚期智教授提出了公认的第一个多方保密计算问题——百万富翁问题之后,经过一系列的研究和发展,多方保密计算已经成为了密码学领域里一个内涵丰富的基础性研究课题,无论是关于其底层基础理论还是现实应用的研究都方兴未艾。在一般的多方保密计算协议中,共同参与计算的两方或多方联合执行一个特殊的函数f(x1,x2,...,xn)=(f1(x1,x2,...,xn),...,fu(x1,x2,...,xn),在不泄漏每一个参与者自己的私有输入xi的同时,分别得到各自的输出yi=f1(x1,x2,...,xn)。在多数多方保密计算问题中,每一个yi都是相等的,比如三方或以上共同计算参与方的平均数；在另一些多方保密计算问题中,参与者得到的输出yi可能并不完全相同,比如点积协议。本文主要对两类多方保密计算问题进行了研究,即隐私保护的数据挖掘问题和保密的计算几何问题。除此之外,在研究这两类问题的过程中,提出了一些新的多方保密计算协议构造模块,并对某些已有模块的效率进行了提升。总的来说,本文的创新之处体现在如下方面：·对于需要进行联合数据挖掘的参与者,提出了一个在数据预处理阶段对数据项进行变换的算法。通过该算法对数据处理后,使得数据提供方既能够得到想要的结果,又能够保证一些不想被数据挖掘执行者得到的规则的安全性。·提出了一个高效的保密地判断点与直线位置关系的协议并给出了严格的安全性证明。将该协议扩展后可用于保密地判断点与部分特殊曲线的位置关系,这些特殊曲线包括多项式函数曲线和指数函数曲线等。·改进了一些多方保密计算构造模块的效率,如标量积协议和保密比较功议。这些基础的构造模块的改进对提升其他更加复杂的多方保密计算协议的性能有很大的帮助。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 研究背景和研究意义
• 1.2 相关工作
• 1.3 本文的主要内容和结论
• 1.4 本文的组织结构
• 第2章 预备工作
• 2.1 基本定义
• 2.2 基本的构造模块
• 第3章 保密的数据挖掘
• 3.1 概念和问题引入
• 3.2 准备工作
• 3.2.1 基本定义
• 3.2.2 安全性定义
• 3.2.3 两个重要事实
• 3.3 算法过程
• 3.4 分析和证明
• 3.4.1 算法分析
• 3.4.2 算法证明
• 3.5 本章小结
• 第4章 隐私保护的计算几何
• 4.1 简介和问题的引入
• 4.2 基本定义和构造模块
• 4.3 保密判定点线位置关系的协议
• 4.3.1 初始分析
• 4.3.2 协议过程
• 4.3.3 分析和证明
• 4.4 协议的推广
• x时的情形'>4.4.1 指数函数f（x）=e^x时的情形
• 4.4.2 其他函数时的情形
• 4.5 协议的分析和比较
• 4.6 本章小结
• 第5章 总结与展望
• 参考文献
• 致谢
• 攻读硕士学位期间的研究成果