妥协环境中的匿名分配和多数表决

摘要

描述了一种在云计算环境中进行匿名工作分配和多数表决的系统。该系统向物理节点广播工作，所述物理节点中的各个物理节点具有控制操作面(COP)节点以及与该COP节点相关联的一个或更多个服务节点。依据隐私工作指派调度，向单独的COP节点分发一组冗余工作指派，使得各个单独的COP节点仅获知其自己的指派和对应的工作。服务节点各自执行指派给COP节点的工作，使得该服务节点完成与该工作相关联的任务并且将单独的结果转发至与该服务节点相关联的COP节点。在COP节点之间执行隐私保护结果检查协议，使得获得多数结果的秘密份额，并且将多数结果提供给客户端。

说明书

政府权利

本发明是根据美国政府合同号HSHQDC-13-C-B0026在政府支持下完成的。政府拥有本发明的某些权利。

相关申请的交叉引用

本申请是2018年8月9日在美国提交的、名称为“Anonymous Allocation andMajority Voting in a Compromised Environment”的美国临时申请No.62/716,680的非临时申请，该美国临时申请的全部内容通过引用并入于此。

发明背景

(1)技术领域

本发明涉及安全系统，而且更具体地，涉及使用云控制操作面(COP：cloud-control operation plane)协议将工作匿名分配给节点服务器并对工作结果进行多数表决(majority voting)的安全系统。

(2)相关技术说明

安全多方计算(MPC)或隐私保护计算是密码术的一个子领域，其目标是创建使多方(或多个节点)在保持他们的输入不公开的同时联合地计算针对这些输入的函数的方法。与攻击者处于参与者的系统之外(针对发送方和接收方的窃听者)的传统的加密任务不同，本模型中的攻击者控制实际参与者。

云控制面是负责控制云中的工作执行的协议、工具、技术以及机制的组合，其可以包括调度、分配、状态报告以及其它控制功能。Baron等人首先提出了使用主动秘密共享(proactive secret sharing)和MPC来保护云中的控制面(参见并入的参考文献列表中的参考文献No.3)，但没有用于精确操作、实现的详细协议，也没有性能评估，尤其是针对恶意攻击者背景下的性能评估。

其它相关的云计算安全工作是MEERKATS云安全架构的工作(参见参考文献No.10)，其也使用主动秘密共享，但仅通过主动分享数据加密密钥来使得能够实现数据迁移。为了处理数据，各个云节点必须对数据进行解密，然后在本地存储未加密的版本。

最相关的MPC协议是参考文献No.6(DN-MPC)的协议。在参考文献No.11中引入了主动安全性，在参考文献No.9中对主动秘密共享进行了细化，以在少于一半的节点被破坏时提供加密安全性，而参考文献No.5解决了异步的情况。通用MPC的实际且已部署的实现的示例包括参考文献No.1，其利用三个服务器实现了甜菜的大规模拍卖。最近的其它示例包括参考文献No.2、No.7以及No.8。主动安全计算的公开可用实现的数量很少；一个是COCA(参见参考文献No.14)，其开发了一个容错的在线证书颁发机构，该证书颁发机构在局域网中和互联网上均已进行了测试。

尽管已有主动秘密共享和MPC协议来保护云中的控制面，但是现有技术都没有采取足够的措施来隐藏被指派了工作的服务器的身份。因此，持续需要这样一种安全系统，即，该安全系统允许从客户端接收工作的服务器集合以以下方式将各个工作指派给一个或更多个节点服务器：任何服务器都不知道其它服务器中的哪些服务器被指派了该工作，从而使得攻击者更难以有选择地针对被指派了任务的服务器。

发明内容

本发明涉及安全系统，更具体地，涉及使用云控制操作面(COP)协议将工作匿名分配给节点服务器并对工作结果进行多数表决(majority voting)的安全系统。所述系统包括非暂时性计算机可读介质和一个或更多个处理器，所述非暂时性计算机可读介质上编码有可执行指令，使得当执行所述可执行指令时，所述一个或更多个处理器执行多个操作。所述系统向多个物理节点广播可执行工作，所述物理节点中的各个物理节点具有单个控制操作面(COP)节点以及与所述COP节点相关联的一个或更多个服务节点。在多个COP节点之间联合地创建隐私工作指派调度。依据所述隐私工作指派调度，向单独的COP节点分发一组具有值m的冗余工作指派，使得各个单独的COP节点仅获知其自己的指派和对应的工作，其中，至少m个COP节点以大于预定阈值的概率被指派给工作。由服务节点执行指派给所述至少m个COP节点的工作，使得该服务节点各自完成与该工作相关联的任务并且将单独的结果转发至与该服务节点相关联的COP节点。在所述至少m个COP节点之间联合地执行隐私保护的结果检查协议，使得所述至少m个COP节点获得多数结果的秘密份额(share)，其中，所述多数结果是由所述服务节点的确定的多数获得的单独的结果。将所述多数结果提供给客户端。

在另一方面，除非被破坏的节点被指派给所述工作，否则向任何被破坏的节点隐瞒表示所述服务节点的确定的多数的值。

在另一方面，在执行所述结果检查协议时，实现确定多数值的表决算法，其中，所述表决算法包括表决阶段和多数决定阶段。

在另一方面，在所述表决阶段期间，被指派了所述工作的各个节点秘密分享[hash(y

在另一方面，在所述多数决定阶段期间，各个节点针对所有j恢复c

在另一方面，将满足hash(y

在另一方面，所述客户端是车辆，并且所述多数结果是到所述车辆的目的地的最佳路线。

在另一方面，所述系统使所述车辆沿着所述最佳路线进行机动。

最后，本发明还包括计算机程序产品和计算机实现方法。所述计算机程序产品包括存储在非暂时性计算机可读介质上的计算机可读指令，所述计算机可读指令能够由具有一个或更多个处理器的计算机执行，使得在执行所述指令时，所述一个或更多个处理器执行本文列出的操作。另选地，所述计算机实现方法包括使计算机执行这种指令并且执行所得操作的动作。

附图说明

根据下面结合参照以下附图对本发明的各个方面的详细描述，本发明的目的、特征以及优点是显而易见的，其中：

图1是描绘根据本公开的一些实施方式的安全系统的组件的框图；

图2是根据本公开的一些实施方式的计算机程序产品的例示；

图3是例示根据本公开的一些实施方式的受控制操作面(COP)保护的云的数据流的图；以及

图4是例示根据本公开的一些实施方式的安全系统的操作的流程图。

具体实施方式

本发明涉及安全系统，并且更具体地，涉及使用云控制操作面(COP)协议将工作匿名分配给节点服务器并对工作结果进行多数表决(majority voting)的安全系统。呈现以下描述以使本领域普通技术人员能够制造和使用本发明并将其并入特定应用的背景中。各种修改以及不同应用的多种用途对于本领域技术人员来说是显而易见的，并且本文限定的一般原理可以被应用于广泛方面。因此，本发明不旨在限于所呈现的方面，而是涵盖与本文所公开原理和新颖特征相一致的最广范围。

在下面的详细描述中，阐述了许多具体细节，以便提供对本发明的更透彻理解。然而，本领域技术人员应当明白，本发明可以在不必受限于这些具体细节的情况下来实践。在其它情况下，公知结构和装置按框图形式而不是按细节示出，以免妨碍对本发明的理解。

也请读者留意与本说明书同时提交的所有文件和文档，这些文件和文档与本说明书一起开放以供公众查阅，所有这些文件和文档的内容通过引用并入于此。本说明书中公开的所有特征(包括任何所附权利要求、摘要以及附图)可以由用于相同、等同或相似目的的另选特征来代替，除非另有明确说明。因此，除非另有明确说明，所公开的每个特征仅仅是一通用系列的等同或相似特征中的一个示例。

而且，权利要求中没有明确陈述“用于执行指定功能的装置”或“用于执行指定功能的步骤”的任何元素不应被解释为如在35 U.S.C.112节第6款中指定的“装置”或“步骤”条款。特别地，在本文的权利要求中使用“……的步骤”或“……的动作”不应触发35U.S.C.112节第6款的规定。

在详细描述本发明先前，首先提供了引用参考文献的列表。接下来，提供了对本发明各个主要方面的描述。最后，提供本发明各个实施方式的具体细节，以使得能够理解具体方面。

(1)并入参考文献的列表

贯穿本申请引用且并入以下参考文献。为了清楚和方便起见，这些参考文献在此被列为读者的中心资源。下列参考文献通过引用并入于此，就像在此完全阐述过一样。这些参考文献通过参照如下对应参考文献号而在本申请中加以引用：

1.Peter Bogetoft,DanLund Christensen,Ivan Damgrd,Martin Geisler,Thomas Jakobsen,Mikkel Krigaard,JanusDam Nielsen,JesperBuus Nielsen,KurtNielsen,Jakob Pagter,Michael Schwartzbach,and Tomas Toft.Secure multipartycomputation goes live.In Roger Dingledine and Philippe Golle,editors,Financial 16Cryptography and Data Security,volume 5628of Lecture Notes inComputer Science,pages 325–343.Springer Berlin Heidelberg,2009.

2.Dan Bogdanov,Sven Laur,and Jan Willemson.Sharemind:A framework forfast privacy-preserving computations.In Sushil Jajodia and Javier Lopez,editors,Computer Security-ESORICS 2008,volume 5283of Lecture Notes inComputer Science,pages 192–206.Springer Berlin Heidelberg,2008.

3.J.Baron,K.El Defrawy,A Nogin,and R.Ostrovsky.An architecture for aresilient cloud computing infrastructure.In Technologies for HomelandSecurity(HST),2013IEEE International Conference on,pages 390–395,2013.

4.Ran Canetti.Universally composable security:A new paradigm forcryptographic protocols.In Proceedings of the 42Nd IEEE Symposium onFoundations of Computer Science,FOCS’01,page 136,2001.

5.Christian Cachin,Klaus Kursawe,Anna Lysyanskaya,and RetoStrobl.Asynchronous verifiable secret sharing and proactive cryptosystems.InProceedings of the 9th ACM Conference on Computer and CommunicationsSecurity,CCS’02,pages 88–97,New York,NY,USA,2002.

6.Ivan Damg°ard and Jesper Buus Nielsen.Scalable and unconditionallysecure multiparty computation.In Alfred Menezes,editor,Advances inCryptology-CRYPTO 2007,volume 4622of Lecture Notes in Computer Science,pages572–590.Springer Berlin Heidelberg,2007.

7.Ivan Damgrd,Marcel Keller,Enrique Larraia,Valerio Pastro,PeterScholl,and NigelP.Smart.Practical covertly secure mpc for dishonest majorityor:Breaking the spdz limits.In Jason Crampton,Sushil Jajodia,and Keith Mayes,editors,Computer Security ESORICS 2013,volume 8134of Lecture Notes inComputer Science,pages 1–18.Springer Berlin Heidelberg,2013.

8.Ivan Damgrd,Valerio Pastro,Nigel Smart,and SarahZakarias.Multiparty computation from somewhat homomorphic encryption.InReihaneh Safavi-Naini and Ran Canetti,editors,Advances in Cryptology CRYPTO2012,volume 7417of Lecture Notes in Computer Science,pages 643–662.SpringerBerlin Heidelberg,2012.

9.Amir Herzberg,Stanislaw Jarecki,Hugo Krawczyk,and MotiYung.Proactive secret sharing or:How to cope with perpetual leakage.InCRYPTO,pages 339–352,1995.

10.A.D.Keromytis,R.Geambasu,S.Sethumadhavan,S.J.Stolfo,Junfeng Yang,A.Benameur,M.Dacier,M.Elder,D.Kienzle,and A.Stavrou.The MEERKATS cloudsecurity architecture.In ICDCSW,pages 446–450,2012.

11.Rafail Ostrovsky and Moti Yung.How to withstand mobile virusattacks(extended abstract).In PODC,pages 51–59,1991.

12.Adi Shamir.How to share a secret.Commun.ACM,22(11):612–613,1979.

13.Tomas Toft.Primitives and applications for multi-partycomputation.PhD Thesis.University of Aarhus,Sections 8.1-8.1.4,pages 49–53,2007.

14.Lidong Zhou,Fred B.Schneider,and Robbert Van Renesse.Coca:A securedistributed online certification authority.ACM Trans.Comput.Syst.,20(4):329–368,2002.

(2)主要方面

本发明的各种实施方式包括三个“主要”方面。第一个主要方面是安全系统。该系统通常采用计算机系统操作软件的形式或采用“硬编码”指令集的形式。该系统可以并入提供不同功能的各种各样的装置中。第二个主要方面是利用数据处理系统(计算机)操作的通常采用软件形式的方法。第三个主要方面是计算机程序产品。计算机程序产品通常表示存储在诸如光学存储装置(例如，光盘(CD)或数字通用盘(DVD))或磁存储装置(例如，软盘或磁带)之类的非暂时性计算机可读介质上的计算机可读指令。计算机可读介质的其它非限制性示例包括：硬盘、只读存储器(ROM)以及闪存型存储器。这些方面将在下面进行更详细描述。

图1中提供了描绘本发明的系统(即，计算机系统100)的示例的框图。计算机系统100被配置成执行与程序或算法相关联的计算、处理、操作和/或功能。在一个方面，本文讨论的某些处理和步骤被实现为驻留在计算机可读存储器单元内并由计算机系统100的一个或更多个处理器执行的一系列指令(例如，软件程序)。在执行时，所述指令使计算机系统100执行特定动作并展现特定行为，如本文所描述的特定行为。

计算机系统100可以包括被配置成传送信息的地址/数据总线102。另外，一个或更多个数据处理单元(诸如处理器104(或多个处理器))与地址/数据总线102联接。处理器104被配置成处理信息和指令。在一方面，处理器104是微处理器。另选地，处理器104可以是不同类型的处理器，诸如并行处理器、专用集成电路(ASIC)、可编程逻辑阵列(PLA)、复杂可编程逻辑器件(CPLD)或现场可编程门阵列(FPGA)。

计算机系统100被配置成利用一个或更多个数据存储单元。计算机系统100可以包括与地址/数据总线102联接的易失性存储器单元106(例如，随机存取存储器(“RAM”)、静态RAM、动态RAM等)，其中，易失性存储器单元106被配置成存储用于处理器104的信息和指令。计算机系统100还可以包括与地址/数据总线102联接的非易失性存储器单元108(例如，只读存储器(“ROM”)、可编程ROM(“PROM”)、可擦除可编程ROM(“EPROM”)、电可擦除可编程ROM(“EEPROM”)、闪速存储器等)，其中，非易失性存储器单元108被配置成存储用于处理器104的静态信息和指令。另选地，计算机系统100可以执行从诸如“云”计算中的在线数据存储单元取回的指令。在一方面，计算机系统100还可以包括与地址/数据总线102联接的一个或更多个接口，诸如接口110。所述一个或更多个接口被配置成使得计算机系统100能够与其它电子装置和计算机系统连接。由所述一个或更多个接口实现的通信接口可以包括有线(例如，串行电缆、调制解调器、网络适配器等)和/或无线(例如，无线调制解调器、无线网络适配器等)通信技术。

在一个方面，计算机系统100可以包括与地址/数据总线102联接的输入装置112，其中，输入装置112被配置成将信息和命令选择传送至处理器100。根据一个方面，输入装置112是字母数字输入装置(诸如键盘)，其可以包括字母数字键和/或功能键。另选地，输入装置112可以是除字母数字输入装置之外的其它输入装置。在一方面，计算机系统100可以包括与地址/数据总线102联接的光标控制装置114，其中，光标控制装置114被配置成将用户输入信息和/或命令选择传送至处理器100。在一方面，光标控制装置114是利用诸如鼠标器、轨迹球、轨迹板、光学跟踪装置或触摸屏的装置来实现的。尽管前述如此，但在一方面，诸如响应于使用与输入装置112相关联的特殊键和键序列命令，光标控制装置114经由来自输入装置112的输入而被引导和/或启用。在另选方面，光标控制装置114被配置成通过话音命令管理或引导。

在一方面，计算机系统100还可以包括一个或更多个可选计算机可用数据存储装置，诸如与地址/数据总线102联接的存储装置116。存储装置116被配置成存储信息和/或计算机可执行指令。在一个方面，存储装置116是诸如磁盘驱动器或光盘驱动器(例如，硬盘驱动器(“HDD”)、软盘、光盘只读存储器(“CD-ROM”)、数字通用盘(“DVD”))的存储装置。依据一个方面，显示装置118与地址/数据总线102联接，其中，显示装置118被配置成显示视频和/或图形。在一方面，显示装置118可以包括：阴极射线管(“CRT”)、液晶显示器(“LCD”)、场发射显示器(“FED”)、等离子体显示器，或适于显示视频和/或图形图像以及用户可识别的字母数字字符的任何其它显示装置。

本文所呈现的计算机系统100是根据一方面的示例计算环境。然而，计算机系统100的非限制示例并不严格限于作为计算机系统。例如，一个方面提供了计算机系统100表示可以根据本文所述各个方面使用的一类数据处理分析。此外，还可以实现其它计算系统。实际上，本技术的精神和范围不限于任何单一数据处理环境。因此，在一方面，使用通过计算机执行的计算机可执行指令(诸如程序模块)来控制或实现本技术的各个方面的一个或更多个操作。在一个实现中，这样的程序模块包括被配置成执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件和/或数据结构。另外，一个方面提供了通过利用一个或更多个分布式计算环境来实现本技术的一个或更多个方面，诸如，在该计算环境中，任务由通过通信网络链接的远程处理装置执行，或者诸如，在该计算环境中，各种程序模块位于包括存储器-存储装置的本地和远程计算机存储介质中。

图2中描绘了具体实施本发明的计算机程序产品(即，存储装置)的示图。计算机程序产品被描绘为软盘200或诸如CD或DVD的光盘202。然而，如先前提到的，该计算机程序产品通常表示存储在任何兼容的非暂时性计算机可读介质上的计算机可读指令。如关于本发明所使用的术语“指令”通常指示要在计算机上执行的一组操作，并且可以表示整个程序的片段或单个分离的软件模块。“指令”的非限制性示例包括计算机程序代码(源或目标代码)和“硬编码”电子装置(即，编码到计算机芯片中的计算机操作)。“指令”被存储在任何非暂时性计算机可读介质上，诸如存储在计算机的存储器中或软盘、CD-ROM以及闪存驱动器上。无论如何，这些指令被编码在非暂时性计算机可读介质上。

(3)各个实施方式的具体细节

本文描述的是一种安全系统，该安全系统实现用于服务器集合的(以运算电路的形式表达的)网络协议集合，以利用多方计算(MPC)协议执行随机化的冗余工作分配并且进行关于任务结果的多数表决。为了提供背景，想象一个受到强大攻击者潜在攻击的分布式系统(例如，云或网格计算环境)，如果攻击者知道需要攻击哪个节点，那么他们可以潜在地破坏系统中的任何特定节点。此外，假定所述节点的某一子集可能已经在攻击方的控制之下(不必以任何方式明显体现出来)。为了保护敏感工作的执行不受攻击方攻击，确信以以下方式在随机挑选的节点上执行工作是有益的：只有受指派节点才能发现它已被指派，而其它节点(包括受攻击方控制的节点)都无法发现或影响该分配。可选地，为解决因运气差而将工作指派给妥协(compromised)节点的可能性，根据本公开的实施方式的系统进行若干冗余分配并且比较结果。

在该项工作中，假设在分配之后以及在结果交付之前，结果是由单独的节点来计算的，而分配和结果交付是由安全的多方计算协议来执行的。先前的工作分配协议没有采取足够的措施来隐藏被指派了工作的服务器的身份。在本公开中描述的协议允许从客户端接收工作的服务器集合以以下方式将各个工作指派给一个或更多个节点服务器：任何服务器都不知道其它服务器中的哪些服务器被指派了该工作。这使得攻击者更难以有选择地针对被指派了任务的服务器。

本文所描述的系统以多种方式对现有工作进行了改进。第一，将主动秘密共享和MPC用于设计和实现云计算的轻量级的弹性且匿名的监督层，这是该领域的主动安全计算的第一个应用。第二，提供了独特的加密协议，该加密协议有效地执行监督层中所需的操作，并使昂贵的交互式MPC步骤的使用最小化。第三，在不同层面上进行了优化，以加速和扩展MPC。第四，整个云控制操作面(COP)监督层是以针对诚实但又好奇的攻击者以及恶意的攻击者的安全保证来实现的。最后，利用大量节点(高达128个)执行实验，并且报告了在大量节点下整个系统的性能评估(典型的现有技术MPC实现和部署考虑了不到十个节点)。

(3.1)架构和数据流

以下是对旨在用于根据本公开的实施方式的协议的系统的数据流的描述。该数据流可以在云架构上实现，这种云架构的非限制性示例如美国专利No.9,846,596中所描述的技术，其通过引用并入于此，如同在此全面阐述一样。还描述了在本文所描述的发明中使用的MPC的加密目前发展水平。

图3描绘了云架构的总体数据流。首先，用户有一份要云执行的工作。用户通过将工作广播给具有COP节点(例如，软件组件)的所有物理节点(例如，计算机)来将工作发送至云(要素300)。例如，若干单独的软件组件可以驻留在单个物理节点上。物理节点可以包含COP软件(“COP节点”)、执行计算工作的虚拟机等。“COP层”是所有COP节点、这些COP节点联合执行的协议等的组合。

COP节点(元素302)(即使一些COP节点是妥协的)联合地创建隐私工作指派和复制调度(元素304)。COP节点将工作指派联合地分发给各个COP节点，各个COP节点将与任务相关的工作指派给驻留在它们的主机处的服务节点。出于本公开的目的，主机等同于物理节点，而服务节点是执行与工作相关的功能的软件模块(这与由COP层执行与工作控制相关的功能(参见参考文献No.3)完全不同)。COP节点不知道(因此不在同一主机上的服务节点不知道)任何其它COP节点是否具有指派或者不知道任何其它指派的内容。为了提供针对短期破坏的适应性(resiliency)，工作是由COP节点(根据可以按照COP攻击风险估计动态改变的可调谐参数)进行冗余指派的。

工作实际上是由服务节点执行的；这些节点是彼此隔离的，并且仅可以通过COP或者辅助COP服务中的一者彼此进行通信或者与用户进行通信。当执行相同工作的一组节点完成其任务(即计算(元素306))时，该组节点将它们的输出转发至对应的COP节点。具有这些相同工作输出的COP节点联合地执行不透露身份或结果的隐私保护鲁棒结果检查协议(元素308)，并且COP共同地获得由多数服务节点获得的结果的秘密份额。COP节点参与协议并获取份额。在一些情况下，是全部COP节点参与全部协议并全部获得份额。然而，也可以决定将系统设置为具有不参与任何事的备用节点。另外，协议还可以选择将某些行为异常的节点排除在参与之外。然后，COP将这些份额用于下一序列的与匿名任务相关的工作。在最后阶段，COP取得最终的已检查了结果的输出(元素310)，并将其转发给用户。

在该处理期间的任何时刻，各个节点仅知道运行其自己的任务所需的信息；COP节点共同使用的任何全局信息(诸如工作指派信息和中间工作数据)对于各个COP节点都是未知的。这是为了确保当攻击方控制同一物理节点上的任何节点时，攻击方所能做的就是获得有关该特定物理节点而非有关任何其它云数据的信息(例如，有多少个节点以及哪些节点正在从事同一工作)。由于任何COP节点都将始终以固定间隔(这些间隔也是可调谐参数)被重置成原始状态，因此，即使COP节点被不断地破坏，COP操作也会继续畅通无阻。本文所描述的系统由用于安全且有效地实现上述架构的“工作提交”模块、“工作指派和复制”模块以及“鲁棒结果检查”模块的协议组成。

(3.2)密码学初步

本发明所基于的引擎是一种众所周知的技术——安全多方计算(MPC)。在这一节中，提供了有关在本发明中使用的特定形式的MPC的一些细节。本节提供有关先前已知技术的背景信息。首先，提供了对线性秘密分享和通用安全多方计算(MPC)协议的回顾。然后，提供了使用MPC进行消息认证和抛硬币(coin tossing)的描述。这些构建模块和协议被用于构建用于工作提交、工作分配以及结果交付的Cloud-COP协议。在本公开中，k表示安全参数。

(3.2.1)秘密分享

非正式地，n方之间的n分之t(t-out-of-n)秘密分享(SS)方案(参见参考文献No.12)是这样一种方案：其中，具有秘密s的交易方(D)向所有各方分发份额(表示为[s])，使得任意t方或更多方可以通过执行多项式插值来根据其份额重构s。主要的安全保证在于：少于t方的组无法了解有关s的任何信息。在Shamir的n分之t非线性SS方案中(参见参考文献No.12)，为了分享秘密s，交易方D选择随机单变量多项式

(3.2.2)安全多方计算(MPC)

用于Cloud-COP操作的主要密码构建模块之一是MPC协议，该MPC协议使得n方能够安全地评估描述待执行的计算的运算电路(即，将计算表示为加法门和乘法门)。特别地，本公开在

1.Rand：在执行时，多个方获得t-分享[r]的l个实例，r是在域

2.DoubleRand：在执行时，多个方获得l对的份额[r]和，使得r在域

3.MultTriple：这种三元乘法协议使得多个方能够计算l个三元组[a]、[b]以及[c]，使得a和b在域

4.Mult([a]，[b])：多个方最初持有两个份额[a]和[b]。当执行该协议时，多个方获得份额[c]，使得c＝a·b(实现利用MultTriple的较早执行)。

5.Open([s])：多个方最初持有份额[s]。如果多个方公开地开放[s]，则所有方均可以从执行中获得s。如果多个方朝向P

应注意，由于所基于的秘密分享方案的线性度，可以在本地执行两个份额的加法运算以及在标量与份额之间的任何代数运算。即，[a]+[b]＝[a+b]，a+[b]＝[a+b]，以及a[b]＝[ab]。上面的前三个协议是用于预处理的协议，它们的输出被用作对运算电路进行安全评估的资源。在下面的算法描述中，稍微援用(abuse)了随机份额的符号如下：节点计算[r]←Rand(·)意味着节点从预处理的随机份额的列表中取得了通过执行Rand(l)生成的[r]。这种符号上的援用也适用于其它预处理数据，诸如双重随机分享和三元乘法。

(3.2.3)RandBit

这是辅助的MPC协议，这归因于被用作其它协议的构建模块的Toft(参见参考文献No.13)。下面的协议RandBit允许服务器计算随机位(0或1)的秘密分享，使得没有服务器知道该位的值。

输认：无

输出：所有节点均输出它们的均匀选择的位b的份额[b]。

1.所有Pi联合计算[r]←Rand(·)。

2.所有P

3.所有P

4.除了指数级的小概率，存在r

5.各方在本地计算[b]←2

(3.3)MPC协议(电路)

(3.3.1)GenCoin

这是被用作其它协议的构建模块的简单的辅助协议。下面的协议GenCoin允许服务器计算0至n-1(包含0和n-1)之间的随机整数的分享，使得没有服务器知道所分享的整数。与下面的协议不同，鉴于参考文献No.7，该协议是相当明显的。

输认：数字n，采样域的上限，其中，n是二的幂。

输出：所有节点均输出它们的数字r的份额[r]，使得r是在{1，2，...，n}中随机均匀分布的。

1.所有P

2.所有P

(3.3.2)Convert

下面的协议Convert允许服务器根据表示相同秘密值的二元向量来计算表示秘密值的一元向量。这是被用作其它协议的构建模块的辅助协议。

输入：节点标识符i的分享的二元表示[b

输出：分享的一元分配向量<[a

1.对于各个i∈{1，...，n}，所有节点联合计算

2.所有节点均输出向量<[a

(3.3.3)信息理论消息认证码(MAC)

为了使得客户端能够验证从计算(或服务)节点发送的消息的有效性和真实性(authenticity)，各方可以使用简单且有效的MAC。设x为计算节点需要发送给客户端的消息，该消息被定义为域F的元素。假设a和b(其中，a和b在域F中是均匀分布的)是由客户端和计算节点两者协定并持有的。将消息x的MAC定义为y＝a*x+b。当节点将其消息x发送给客户端时，该节点也发送y。当接收到(x；y)时，客户端检查是否y＝a*x+b，并且如果该检查成功，则客户端接受消息x。应注意，除概率1＝|F|以外，未拥有a和b的节点将无法相对于a和b来生成消息x的正确的MAC。

虽然MAC对于在将工作指派给单个节点时检查有效性和真实性很有用，但是在将工作指派给多个节点时，不需要MAC，这是因为多数表决处理确认了有效性和真实性。因此，MAC是可选的特征。

(3.3.4)SecureJobSubmission

下面的协议SecureJobSubmission允许客户端将工作提交到服务器集合。这是开始执行该工作的初始协议。它实现了数据流程图中的“工作提交”模块。在这个协议中，客户端将秘密密钥的份额分发给服务器，这将允许被指派的服务器对工作数据进行解密。

输认：客户端具有描述计算工作的隐私输入(数据)。

输出：所有节点均获得它们的解密密钥sk的份额[sk]，以及密文Enc

1.客户端对秘密密钥sk进行采样。

2.客户端通过计算Enc

3.客户端计算sk的t-分享[sk]。

4.客户端向服务器广播ξ，并将各个份额[sk]发送到服务器节点。

(3.3.5)RandJobAlloc

下面的RandJobAlloc协议允许服务器将按协议SecureJobSubmission提交的工作分配给所述服务器中的一个服务器，而这些服务器中的任何服务器均不知道哪个服务器被指派了该工作。被指派的服务器将接收到客户端提交的秘密密钥，这将允许该服务器对数据进行解密。

该协议是数据流程图的“工作指派和复制”模块的两种另选实现之一。它实现了工作指派功能，但没有实现复制功能。可以在不需要复制的那些情况下使用该协议。另选地，可以将该协议用作下面的RedundantRandJobAlloc协议的构建模块。

输认：从客户端接收到的标识符为σ的工作的解密密钥sk的份额[sk]。

输出：当且仅当P

1.所有方执行[τ]←GenCoin

2.所有方执行([a]，[b])←Rand(·)。

3.所有方将它们的份额[a]和[b]发送给客户端。

4.对于各个i，使得1≤i≤n，所有方计算以下项：

a.[r

b.[r′

c.[r″

5.对于各个i，使得1≤i≤n，所有方使用Mult(·，·)和本地计算来计算以下项：

a.[α

b.[β

c.[γ

6.对于各个i，使得1≤i≤n，所有方朝向P

7.对于各个i，使得1≤i≤n，所有方针对τ的二元表示的份额来计算Convert(·)，并将所得的指派向量更新至它们的状态。

8.客户端通过使用Berlekamp-Welch算法重构(a，b)来输出MAC密钥(a，b)。

9.各个P

应注意，在步骤9中，已经具有指派的工作的一方将得到sk、a和b，而其它所有方都将得到随机值(即，噪声)。已经具有指派的工作的一方通过了解其得到的值是格式正确的sk/a/b三元组来获知其得到了指派。

(3.3.6)RedundantRandJobAlloc

下面的协议RedundantRandJobAlloc与上面的协议RandJobAlloc类似；唯一的区别是它使用RandJobAlloc作为子协议来将工作提交给多个服务器，而不是单个服务器。该协议是数据流程图的“工作指派和复制”模块的两种另选实现中的主要实现。

输入：从客户端接收到的标识符为σ的工作的解密密钥的份额[sk]和期望重数(multiplicity)μ。

输出：被指派了工作的至多2μ-1个节点输出解密密钥sk。

1.令μ＜n/4。

2.所有方联合地独立执行RandJobAlloc协议达2μ-1次。

3.所有方输出通过上述步骤计算出的结果。

(3.3.7)SingleJobDelivery

下面的协议SingleJobDelivery将完成的工作数据返回给客户端，并且允许客户端确认所述数据已来自被指派了该工作的服务器。针对将RandJobAlloc协议用于数据流程图的“工作指派和复制”模块的那些另选方案，该协议实现了数据流程图的“鲁棒结果检查”模块。

被指派了工作的节点P的输入：结果m和MAC密钥(a，b)(如果被指派了工作，则在工作分配期间获得的)。

客户端的输入：MAC密钥(a′，b′)(在工作分配期间获得的)。

输出：客户端输出从节点P发送的m。

1.令P方是被指派了由客户端C请求的工作的节点，使得结果为m。

2.P方随机均匀地选择域元素x并计算y＝ax+b。

3.P方将(m，x，y)发送给客户端C。

4.可选地——所有其它方向客户端发送了大小相同的随机消息(在期望由受指派节点生成的网络流量应与所有其它节点生成的网络流量无法区分的情况下使用)。

5.当接收到来自P的(m，x，y)时，客户端C使用它自己的(a′，b′)并且检查是否y＝a′x+b′。

6.如果该检查成功，则C接受并输出m作为计算的结果。

7.否则，该客户端输出⊥。

(3.3.8)RedundantJobDelivery

下面的协议RedundantJobDelivery与协议SingleJobDelivery类似，区别在于RedundantJobDelivery是在工作是由多个服务器进行处理的情况下使用(而不是在SingleJobDelivery的情况下仅使用一个服务器进行处理)。协议RedundantJobDelivery实现了一种表决算法，以允许服务器决定要返回给客户端的工作的正确值。针对那些将RedundantRandJobAlloc协议用于数据流程图的“工作指派和复制”模块的另选方案，该协议实现了数据流程图的“鲁棒结果检查”模块。

当将工作指派给多个节点时，期望CloudCOP节点在内部(但以安全且匿名的方式)计算它们的输出的多数(majority)。下面，假设客户端将工作作为具有值m的冗余工作指派提交到云，以使至少有m个节点以高概率被指派了该工作。m的值可以大于或等于1。例如，在大多数时间，COP节点可以选择使用m＝1，而对于不可预测但罕见的时机选择m＝2，以便抓住潜在的欺骗者。匿名多数表决的期望特性是：

(1)除非被破坏的一方被指派了工作，否则被选定为多数的值相对于该被破坏的各方仍保持隐瞒；以及

(2)被指派了工作的节点的身份相对于被破坏的各方仍保持隐瞒。

作为附加的安全层，被指派了工作的节点可以在分享散列之前，使用与客户端提供的用于加密初始工作数据相同的密钥来对该散列进行加密。在下面的描述中，用Assigned表示被指派了工作的节点集，用

各个节点P

输出：客户端获悉多数结果y。

1.表决阶段：

a.各个P

b.各个

c.各个P

d.各个P

e.各个P

2.多数决定阶段：

a.各个P

b.各个P

c.各个P

d.各个P

e.各个

f.客户端通过支持多数来确定y，并且取满足hash(y

图4是描绘本文所描述的系统执行的操作的流程图。给定可执行工作(元素400)，在第一操作(元素402)中，系统将工作广播给一组物理节点，所述物理节点中的各个物理节点具有单个控制操作面(COP)节点以及与所述COP节点相关联的一个或更多个服务节点。在第二操作(元素404)中，在COP节点之间联合地创建隐私工作指派调度。在第三操作(元素406)中，依据所述隐私工作指派调度，向单独的COP节点分发具有值m的一组冗余工作指派，使得各个单独的COP节点仅获知其自己的指派和对应的工作，其中，以大于预定阈值的概率向至少m个COP节点指派工作。阈值的常见示例包括“少于n/3个节点”和“少于n/4个节点”，其中，n是参与MPC协议的节点的总数。在第四操作(元素408)中，由服务节点执行指派给m个COP节点的工作，使得该服务节点完成与该工作相关联的任务并且将单独的结果转发至与这些服务节点相关联的COP节点。在第五操作(元素410)中，在所述至少m个COP节点之间联合地执行隐私保护结果检查协议，使得所述至少m个COP节点获得多数结果的秘密份额。将多数结果(元素412)提供给客户端。

本发明可以被用于广泛数量的应用。例如，本文所描述的系统和方法可以被用于允许分布式车辆/飞机以安全的方式向分布式服务器提交工作。车辆要分发的工作的非限制性示例是请求帮助车辆找到到达其目的地的最佳路线，其中，输出是最终的最佳路线。然后，系统可以通过经由多个车辆机械组件(例如，制动机构、转向机构、发动机、加速机构)使车辆进行诸如转向、加速、减速以及停止的车辆操作，从而使车辆沿着最终的最佳路线自动地进行机动。

最后，虽然已经根据多个实施方式对本发明进行了说明，但本领域普通技术人员应当容易地认识到，本发明可以在其它环境中具有其它应用。应注意，可以有许多实施方式和实现。此外，所附权利要求绝不旨在将本发明的范围限于上述具体实施方式。另外，“用于……的装置”的任何用语旨在引发要素和权利要求的装置加功能的解读，而未特别使用“用于……的装置”用语的任何要素不应被解读为装置加功能要素，即使权利要求以其它方式包括了“装置”一词。此外，虽然已经按特定顺序陈述了特定方法步骤，但这些方法步骤可以按任何期望的顺序进行，并且落入本发明的范围内。