安全多方计算问题及其应用：一个审查和开放的问题外文翻译资料

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

安全多方计算问题及其应用：一个审查和开放的问题

Wenliang Du，Mikhail J. Atallah

摘要

互联网的发展为合作计算带来了巨大的机会，人们正在根据他们提供的私有资源共同进行计算任务。 这些计算可以发生在相互不信任的参与方之间，或者甚至在竞争者之间。 例如，客户可能访问远程数据库查询私人信息 ；两个相互竞争的金融组织可能共同参与一个必须满足两个组织的私人和有价值约束的项目，等等。 今天，为了进行这样的计算，一个实体通常必须知道来自所有参与者的输入; 不过，如果知道所有的输入的人不值得信任，隐私将成为主要关注点。

这个问题在文献中被称为安全多方计算问题（SMC）。 SMC领域的研究一直专注于一组有限的特定SMC问题，而在各个计算领域中，涉及隐私的协作计算需要进行SMC研究。 在我们研究问题之前，我们需要识别和定义这些计算域中特定的SMC问题。 我们已经开发了一个框架来解决问题探索这项任务。 基于我们的框架，我们已经在一系列计算域中识别和定义了许多新的SMC问题。 这些问题包括隐私保护数据库查询，隐私保护科学计算，隐私保持入侵检测，隐私保留统计分析，隐私保留几何计算和隐私保护数据挖掘。

本文的目的不仅是呈现我们的结果，而且作为一个指南，其他人可以在自己的计算领域中识别有用的SMC问题。

关键词

隐私，安全多方计算。

1.引言

互联网的爆发为合作计算带来了巨大的机会，人们正在相互合作，根据他们提供的输入来进行计算。 这些计算可以发生在可信合作伙伴之间，部分信任的合作伙伴之间，或甚至在竞争者之间。 例如，客户可能访问远程数据库查询私人信息 ，两个竞争的金融组织可能共同投资一个必须满足两个组织的私人和有价值约束的项目，等等。 通常，为了进行这些计算，必须知道所有参与者的输入; 不过，如果知道所有的输入的人不值得信任，隐私将成为主要关注点。 例如，考虑以下应用程序：

1.Alice认为她可能有遗传疾病，她想自己调查。 她知道Bob有一个数据库包含各种疾病的DNA模型。 Alice获取她的DNA序列样本后，她将其发送给Bob，然后Bob会告诉Alice的诊断结果。 可是，如果Alice关心她的隐私，上述过程是不可接受的，它不能防止止Bob知道Alice的隐私信息 - DNA和查询结果。

2.经过昂贵的市场调查，A公司决定扩大在某些地区的市场份额，这是非常有益的。 然而，A知道另一家竞争公司B也计划在一些地区扩大其市场份额。 在战略上，A和B不想在同一区域中相互竞争，因此他们想知道他们的区域是否重叠，但没有给出位置信息（公开这些信息不仅会使两家公司花费大量资金，而且如果向其他方披露，也会对公司造成重大损失，例如，另一个更强的竞争对手可以在A或B开始之前立即占据市场；如果知道A或B对该位置非常感兴趣，一些房地产公司会提高价位）。 因此，他们需要一种方法来解决这类问题，同时保护他们的隐私。

3. 为双方的利益，两个金融组织计划合作开展一个项目。 每个组织都希望能满足自己的需求（通常，这些需求被建模为线性方程或线性不等式）。 他们的需求是私有数据，包括客户的某些商品价格，利率和通货膨胀率，经济统计，投资组合持有的未来发展的项目。 因此，没有人愿意将其需求披露给另一方，甚至向“受信任”的第三方披露。 他们如何在这个项目上合作，同时保护个人隐私信息？

上述三个例子的共同特性如下：两个或多个参与方希望基于他们的私有输入进行计算，但是任何一方都不愿意向其他任何人公开自己的输入。 问题是如何进行这样的计算，同时保护隐私。 这个问题在文献[39]中被称为安全多方计算问题（SMC）。一般来说，安全多方计算问题涉及在分布式网络中的任何输入上进行计算的函数，其中每个参与者持有输入中的一个输入，确保输入的独立性，计算的正确性，并且从该参与者的输入和输出推断[18]，没有更多的信息暴露给计算中的其他参与者。

目前，为了解决上述问题，通常的策略是假设服务提供商可信，或假定存在可信第三方，不过，在如今的恶意环境中是有风险的。因此，支持联合计算同时又保护参与者隐私的协议变得越来越重要。 理论上，一般的安全多方计算问题是可解的[39,31,16]，但是Goldreich在文献[16]中指出，对于多方计算的特殊情况，使用这些一般方法获得解是不切实际的; 为了效率，应为特殊情况制定特殊解决方案。

Goldwasser预测，“今天多方计算领域如同十年前的公钥加密，是一个非常强大的工具和强有力的理论，现实生活中的使用虽然只是在这个时候才开始，但将来会成为我们的计算现实的一部分“[18]。

Goldreich的观察和Goldwasser的预测激励我们寻找具有“现实生活用法”的特定SMC问题，以及寻找他们的解决方案。 我们在安全多方计算环境下研究了许多具体的计算领域，如数据挖掘，入侵检测，数据库查询，科学计算，几何计算和统计分析。 结果带来了许多有趣的问题。本文的目的是记录这项研究的结果，并提出开放性问题。

为了寻找新的SMC问题，我们提出了一个转换框架，我们将正常计算（不一定与安全相关）转换为安全多方计算。 对这些问题的进一步研究带来了一些有趣的新问题。 我们将在本文中描述这些新问题，并讨论它们的潜在应用领域和相关工作（如果有的话）。 重要的是，本文件中提出的问题并不详尽; 我们相信在每个特定的计算领域中还有许多其他SMC问题。 我们的论文提供了一个框架，并为在其他领域工作的研究人员发现新的SMC问题提供一个指南。

本文的框架已经引起了一些有趣的调查。 一些问题目前正在研究中，如隐私保护合作统计分析[14]，隐私保护合作科学计算[13]和隐私保护几何计算[4]，隐私保护数据库查询[12]和隐私保护保留入侵检测。

2.相关工作

多方计算问题的历史是广泛的，从姚提出[39]，到 Goldreich，Micali和Wigderson [31]和其他人的扩展。这些工作都使用类似的方法论：计算问题首先表示为组合电路，然后各方针对电路中的每个门运行短协议。 虽然这种方法在其通用性和简单性方面非常有吸引力，但其生成的协议取决于电路的大小。 这个大小取决于输入域的大小，以及这种计算的复杂性。

在过去，安全多方计算的研究大多集中在理论研究上，并且已经研究了一些应用问题。 在文献中，有一些安全多方计算问题的示例，诸如私人信息检索问题（PIR），隐私保护统计数据库和隐私保护数据挖掘。

PIR问题由客户端和服务器组成; 客户端需要从服务器获得二进制序列的第i个比特，而不让服务器知道i; 服务器不希望客户端知道二进制序列。 解决这个问题并不困难; 但是，有效的解决方案，特别是具有小通信成本的解决方案并不简单。 研究[26,8,24,33,27,30,28,19]表明，可以设计一个协议来解决PIR问题，它比使用一般理论解决方案具有更优的通信复杂性。

隐私保护数据挖掘问题是一个特定的已经在文献中讨论的安全多方计算问题。 最近，Lindell和Agrawal提出了两个不同的隐私保护数据挖掘问题。 在Lindell的文章[29]中，问题定义为：双方都有一个私人数据库，联合两个数据库进行数据挖掘操​​作。 这两方如何实现这一点，而不向另一方或任何第三方透露他们的数据库。 在Agrawal的论文[1]中，隐私保护数据挖掘问题被定义为：Alice被允许对Bob私有数据库进行数据挖掘操​​作，Bob如何防止Alice访问个别数据记录中的精确信息，而Alice仍然能够进行数据挖掘操​​作？ 解决这两个类似的问题是完全不同的：Lindell和Pinkas使用安全多方计算协议来解决他们的问题，而Agrawal使用数据扰动方法。

除了上述问题，安全多方计算问题也存在于许多其他计算领域中，其中大多数没有被研究过。如果我们将隐私问题与在特定计算域中的协作计算相结合，则出现一些新问题。 本文的目的是记录我们如何识别这些问题及其定义。我们希望激励更多的人来思考这些问题。 本文的作者已经研究了这些问题中的一些[12,13,14,4]。

在某些情况下，只有部分数据集需要保密。 例如，当两个零售商店想要对他们的数据进行联合计算时，他们只关心他们的客户的名字，而不是每个事务。 在这些情况下，问题可以使用假名技术解决[6,5]。

3.框架

我们引入一个转换框架，将正常计算转换为安全多方计算。 我们从描述两个不同的计算模型（没有隐私要求）开始，然后展示如何将它们转换为隐私保护的模型，从而产生新的SMC问题。 转换后的模型是安全多方计算（SMC）模型。

根据输入的数量，我们将计算分为两个不同的模型：多输入计算模型和单输入计算模型。多输入计算模型通常有两个可区分的输入。 例如，客户端/服务器计算是多输入计算模型。 单输入计算模型通常具有一个输入或一组输入。例如，在数据挖掘和统计分析中，，尽管输入包括多个数据项，但所有输入通常来自一个数据集。

接下来，我们要将两个模型转换成安全多方计算模型，其中，来自每个参与方的输入被认为是私有的，并且没有人愿意向其他方公开其自己的输入。 在某些特定情况下，计算结果也是私有的，即某一方不应该知道结果。

对于多输入计算模型，因为该模型具有至少两个输入，其到相应的SMC模型的变换是直接的。 如果我们将每个输入视为来自不同方，则新问题现在变为“如何在保护每方输入隐私的同时进行相同的计算”。图1（a）演示了这样的变换。

对于单输入计算模型，由于它只有一个输入，我们不能使用与用于多输入计算模型相同的变换; 我们必须以某种方式将模型转换为多输入计算模型。 我们假设计算C，并且假设单个输入是数据项的集合D. 如果我们可以将D分成两个不相交的数据集D1和D2，我们得到一个多输入计算模型。 有很多方法将D分成两个数据集，每个方法都可能导致不同的SMC问题。 我们研究两种类型的变换：均匀变换和异质变换。

在均匀变换中，D的数据项被划分为两个集合，但是单个数据项不被划分为两个部分。 例如，如果D是学生记录的数据库，则均匀变换将把记录的子集放入一个数据集中，并将其余的记录放入另一个数据集中; 不过，每个学生的记录不被分成两部分。 换句话说，两个生成的数据集持有相同的特征。 图1（b）示出了这种变换。

在异构变换中，单个数据项被切割成两部分，每个部分到单独的数据集。 采用上面的例子，如果每个学生记录包含学生的学术记录和医疗记录，则异质变换可以将所有学生的学术记录放入一个数据集，并将所有学生的医疗记录放入另一个数据集。 换句话说，两个生成的数据集持有不同的特征。图1（c）示出了这种变换。

在上述变换之后，新问题现在变为“如何对D1和D2的并集进行计算C，其中D1属于一方，D2属于另一方，并且这两方都不想公开他或她的私有数据集。

隐私要求

解决方案是否达到隐私要求，就要我们知道隐私的正式定义。

Goldreich在[16]中提供了一个正式的隐私定义，并提供了一个坚实的理论背景，解决一个特定的安全多方计算问题应该基于此。 有关详细信息，请参阅[16]。

4.特定的安全多方计算问题

在本节中，我们将研究一些具体的计算，包括数据库查询，入侵检测，数据挖掘，几何计算，统计分析，科学计算和一些杂项计算。对于每个计算，我们将应用变换框架将其转换为安全多方计算问题。 如将示出的，由此产生的一些问题是新的，一些已经在过去被研究过。 对于已知问题，我们对相关工作进行简要调查; 对于新的问题，我们描述他们在现实生活中的应用。 我们还将一些众所周知的计算问题转换为相应的SMC问题，这些问题的应用目前尚未知晓，但是由于原始问题在实际生活中非常有用，我们认为相应的SMC问题最终将适用。

我们强调，本节中列出的清单并非旨在详尽无遗; 我们推测在本文所描述的模型之后还会出现许多新的研究问题。 本节作为指南，为那些在其特定领域工作以定义新的SMC问题的研究人员提供指导。

4.1隐私保护合作科学计算

问题1（等式的线性系统）Alice具有由M1x = b1表示的m个私有线性方程，Bob具有由M2x = b2表示的n-m个私有线性方程，其中x是n维向量。 Alice和Bob想要找到一个满足Alice和Bob公式的向量x。

问题2（线性最小二乘问题）Alice拥有m1个私有线性方程M1x = b1，Bob拥有m2个私有线性方程M2x = b2，其中x是一个n维向量并且m1 m2gt;n。Alice和Bob想得到一个x满足他们的解。因为有很多条件（方程）需要满足，这是不可能的。因此，他们希望尽量满足方程，使剩余向量R的大小与组件尽可能小（a_ji是M1和M2的形成新的矩阵的项）。最小二乘准则是使用的欧几里德（或最小二乘）范数的R的大小，即，最小化.

问题3.（线性规划）Alice具有由M1xlt;=b1表示的m1个私有线性不等式，Bob具有由M2xlt;=b2表示的m2个私有线性不等式，其中x是n维向量。 他们想要最小化（最大化）a1*x1 ... an* xn的值，对于已知的a1，hellip; ，an，并且解x =（x1，...，xn）应该满足Alice和Bob的所有要求。

线性方程组问题，线性最小二乘问题和线性规划问题已被证明对于规划，路由，调度，分配和设计中的许多不同类型的问题建模是有价值的。 利用这些问题及其扩展的工业包括交通，能源，电信和许多种类的制造。 在许多情况下，这些线性方程或线性要求是专有数据，并且大有价值，无法向任何人公开，尤其是对潜在竞争对手。

例如，在本文开头提到的一个例子中，两个金融组织计划合作开展一个互惠互利的项目。 每个组织都希望满足自己的要求（通常，这些要求被建模为线性方程或线性不等式）。 然而，他们的大部分需求很可能是他们的专有数据，其中包括客户的某些商品价格，利率和通货膨胀率，经济统计，投资组合持有等

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[141516]，资料为PDF文档或Word文档，PDF文档可免费转换为Word