摘 要

安全多方计算一直以来都是信息安全的一个重要研究领域。主要研究多方合作计算问题，即分布式网络中涉及多个参与者协作进行计算，并且保证输入信息的私密性。随着互联网的发展，越来越多的信息在网络中流动。网络信息的安全成为人们关注的热点问题，安全多方计算也显得越来越重要。我们从两方面对安全多方计算进行研究。一方面，研究安全多方计算的一些基本概念和两方比较的百万富翁协议，并基于这个协议研究设计了安全多方排序方案。另一方面，研究了安全多方排序的一个实际应用，即电子拍卖采购方最佳决策问题。

隐私保护网络数据排序是分布式网络中的若干个参与者共同参与计算，以得到参与者之间的排序关系，并且不泄露参与者的任何私有信息。这是安全多方计算中的安全多方排序问题。安全多方排序在很多实际应用中都体现了其重要性，是安全多方计算一个非常值得研究的领域。

本文研究了安全多方排序问题，主要工作体现在以下两方面：

一方面，详细介绍了安全多方排序的背景，总结了目前的研究现状。描述了一个安全两方比较方案，然后从这个方案推广到安全多方排序，并加以分析。

另一方面，研究了多属性拍卖模型。通过对已有的多属性拍卖模型的研究，提出了一个简单的符合实际情况的多属性采购模型。基于这个模型，我们通过安全多方排序方案提出了采购方最佳决策。然后，我们进行了协议的设计，并理论分析了该方案的正确性、安全性和实用性。

关键词：安全多方计算；隐私保护；排序；同态加密；电子拍卖

Abstract

Secure multi-party computation has always been an important research area of information security. It mainly studies the multi-party computation problems, that is, multiple participants in the distributed network perform cooperative calculations and ensure the privacy of the input information. With the development of the Internet, more and more information spread in the network. The security of network information has become a primary concern. And secure multi-party computation is also becoming more and more important. We study the secure multi-party computation from two aspects. One, study some basic concepts of secure multi-party computation and millionaire agreement, and then design a secure multi-party sorting solution based on the agreement. The other, study a practical application of secure multi-party sorting, that is, the best decision of the purchaser in electronic auction.

Privacy-preserving network data sorting is that multiple participants in a distributed network perform cooperative calculations to get the sorting relationship among the participants and not reveal any private information from the participants. This is a secure multi-party sorting problem in secure multi-party computation. Many applications reflect the importance of secure multi-party sorting. It is an important research area.

This thesis studies the secure multi-party sorting problems, the main contribution is reflected in the following two aspects:

Firstly, this thesis introduces the background of safe multi-party sorting and summarizes the current research status. Describes a secure two-party comparison scheme, and then extends from this program to secure multi-party sorting and analyzes it.

Secondly, this thesis studies the multi-attribute auction model. Based on the research of the existing multi - attribute auction model, a simple multi - attribute purchasing model is put forward according to the actual situation. Based on this model, the best decision of the purchaser is proposed through our secure multi-party sorting scheme. Then we have the design of the agreement, and theoretically analyzed the correctness, security and practicability of the scheme.

Keywords: Secure Multi-party Computation; Privacy Protection; Sorting; Homomorphic Encryption; Electronic Auction

目录

第一章 绪论 1

1.1研究背景及现状 1

1.2本文的研究内容 1

1.3本文结构安排 2

第二章 相关概念和定义 3

2.1安全多方计算简介 3

2.2安全性的定义 3

2.2.1计算不可区分 3

2.2.2敌手模型 3

2.3加同态加密体制 5

第三章 基于隐私保护的排序方案 6

3.1安全两方排序 6

3.1.1问题背景和现状 6

3.1.2基于Paillier加密体制的比较协议 6

3.2推广的安全多方排序 7

3.2.1问题定义 7

3.2.2协议设计 8

3.2.3协议分析 9

第四章 多属性拍卖模型 10

4.1电子拍卖模型背景和现状 10

4.2多属性电子拍卖模型 10

第五章 采购方最佳决策 12

5.1多属性采购拍卖模型 12

5.2采购方最佳决策 12

5.3采购方最佳决策协议 13

5.4协议分析 17

5.4.1正确性分析 17

5.4.2安全性分析 18

5.4.3实用性分析 19

第六章 总结和展望 21

6.1总结 21

6.2展望 21

参考文献 22

致谢 23

第一章 绪论

1.1研究背景及现状

分布式网络的壮大为合作计算奠定了基础，社会中独立存在的个体认识到协作计算将会带来更大的利益。不同的单位和组织之间的合作日益增长，在如今的社会中，合作计算成为常态。在合作计算中，参与方携带不同的数据，通过数据的整合分析，得到了更有价值的数据信息。目前，大多数合作计算都是透明的，要么是计算中的参与方之间共享这些数据，要么是通过第三方对合作计算进行代理。所以第三方往往能得到参与者的数据。假如参与方不信任任何人，不想共享这些私有数据，也不想告知第三方。合作计算中的信息私密性成为难点。安全多方计算的出现为解决这些问题提供了很好的思路。安全多方计算是参与计算的各方按照一定的规则和协议提供自己的数据进行计算，计算过程结束后能得到正确的结果，并且除了结果本身以外，不泄露参与者的任何信息。因此，安全多方计算保证了计算中信息的私密性。安全多方计算在各个领域都有着十分广泛的应用。比如在信息复杂的商业领域和信息高度敏感的军事领域。不管在那个领域，在信息的处理和交融上，总会存在对数据的比较和排序进行操作。如今，随着互联网的发展，每个单位或组织都有自己的数据中心，从分布式网络看，它们分布在不同的客户端。如何对分布在不同客户端或服务器上的数据进行大小比较和排序依然是一个难点。目前，已经有一些方案解决类似这样的问题，大多数为了效率忽略了隐私的保护。在信息高度敏感时代，急需新的方案来解决隐私保护问题。我们的研究就是要解决这样的问题，在处理网络数据上，提出了基于隐私保护的排序方案。

排序问题可以划分为两个数的排序和多个数的排序两类。两个数的排序是多个数排序的特殊情况。通过分析两个数的排序拓展到多个数的排序被认为是理所当然的，也是正确的。我们的研究也是从两个数的排序开始，然后拓展到多个数的排序。当然，我们的研究并不仅仅是在理论上，我们还将多方排序算法应用到电子拍卖领域上，以此来证明我们的方案具有实用性。通过研究现有的电子拍卖模型，提出一个新的简单的更符合实际情况的采购方多属性拍卖模型。基于该模型，为采购方提出一个最佳决策，即从投标人中选择最优者，并保证在决策过程中不泄露采购方和投标人的任何信息。

1.2本文的研究内容

本文的研究内容是隐私保护下的排序问题，通过研究这样的问题提出一个基于隐私保护的排序方案，但我们的研究并不仅仅是在理论上，还将多方排序算法应用到电子拍卖领域上，以此来证明我们的方案具有实用性。通过研究现有的电子拍卖模型，提出一个新的简单的更符合实际情况的采购方多属性拍卖模型。基于该模型，为采购方提出一个最佳决策，即从投标人中选择最优者，并保证在决策过程中不泄露采购方和投标人的任何信息。

1.3本文结构安排

本文主要对隐私保护下的网络数据排序进行研究，分七个章节进行阐述，各章组织如下：