CN1875569A - 用于有效多方乘积的方法和设备 - Google Patents

Abstract

本发明在基于同态阈值加密系统的安全多方计算的体制中引入一种协议和一种特别的乘法门电路，它们可以仅使用标准同态阈值ElGamal加密以惊人地简单和有效的方式实现。因为加法门电路本质上是没有限制的，条件门电路不仅允许建立用于任何函数的电路，而且事实上可用产生用于各类任务的有效电路。

Description

用于有效多方乘积的方法和设备

技术领域

本发明涉及一种用于一方(party)参加多个参与者(paticipant)之间的安全多方乘积协议(secure multiparty multiplicationprotocol)的方法，一种被安排为实现该方法的设备，以及具备引起可编程设备执行该方法的计算机可执行指令的计算机程序产品。

安全多方计算是多个参与者计算函数f以获得未加密输出的处理。在计算期间只有输出结果对于参与者是可用的。

背景技术

这些计算类型的一些公知的实例是拍卖(auctions)、百万富翁问题、安全函数估计、投票、具备合理和安全的简档匹配的加密计算。

同态阈值加密系统提供了安全多方计算的基础。对于已知的n元函数f来说，基本门电路的电路是由在其输入线上的给定加密x₁，...，x_n和在其输出线上产生的加密f(x₁，...，x_n)构成的。基本门电路按照相同的方式运行。整个电路中的线路被相同的公钥加密；对应的私钥被一组各方共享。

基本门电路对比特或者更大域(环(rings)或者字段)的元素进行操作，显然从效率的角度看后一种类型是首选的。

借助加密计算的工具箱中的基本工具是安全乘积协议。尽管可以不必解密任何值，以及不用充分利用加密系统的同态性能地估计加法门电路，但是乘法门电路要求至少一个阈值解密来继续处理。

在US专利6,772,339中描述了一种安全多方计算的方法，该方法包括：根据将被计算的函数产生数据集，所述数据集包括第一数据和第二数据对；对于第一数据和第二数据的每对，加密所述第一数据和所述第二数据；将已加密的第一数据和第二数据对混合；比较加密的输入数据与所述加密的输入数据以检测匹配；选择符合所述已检测匹配的已加密的第二数据。

由此得到的用于估计乘法门电路的协议尽管概念简单，但是十分低效。

发明内容

因此，本发明的目的是提供一种能够为多方计算，特别是为乘积协议提供有效构件块的方法和设备。

本发明的目的是通过用于使一方参加多个参与者之间的安全多方乘积协议的方法来实现的，该协议被安排为计算专有第一数据和加密第二数据的乘积，其中该协议包括具有以下步骤的子协议：

-所述一方获得第一数据，第一数据是专有第一数据或者是来自二值域的第一数据，

-所述一方获得加密的第二数据，

-所述一方计算加密的输出数据，其包括使用基于离散对数的加密系统对第一数据与第二数据的乘积进行的随机加密，

-所述一方产生一个被安排为显示加密的输出数据正确的证据。

乘积协议将输入当作专有或者加密的乘数x和加密的被乘数y，在多项式时间(polynomial time)中产生输出，即乘积xy的加密。该协议不泄漏任何关于x、y和xy的信息。此外，出于安全性的原因，要求该协议产生公众可检验的证据，即直接地计算乘积。

按照本发明的方法，给定的专有或者加密的第一数据[[x]]＝(a，b)＝(g^r，g^xh^r)和加密的第二数据[[y]]＝(c，d)，其中一方P知道r，x，所述一方P使用基于离散对数的加密系统的同态性能计算随机加密[[xy]]＝(e，f)＝(g^s，h^s)*[[y]]^x，其中s∈_RZ_q。所述一方P还产生显示输出是正确的证据，这意味着它证明证人的认识，r；s；x∈Z_q满足a＝g^r，b＝g^xh^r，e＝g^sc^x，f＝h^sd^x。

该方法允许有效地实施应用，例如该方法允许至少两个用户按照一些量度比较他们的专有数据，而不必透露除他们是否相似或不同之外的任何其他的信息。

这种基于离散对数的解决方案的进一步优点是关于阈值版本(threshold version)的分布的密钥生成相对简单。

该方法的一个附加的优点是它还解决了恶意情况的处理并且解决了双方情况下的公平问题。

本发明的又一个优点是它尤其适合在大组对等用户之间的特别联系方面的执行，其中重要的是每个用户仅需要有限数量的设置信息(独立于用户的总数)，以及总的执行时间-包括关于分布的密钥生成的时间-用于在任何两个用户之间运行协议，也是有限的。

该乘积协议的方法要求其中一个乘数是专有的，即只为单一一方所知。

这个限制允许乘积协议在Diffie-Hellman假定下存在。

依照本发明的有利的方法的特征在于第一数据是来自二值域的随机数据。

该方法允许至少两个用户获得两个数的乘积，其中一个数是来自二值域的随机数，和显示该结果被正确计算的证据。

该方法执行一种能计算两个已加密数的加密乘积的协议。

在被称作是有条件的门电路的依照权利要求2的协议中，乘数x来自于两分(二值的)域。这个限制允许乘积协议在Diffie-Hellman假定下存在。发明者实现了对比特操作的基本门电路能足以有效地实施包括乘积的多方计算。

如果x只限于二值域，则依照权利要求2的协议能有效地将加密数值x和y相乘。

依照本发明的有利方法的特征在于基于离散对数的密码系统是ElGamal加密系统。

发明者相信同态ElGamal基本上能足够有效地处理各种各样的问题。第二数据的加密是同态ElGamal加密，其中很清楚这些加密是随机化的，并且用于这些加密的公钥总是相同的。对应的私钥在多个各方之间共享。

优点是当前的方法在仅使用同态阈值ElGamal加密的标准判定Diffie-Hellman假定下运行，这比例如使用诸如Paillier加密系统的RSA类加密系统便宜得多，因为生成用于对应阈值加密系统的共享RSA模数(modulus)很昂贵，它经常主导整个应用的成本。即使对于双方的情况，共享RSA模数是件不平凡的(non-trivial)任务。相反，用于基于离散对数的加密系统的分布的密钥生成很简单，事实上在双方情况中是没有限制的。

作为一个附加的优点，ElGamal允许基于任何离散对数设置，例如椭圆曲线或者XTR的解决方案。

每方用于估计有条件的门电路的工作总计大约12次取幂(exponentiation)，但是在上述US专利的混合匹配(Mix and Match)方法中，因为每方需要隐蔽和改序(permute)组成门电路的加密真值表的4×3个ElGamal加密并且提供正确性证据，所以要求对类似的乘法门电路采取近似150次取幂；每个用户还必须平均参加4次明文-相等(plaintext-equality)测试。

因此，依照当前发明的方法可能是迄今为止关于姚(Yao)的百万富翁问题和例如安全拍卖的许多其他问题中的最有效的解决方案。

依照本发明的有利方法的特征在于加密数据是Pederson委托(commitments)。

经常通过对乘数用Pedersen委托<<x>>＝g^xh^r代替ElGamal加密[[x]]＝(g^r，g^xh^r)的方式进行细微的优化。

依照本发明的有利方法的特征在于该协议包括另外的步骤-所述一方向至少一个其他的参与者传送证据，

依照本发明的有利方法的特征在于该协议包括另外的步骤-所述一方向至少一个其他的参与者传送加密的输出数据，

依照本发明的有利方法的特征在于在两方之间执行该协议。

此外，通过被安排为执行依照权利要求1的方法的设备来实现本发明的目的。

此外，通过能够进行多方计算的、具备引起可编程设备执行依照权利要求1的方法的计算机可执行指令的计算机程序产品来实现本发明的目的。

附图说明

图1举例说明乘积协议的子协议，和

图2显示用于执行依照本发明的方法的设备。

具体实施方式

多方乘积协议是一种由两个或更多参与者执行的协议。

该协议的输入包含两个(可能被加密的)数，x和y。数x可以由参预者(player)P₁提供；y可以由参预者P₂提供。该协议结束时，两个参预者得到乘积[[xy]]作为结果。此外，用户还得到该结果被正确计算、另一个参预者(多个参预者)没有欺骗的证据。

首先讨论一些进行计算所需的预备知识。

令G＝<g>表示素数次序(order)q的有限循环(倍增的)组，在此假定判定Diffie-Hellman(DDH)问题为不可行的。

对于公钥h∈G来说，附加地使用同态ElGamal加密，消息m∈Z_q被加密成为一对(a，b)＝(g^r，g^mh^r)，其中r∈Z_q。同态性能是m和m′的加密的分量方式乘积(component wise multiplication)，产生m+m′的加密(模q)：(a，b)*(a′，b′)＝(aa′，bb′)＝(g^r+r′，g^m+m′，h^r+r′)。

假使加密(a，b)＝(g^r，g^mh^r)是公共输入，标准技术产生用于显示(唯一)证人(m，r)的认识的认识的证据。(按照倍增的意义，对于m∈G，具有形式为(g^r，m h^r)的加密的标准ElGamal加密是同态的，但是缺乏这种认识的证据。)

通过表示当且仅当log_g(a/a′)＝log_h(b/b′)时加密(a，b)和(a′，b′)相等来定义关于GxG的等价关系。使用(I，g^m)，m∈Z_q作为正规的代表，[[m]]用来表示(I，g^m)的等价类。换句话说，[[m]]表示m的所有ElGamal加密(在公钥h下)的集合。按惯例，关于直积(direct product)群GxG的操作被提升(lifted)到等价类。同态性能则表示[[x]]*[[y]]＝[[x+y]]知[[x]]^c＝[[cx]]。

因此容易完成通过标量的加法和乘法。当以确定的方式实施时可以容易地检验这些操作。

ElGamal加密的随机化(或者隐蔽)也是重要的原语(primitive)。这实际上是给定加密与随机元素(a，b)∈_R[[0]]相乘。证明log_ga＝log_hb显示(a，b)确是0的加密。

假定私钥α＝log_gh，通过计算b/a^α执行解密，对于一些m∈Z_q来说，其等于g^m。通常认为从g^m中恢复m很难，因此必须查看这个加密系统中关于有充分小的尺寸的集合M∈Z_q的情况，使得无论何时m∈M从g^m找到m都是可行的。然而在当前的发明中，M的尺寸很小，常常是|M|＝2。

ElGamal加密系统在DDH假定下在语义上是安全的。

在ElGamal的(t，n)阈值版本中，1≤t≤n，计算加密w.r.t.公共的公钥h(如上所述)，同时在n方之间使用联合协议进行解密，每方具有共享私钥α＝log_gh。只要至少t方参加便可成功地解密，反之比t方少时将不能成功解密。这些方通过运行分布的密钥生成协议来实现他们的共享。

因为该发明特别有利于双方计算，在(2，2)阈值方案中介绍更多的细节。通过让各方P₁、P₂首先广播委托c_i＝g^α _ih^r _i，其中α_ir_i∈Z_q，i＝1，2，然后与认识log_gh_i的证据一起广播数值r_i，其中h_i＝c_i/h^r _i，i＝1，2。联合公钥是h＝h₁h₂，私钥是α＝α₁+α₂。为了解密加密(a，b)，参预者p_i与log_αd_i等于log_gh_i的证据一起产生d_i＝a^α _i。然后从b/(a₁a₂)中恢复该消息。

无疑(2，2)阈值ElGamal允许特别的使用。产生密钥的努力几乎与执行解密的努力相同。

假定2个同态的加密[[x]]、[[y]]，可以通过包含以下步骤的协议来计算同态的加密[[xy]]：

-参预者p_i选择一个随机数值r_i，并将[[r_i]]与其知道r_i的证据一起发送到参预者P_3-i，i＝1，2。

-各参预者共同解密[[x+r₁+r₁]]。

-让x₁＝x+r₂，x₂＝-r₂。参预者p_i将[[x_i]]，[[f_i]]＝x_i[[b]]与证据一起发送到参预者P_3-i，i＝1，2。

-两个参预者可以计算[[f₁]]+[[f₂]]＝[[xy]]。

如果任何证据失败则中断协议。

作为最后的预备步骤，显示Pedersen委托。假定g，h∈G，消息m∈Zq的委托是数值c＝g^mh^r，其中r∈_RZ_q。通过泄漏m和r来公开委托。在假定不能确定log_gh时，Pedersen的解决方案是无条件地隐藏和计算地约束。委托解决方案也是附加的同态，<<m>>将被用来表示对消息m的委托，其中抑制随机化。

依照这些预备步骤，如果f通过Z_q被表示为仅包含加法门电路和简单乘法门电路的电路，则可在多方设置中安全地评价函数f。加法门电路将加密[[x]]和[[y]]作为输入，产生[[x]]*[[y]]＝[[x+y]]作为输出，简单乘法门电路将[[x]]作为输入，产生[[x]]c＝[[cx]]作为输出，对于公共的已知数值c∈Z_q。然而，为了能处理任何函数f，对两个输入都被加密的情况则需要更多的通用乘法门电路。

如果对x或y没有限制，则在假定DH问题不可行的情况下不存在这种将[[x]]和[[y]]作为输入，并有效地产生[[xy]]作为输出的乘法门电路。因此，使用特殊的乘法门电路，对乘数x施加一些限制。

在本发明的第一实施例中，该方法要求乘数x是专有的，这意味着它只为单一一方所知。

在本发明的第二实施例中，该方法包括使用特殊的乘法门电路。这个被称作条件门电路的门电路要求乘数x来自二分(二值)域。这个协议将被称作具有共享二分乘数的乘积协议。这个协议较少通用，但是比已知的那些协议更加有效。

尽管有这些限制，但依照本发明的方法还是产生了非常有效的多方协议。

首先，在依照本发明的第一实施例介绍的乘积协议中乘数x是一个专有输入(而不是共享输入)。也就是说，只有单一一方p知道x的值。在被乘数y上没有限制。有专有乘数的乘法作为在条件门电路的协议和许多分离的其他协议中的子协议发生。

图1举例说明本发明的两个不同实施例。一方P，100获得专有第一数据[[x]]，101和加密的第二数据[[y]]，102，计算加密的输出数据[[xy]]，103，包括正确性证据104。获取的方式可以是从不同的一方接收，从内部存储器查找或者内部产生。

假定加密[[x]]＝(a，b)＝(g^r，g^xh^r)和[[y]]＝(c，d)，其中一方P知道r、x，一方P自己使用同态性能计算随机化的加密[[xy]]＝(e，f)＝(g^s，h^s)*[[y]]^x，其中s∈_RZ_q，。然后一方P广播[[x]]和显示这是正确输出的证据，这意味着证明认识到证人r；s；x∈Zq满足a＝g^r，b＝g^xh^r，e＝g^sc^x，f＝h^sd^x。

在后面的使用中需要模拟上述协议。模拟器得到输入[[x]]和[[y]]，正确的输出加密[[xy]]，但是它不知道x。结果是，模拟器只需要增加模拟的认识的证据。模拟的抄本统计上难以与真实抄本区分。

还可以使用上述协议的变型，其中专有乘数x同时与几个被乘数yi相乘。此外，通过对乘数使用Pedersen委托<<x>>＝g^xh^r代替ElGamal加密[[x]]＝(g^r，g^xh^r)进行细微的优化。

在本发明的第二实施例中，条件门电路被用作特殊乘法门电路类型，可以仅使用标准同态阈值ElGamal加密以令人吃惊的简单和有效方式实现该特殊乘法门电路。因为加法门电路基本上是没有限制的，条件门电路不仅允许构造用于任何函数的电路，而且事实上产生用于各种任务的有效电路。

出于解释的目的，二分域{-1，1}很方便。可以替换地使用域{0，1}或者任何其它域{a，b}，a≠b，因为这些域可以通过线性变换彼此转变。这些变换也可以被用于加密。

在两个不同的协议中举例说明条件门电路。

在第一个协议中为了实现条件门电路，该协议使参预者p₁，...，p_N，N≥2，能够安全地计算[[xy]]。为简单起见，假定参预者也共享同态加密方案[[.]]的私钥。

在协议阶段1：对于i＝1...N，参预者P_i将[[x_i-1]]作为输入，选择s_i∈_R{-1，1}。参预者P_i使用用于具有专有乘数的乘法的协议广播加密[[S_i]]和[[S_ix_i-1]]，以及[[S_ix_i-1]]是正确的w.r.t.[[S_i]]如[[x_i-1]]的证据。让x_i＝s_ix_i-1。

在协议阶段2：参预者共同解密[[x_N]]以获得x_N。每个参预者检查x_N∈{-1，1}。给定x_N和[[y]]，公开地计算加密[[x_Ny]]。让z₀＝x_Ny。

在协议阶段3：i＝1...N，参预者P_i将[[Z_i-1]]作为输入，使用用于具有专有乘数的乘法的协议广播加密[[S_iZ_i-1]]，和[[S_iZ_i-1]]是正确的w.r.t.[[S_i]]和[[[Z_i-1]]的证据。让z_i＝s_iz_i-1。

协议的输出是[[z_N]]＝[[xy]]。该协议只要求单个阈值的解密。因为必须保持X_N∈_R{-1，1}，对于同态ElGamal加密解决方案来说，解密是可行的。该协议粗略地需要2N圈(rounds)。

因为如果至少t＝N/2个可靠的参预者能够成功地完成协议，则x_N的数值是统计上独立的，x_N的数值不会泄漏任何关于x的信息。

任选地，可以将该协议处理成鲁棒的。如果在协议阶段2参预者P_i失败，则在协议剩余部分简单地将其丢弃。对于阶段2，根据定义联合解密步骤是鲁棒的。如果检查x_N∈{-1，1}失败，则要求参预者广播s_i∈{-1，1}的证据。不能提供正确证据的参预者被丢弃并且解密他们的s_i数值。由此调节X_N的数值。类似地，在阶段2，如果参预者Pi不能完成它的步骤，它的数值S_i被解密并且公开地计算加密[[S_iZ_i-1]]。

这个协议是正确的、可靠的和计算的(computational)zk。

在第二实施例的第二个协议实施中，再一次使用二分域{-1，1}，但是可以任何不同的域来代替使用线性映射。

让[[x]]、[[y]]表示加密，x∈{-1，1}Z_q，y∈Z_q。下面的协议使各方P₁...P_n，n＞1能够安全地计算加密[[xy]]。为简单起见，假定这些方也共享(t+1；n)阈值方案[[.]]的私钥，其中t＜n。该协议包括两个阶段。

协议阶段1。让x0＝x，y0＝y。i＝1...n，一方p_i依次将[[X_i-1]]和[[Y_i-1]]作为输入，广播委托<<S_i>>，S_i∈_R{-1，1}。然后P_i将专有乘数乘积协议应用到乘数<<S_i>>和被乘数[[X_i-1]]和[[Y_i-1]]上，产生随机加密[[x_i]]和[[y_i]]，其中x_i＝s_ix_i-1，y_i＝s_iy_i-1。如果P_i没能成功地完成它的步骤，则被立即丢弃。

协议阶段2。用户共同解密[x_n]]以获得x_n。如果因为正确的共用部分数量不够而导致解密失败，那么中断全部协议。如果因为x{-1，1}而导致解密失败，则要求每方P_i广播S_i∈{-1，1}的证据。不能这么做的各方被丢弃，并且重新开始协议(再次在阶段1开始)。给定x_n和[[y_n]]，公开计算如密[[x_ny_n]]。如果所有方都可靠，则x_ny_n＝xy。

任何一方都可以通过在范围{-1，1}之外挑选数值S_i来干扰协议中阶段1的最多一个运行。对于t＜n/2、协议是鲁棒的，整体允许总共t个失败的各方(如同阈值解密步骤容忍直至t个失败的各方一样)。对于n/2≤t＜n，协议不是鲁棒的，但是对手在这种情况下不能得到好处。

该协议只需要单个阈值解密。因为必须保持X_N是二值的，对于同态ElGamal加密解决方案来说解密是可行的。由于x_n的值在统计上是独立于x的，所以x_n的值不会泄露任何关于x的信息。

如果各方的总数与将要被估计的条件门电路的总数相比较大，则保证鲁棒的替换方法是让用户在阶段1使用加密[[S_i]]代替委托<<s_i>>。此外，如果在阶段2，x_n{-1，1}，要求所有各方证明S_i∈{-1，1}。失败的各方被丢弃，并且解密他们的S_i值以校正x_n的值。

用通信复杂度(以比特方式)和环绕复杂度(round complexity)来确定协议的性能。在阶段1，每方应用专有乘数乘积协议，广播大约10个数值。对于解密，每方最多广播3个数值。因此，通信复杂度为O(nk)，其中隐藏的常数是非常小的。通常，环绕复杂度为O(n)时这个数值是高的，但是在双方计算的情况下，它是O(1)。此外，当并行估计多个条件门电路时，一个用户可以利用这样的事实，即可以任意选择各方P₁...P_n执行条件门电路协议的阶段1的顺序。

作为条件门电路的第一个应用，显示异或同态的ElGamal加密方案。假定使用一次阈值解密、按照以下步骤计算[[X]]和[[y]]，x，y∈{0，1}，[[xy]：

步骤1：公开地将[[X]]转换为[[x′]]，x′＝2x-1∈{-1，1}。

步骤2：将条件门电路应用到[[X′]]和[[y]]以获得[[x′y]]。

步骤3：公开地计算[[x-x′y]]，它等于[[xy]。

条件门电路的应用需要阈值解密，对于完成异或同态的ElGamal加密，这似乎是不可避免的。

每方的工作非常有限，对于每个条件门电路大约13次取幂。相反，依照US专利中提到的混合匹配方法则要求每方以可检验的方式混合4行xy的真值表(混合步骤，构造入口需要24次取幂，正确性证据需要6×12次取幂(使用J.Groth的有效协议，“A verifiable secret shuffleof homomorphic encryptions，public key cryptography PKC’03”，计算机科学讲稿中的卷2567，页145-160，柏林，2003年，Springer-Verlag)，平均执行4次明码文本等同性测试以找到给定[[x]]和[[y]]的[[xy]](匹配步骤，需要4×7次取幂)。因此，条件门电路大约提供10倍的改进的计数取幂。

作为条件门电路的第二个应用，显示逻辑门电路的实现。

任何关于两个比特x和y的运算符都可以用唯一的方式表示为以下形式的多项式：α₀+α₂x+α₂y+α₃xy。系数不必是二进制的。例如，异或运算符满足xy＝x+y-2xy。正好存在16个类型{0，1}²→{0，1}的多项式，如果一个多项式考虑下面的正常形式：b₀xy+b₁x(1-y)+b₂(1-x)y+b₃(1-x)(1-y)，则该多项式是紧接的(immediate)，其中系数为二进制。通常，如果在其它像{-1，1}这样的二值域工作时系数也不必是整数。

在条件门电路的以下应用中，用特殊的乘法门电路获得用于诸如整数比较和二进制表示的数加法这样的基本操作的有效电路。

作为条件门电路的第三个应用，所显示的对姚的百万富翁问题的细微变形的有效解决方案是允许扩展为更普通的情况。在这个应用中，由他们的二进制表示，即x＝(x_n-1，...，x₀)和y＝(y_n-1，...，y₀)分别给出输入。通过Z定义实现符号函数多元多项式p。

可以使用几个多项式来实现这个函数。看来，根据下面的多元减多项式(multivariate reduction polynomial)可以构造最有效的解决方案：对于x，y∈{0，1}，F(s，x，y)＝s+(1-s²)(x-y)。通过引进辅助变量v＝1-s²可以有效地估计多项式。最初，s＝0，v＝1。然后，对x和y的所有分量重复计算s，v＝s+v(x-y)，v-v(x-y)²，给出想要的结果。表达式v-v(x-y)²可以作为v(1-x+2xy-y)计算。为了用专有方式进行这个计算，需要三个基本步骤，其中参预者用它的x或y与给定的同态加密相乘。

-参预者1根据[[v]]和((x))计算[[vx]]。

-参预者2分别根据[[v]]、[[vx]]和((y))计算[[vy]]和[[vxy]]。

-两个参预者可以计算[[s+vx-vy]](这是新的s)。

-两个参预者计算[[v-vx+2vxy-vy]](这是新的v)。

如果需要，可以使用阈值解密对s进行解密。注意到，这个算法需要对每个比特进行三次“具有专有乘数的乘法”协议。可以有效地执行算法中的第二步。这个方法还可以用于社会主义(socialist)的百万富翁问题以产生加密形式的结果。

示出了作为条件门电路的第四个应用是两个数字的加法。为了相加由他们的二进制表示给出的两个数x、y，相加各个位，同时考虑进位。为了产生输出z的下一位，必须计算[[t]]＝[[x_i+y_i+c_i-1]]，其中c_i-1为进位值。保持z_i＝t mod 2，c_i＝[t/2]。计算为z_i＝x_i+y_i+c_i-1-2x_iy_i-2x_ic_i-1-2y_ic_i-1+4x_iy_ic_i-1和c_i＝x_iy_i+x_ic_i-1+y_ic_i-1-2x_iy_ic_i-1。如果x和y都是专有的，则可以使用“简单”乘积协议计算所有这些项。每一位的计算都需要4个这样的乘法。所以，使用n个环绕合计为O(n)。如果只有一个是专有的，则需要一次二分乘法。如果两个是共用的，在一直使用二分乘法。

类似地，通过学校方法完成数字x、y的乘法。这需要O(n²)的位乘法。

作为条件门电路的第五个应用是汉明(Hamming)间距的计算。给定两向量x和y有在Z_q的入口，在x和y之间的汉明间距d_H(x，y)被定义为 $d_H(x,y)=\underset{n-1}{\overset{n}{\mathrm{\&Sigma;}}}\mathrm{\&delta;}(x_i-y_i),$ 其中如果x＝0，则δ(x)＝0，如果x≠0，则δ(x)＝1。这部分的目的是安全地计算x和y之间的汉明间距，不泄露关于x和y的任何进一步的信息。更确切地说，假定两个参预者P₁和P₂，每个参预者分别有一个叫做x和y的向量。他们想通过执行双方协议来计算d_H(x，y)。向量x的第i个入口表示为x_i∈Z_q。可以通过下面的表示： $x_i=\underset{j=0}{\overset{m}{\mathrm{\&Sigma;}}}{x}_{\mathrm{ij}}{2}^j$ 将入口x_i表示为二进制串。使用变量h进行等同性测试。

在协议的最后，P₁和P₂解密h。在这个协议中的不变量是 $h=\mathrm{\&delta;}\underset{k=0}{\overset{j}{\mathrm{\&Sigma;}}}{(x_k-y_k)}^2.$ 为了计算d_H(x，y)，必须对向量x和y的每一个入口x_i、y_i执行上面定义的协议。用h_i表示入口i的输出量。然后， $\left[\right[d_H(x,y)\left]\right]=\left[\right[\underset{i}{\mathrm{\&Sigma;}}{h}_i\left]\right]=\underset{i}{\mathrm{\&Pi;}}\left[\right[h_i\left]\right].$ 然后两个参预者共同解密[[d_H(x，y)]]。

示出了作为条件门电路的第六个应用的欧几里得距离的计算。与汉明间距计算的差异存在于相似性的测量。对于长度为n的两个向量x和y，欧几里得距离d_E(x，y)被定义为 $d_E(x,y)=\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}{(x_i-y_i)}^2.$ 为了计算的d_E(x，y)，参预者执行下面的步骤：

-参预者1根据它对x_i的认识为所有i＝1，...，n计算[[x_i ²]]。类似地参预者2为所有i＝1，...n计算[[y_i ²]]。

两个参预者都计算 $\left[\right[O_i\left]\right]=\left[\right[x_i^2-2x_i{y}_i+y_i^2\left]\right].$ 因此参预者1向参预者2发送[[x_i]]，参预者2然后计算[[2x_iy_i]](与她使用正确的y_i的证据一起，即与她在y_i ²的计算中使用的证据相同)。然后他们计算 $\left[\right[{x_i}^2-2x_i{y}_i+{y_i}^2\left]\right].$

-最后，他们通过利用加密方案的同态性能： $\left[\right[d_E(x,y)\left]\right]\underset{i=1}{\overset{n}{\mathrm{\&Pi;}}}\left[\right[O_i\left]\right]=\left[\right[\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}{O}_i\left]\right]$ 来计算[[d_E(x，y)]]。

-通过使用公平的阈值解密得到结果。

此外，考虑这个计算的阈值版本，即，对于某个阈值μ，一个(或者两个)参预者只得到判定问题d_E(x，y)＞μ的答案的情况。在那种情况，两个参预者必须使用他们输入的二进制表示，以二进制表示计算输出[[O_i]]的值。然后，通过使用与之前解释的方法相同的方法计算

的二进制表示。然后，他们执行“百万富翁”协议以获得加密的结果。最后，他们使用公平阈值解密向两个参预者揭示解决方案。

示出了作为条件门电路的第七个应用的另一个公知的用于比较两个向量的相似性测量，归一化标量积被定义为 $<x,y>=\left(\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}{x}_i{y}_i\right)/\left(\right|\left|x\right|\left|\right|\left|y\right|\left|\right),$ 其中 $\left|\right|x\left|\right|=\sqrt{}\left(\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}{x}_i^2\right).$ 由于数据x、y是专有的，可以由各个参预者秘密计算数1/‖x‖和1/‖y‖。可以使用ElGamal加密方案的同态性能计算和

再次使用同态性能，可以获得<x，y>。最后，通过应用(公平)阈值解密和扩展P-A技术来获得数值。Fouque，J.Stern，G-J.Wackers，处理ElGamal情况的有理数的“CryptoComputing with rationals”，财务密码学，2001年。

为了解决有关的判定问题，即对某个明确定义的阈值μ来说，是否<x，y>＞μ，必须如之前解释那样以用二进制表示进行所有的计算。此外由于0≤μ≤1，显然有利于解决下面有关的判定问题：

(1/μ)Σx₁y₁≥‖x‖‖y‖。然后，必须应用“百万富翁”协议。最后通过应用(公平)阈值解密获得结果。

为了举例说明本发明的广泛适用性，显示条件门电路的第八个应用：安全拍卖。

拍卖由两个阶段：投标阶段，在这段时间参与者向拍卖人发出他们的出价，公开阶段，在此期间拍卖人宣布最高价格和优胜者的身份。

假定以下的模型。有m个投标者P_i，...，P_m。用x₁＝x_1，n-1，...，x_1，0)₂，...，x_m＝(x_m，n-1，...，x_m，0)₂给出出价。在这个符号表示法中，表示是从msb到lsb的顺序。投标者用服务器的公共公钥加密他们的出价，并发送到拍卖人；[[x_i]]＝[[x_i，n-1]]，...，[[x_i，1]]。有K个服务器。将描述关于最高价格拍卖的方法。

介绍一种用于确定最高投标者身份的算法。服务器使用这个算法来安全地确定最高投标者的最高出价和身份。在这之前，定义了一组n+1个选择向量w_i∈{0，1}^m，i＝-1，...，n-1，跟踪直至位i的最高投标者的身份(从msb开始)。该算法从向量w_n-1开始，最高投标者的身份包含在向量w_-1中。为了给出将w_i更新到w_i-1的动态，定义了第二组向量t_i∈(0，1)^m+1，i＝0，...，n-1。向量t_i检查向量x_jw_j是否等于零失量。向量w_i，t_i的第j个分量用w_j，i，t_j，i表示。用t_0j＝0，j＝0，...，n-1给出t向量的初始条件，W_n-1＝(1，...，1)给出w向量的初始条件。多项式定义为：F(s，z)＝s+(1-s)z和G_α(s，z)＝s(z+(1-z)(1-α))。然后通过下面的更新规则定义动态：t_j，i＝F(t_j-1，i，x_j，iw_j，i)，

t_m，i＝F(...F(F(t_0i，x_1iw_1i)，x_2iw_2i)...)，以及 $w_{j,i-1}=G_{i_{m,i}}(w_{j,i},x_{j,i}),$ i＝n-1，...，0，从i＝n-1开始，对于每个i来说，计数器j从1运行到m。注意到，t_mi＝1意味着向量x_jw_j的至少一个分量等于1。为了安全地计算向量W_-1，服务器在条件门电路的基础上使用广义的百万富翁协议。

当已经安全地计算了向量w_-1，服务器使用公平阈值解密来解密向量w_-1的入口。获胜的投标者的身份对应w_-1入口的位置，w_-1等于1。使用这个标识符，他们可以发现对应的最高出价，并使用阈值解密将其解密。

这个协议满足与Juels和Jakobsson在上述US专利中用公式表达的相同的优点，特别是它满足：非交互性、拍卖适应性、完全保密、鲁棒性、多个服务器和公众可验证性，同时它避免了计算上相对昂贵的混合计算。

这个协议可以被扩展到Vickrey(第二-价格)拍卖。Vickrey拍卖是一种最高投标者胜出，但是清除价格，即获胜者必须支付与第二最高出价相同的价格的拍卖。为了执行Vickrey拍卖，可能进行以下方法。首先，服务器通过上述协议确定优胜者的身份(而不是获胜出价)。然后，他们从列表中删除获胜者和他们的出价。最后，他们估计下面的多项式组，p_j＝F(...F(F(0，x_1jw_1j)，x_mjw_mj)，j＝n-1，...，0，其中按上文的描述定义F。然后，向量p＝(p_n-1，...，p₀)包含最高的出价。

最后显示两个使用专有乘数乘积协议的应用。第一个应用是广义的百万富翁问题。

在百万富翁问题中，各自的输入x和y对于参预者都是专有的。然而在许多应用中(例如安全简档匹配)一个或者两个输入将被共享。如果只一个输入x被共享，在算法的一些步骤中仍使用具备专有乘数协议的乘法。对于百万富翁算法来说，这产生了2n个专有乘数协议和n个二分乘积协议。然而如果两个输入都被共享，则必须在所有步骤中使用二分乘积协议，引起二分乘积协议的3n次使用。

如果一个输入x被共享，而另一个输入是已知常数T，则可能有以下的协议。用T_j代替y_j，对于j＝0，...，n-1，通过使用加密方案的同态性能计算{[[x_j-T_j]]}，j＝0..n-1。以这种方式将该问题转变成不等式x-T＞0。然后，只需用二分乘积协议进行[[v(x_j-T_j)]]的计算(导致n个二分乘法)。

作为第二个应用显示的是安全简档匹配。

近年来，大量以电子形式出现的内容(音频、视频、文本等)对用户的可用性要求发展信息选择方法。这种方法绝大部分是基于个性化的思想，其中特定的用户依照用户偏爱简档选择信息。这种系统通称为推荐系统。

合作过滤技术是推荐系统，其中根据给定用户的简档和其他用户简档(不在内容本身的属性中)之间的相似性推荐内容。如果任何两个简档之间的相似性量度足够高(依照一些预定的标准)，则该系统可以向一个用户推荐另一个用户非常欣赏的内容项目，该项目还没有被第一个用户看到。

这里这个设置被扩展到特殊的情况，两个用户可以比较他们的简档，并且找出他们是否具有类似的爱好。如果有类似的爱好，他们可以开始一段处理程序以彼此交换内容。否则，该协议保证除了简档不相似的事实之外，不泄露其他的专有信息。

通过两个简档的秘密比较，意味着该用户安全地计算了预先协商的测试函数。在第二阶段，他们安全地比较这个(加密)的数值与阈值；即，在协议的最后，参预者得到的唯一认识就是测试函数的数值是否超过了阈值。

假定参与者彼此有一个认证(authenticated)通道。为了清楚起见，该描述局限于这种情况，即用户的专有简档由表示为x和y的二进制向量组成，但是也可能扩展到非二进制向量。

用两个向量中的不同入口的数目给出比较两个向量的第一量度。可以按照两个向量x，y∈{0，1}ⁿ之间的汉明间距d_H(x，y)定义这个量度，用 $d_H(x,y)=\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}\mathrm{\&delta;}(x_i-y_i)$ 给出，其中如果x＝0，则δ(x)＝0，如果x≠0，则δ(x)＝1。认为第二量度将是用 $d_S(x,y)=\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}{x}_i{y}_i$ 定义的标量积。这个部分的目的是显示如何计算d_H(x，y)和d_S(x，y)，以及如何以秘密方式与阈值比较。

通过运行专有乘数乘积协议以及使用阈值解密来解密结果以执行d_H(x，y)的秘密计算。d_S(x，y)的秘密计算也是基于专有乘数乘积协议和ElGamal加密系统的同态性能。

当必须用秘密方式解决由一个或者两个参预者选择的阈值μ的判定问题d_H(x，y)＞μ或者d_S(x，y)＞μ时，出现了更有趣的情况。假定用μ的二进制表示μ_n-1，...，μ₀定义μ。下一个协议解决d_H(x，y)的判定问题，而d_S(x，y)的情况完全相似，因此忽略其细节。

-首先，参预者使用密钥生成协议建立阈值ElGamal系统。

-对于每个分量i＝1，...，n，两个参预者使用在百万富翁问题的部分描述的“社会主义”协议来安全地计算[[O_i]]＝[[δ(x_i-y_i)]]，或者通过使用专有乘数乘积协议计算[[O_i]]＝[[(x_i-y_i)²]]。

-他们秘密地计算 $\left[\right[s\left]\right]=\left[\right[\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}{O}_i\left]\right]$ 的位表示。

结果参预者获得([[s_n-1]]，...，[[s₀]])₂； 的二进制表示。

-参预者对[[s]]和[[μ]]执行百万富翁协议以检查是否[[s]]]＞[[μ]]。

-最后，他们应用(公平)阈值解密以解密判定问题的结果。

这个协议要求对每个参预者用O(nlog n)次取幂。

上述方法可以被扩展到入口属于离散(位，而不是二进制)域的情况。思想是相同的，但是计算需要更多的步骤和细节。强调的是在那种情况下可以保证秘密。

图2举例说明用于实现依照本发明的方法的设备的计算机程序产品。

设备200包括内存201、处理装置202、输入装置203和输出装置204，它们被安排为实现依照本发明的方法。

计算机程序产品210在被加载后可以执行指令，该指令引起设备200中的可编程设备执行实现依照本发明的方法所必需的步骤。

注意到上述的实施例仅是为举例说明，而不是限制本发明，在不脱离附加的权利要求的范围内，本领域的技术人员将能够设计许多替换的实施例。

在权利要求中，任何放在括号内的参考符号不认为是限制权利要求。单词“包括”不排除存在除权利要求中列出的元件或者步骤之外的元件或者步骤。在元件之前的单词“一”和“一个”不排除存在多个这种元件。本发明可以通过包含几个清楚元件的硬件，以及通过被适当编程的计算机来实现。单个处理器或者其他(可编程的)单元也可以完成权利要求中描述的几个装置的功能。

在列举了几个装置的产品权利要求中，这些装置中的几个装置可以具体表现为一个装置，也可以是相同的硬件部件。仅仅用在相互不同的从属权利要求中描述的某些测量的事实不指表示不可以使用这些测量的组合受益。

Claims (9)

1.一种用于一方参加多个参与者之间的安全多方乘积协议的方法，该协议被安排为计算专有第一数据和加密的第二数据的乘积，其中该协议包括含有以下步骤的子协议：

-所述一方(100)获得第一数据(101)，该数据是专有第一数据或者是来自二值域的第一数据，

-所述一方获得加密的第二数据(102)，

-所述一方使用基于离散对数的加密系统计算加密的输出数据(103)，该数据包括第一数据和第二数据乘积的随机化加密，以及

-所述一方产生被安排为显示加密输出数据正确的证据(104)。

2.依照权利要求1的方法，其中第一数据是来自二值域的随机数据。

3.依照权利要求1的方法，其中基于离散对数的加密系统是ElGamal加密系统。

4.依照权利要求1的方法，其中加密的数据是Pederson委托。

5.依照权利要求1的方法，其中该协议进一步包括所述一方向至少一个其他参与者发送证据的步骤。

6.依照权利要求1的方法，其中该协议进一步包括所述一方向至少一个其他参与者发送加密的输出数据的步骤。

7.依照权利要求1的方法，其中在双方之间执行协议。

8.一种被安排为实现依照权利要求1的方法的设备(200)。

9.一种计算机程序产品(210)，用于使能多方计算，其具有引起可编程设备执行依照权利要求1的方法的计算机可执行指令。

Images