在如今的大数据时代,数据分析与挖掘已经成为从海量数据中提取出有用信息的一种必要技术手段。然而,目前存在的一个障碍是数据分析者可能并不完全拥有数据,甚至数据完全不在数据分析者手中。而将己方的私有信息透漏给不可信的第三方,由第三方对集中数据集进行分析与挖掘又会对数据持有者的利益造成不可预知的损害。这就会大幅度降低合作计算的可能性。幸运的是,安全多方计算技术的出现使得弥合上述看似矛盾的事实成为可能。其目的在于能够让互相不信任的各个参与方在均不泄露本身私有信息的前提下,通过合作计算来完成对整体数据集的分析与挖掘,以得到更精确的分析结果,从而实现共赢。安全两方计算是安全计算领域里的核心内容。它不仅可以直接应用于实际生活中,同时也是构建多方协议的基础。然而,到目前为止,很多安全两方计算中的关键问题尚未得到很好的解决,这也直接导致了很多数据分析与挖掘算法难以实现隐私化的目标。本文针对安全两方计算中第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的基础上实现了所提协议的系统,并通过衡量实际运行时间来确保所提方案的高效性。