安全多方计算(Secure Multi-party Computation, SMPC)是密码学领域里一个基础性研究方向。借助于安全多方计算协议,网络上一些互不信任的实体能够以自己的秘密信息为输入共同完成预定的计算任务；计算完成以后,所有参与方得到自己期望的输出,并且不泄漏自己所输入的秘密信息。广义上说,任何密码学协议都可以看成是安全多方计算的特殊情况,因而安全多方计算可以视为密码学协议的一般性研究。能够完成任意计算的通用安全多方计算协议已经存在；这些通用协议从理论上说明任何多方计算都可以安全实现。但是这些通用协议的效率都非常低下,因而不可能在实际应用中使用。为了解决这个问题,我们致力于为特定的计算任务设计高效的安全多方计算协议；我们将探讨一些典型而重要的基础问题在安全多方计算背景下的协议实现及复杂度,这既是能够促进安全多方计算协议实用化的研究,又是一项具有重要理论意义的工作。大致来讲,安全多方计算的研究可以分为两种：基于秘密分享的安全多方计算和基于门限同态加密的安全多方计算。在基于秘密分享的安全多方计算中,协议是以线性秘密分享方案为基础的；协议的输入和(绝大部分)中间结果都被分享在参与方之间,以分享的方式参与运算。而在基于门限同态加密的安全多方计算中,协议是以(具有同态性的)Paillier公钥加密方案为基础的；协议的输入和(绝大部分)中间结果都处于加密状态,以密文的方式参与运算；而用来解密的私钥则使用门限秘密分享的方式分享在各参与方之间。我们主要关注的是基于秘密分享的安全多方计算；我们的工作中所使用的一些方法也可以被应用到基于门限同态加密的安全多方计算中,来设计一些功能类似的协议。在基于秘密分享的安全多方计算的研究中,通常假设所基于的秘密分享方案是建立在素域Zp上的,其中p是一个l比特长的素数(即ι＝[log p]。另外,对于域中的元素x=(xl-1,…,x1,x0)∈Zp,我们使用[x]p来表示对x的分享,而用[x]B来表示对x的按位分享(即对x的每个比特的分享)；也就是说,我们有我们的工作是以安全多方计算领域里一个重要工具“比特分解(Bit-Decomposition)"为基础的；此工具是由Damgard等人在TCC 2006上提出的。给出对x的分享,比特分解能够输出对x的按位分享。也就是说,我们有[x]B←Bit-Decomposition([x]p).借助于比特分解的帮助,我们可以为许多安全多方计算问题构造协议。具体说,一方面,借助于比特分解我们可以实现一些重要的布尔运算,如求一个分享的秘密值的海明重量或者求两个分享的秘密值的海明距离、按位异或等。另一方面,一些重要的、相对较复杂的算术操作也可以借助于比特分解来实现；下面列举的,是比特分解的4个主要应用：·比较分享的秘密值(Comparing Shared Values) [α]p<[b]p即在分享状态下,比较a、b的大小·测试分享的秘密值是否相等(Testing the Equality of Shared Values) [α]p=[6]p即在分享状态下,测试a、b是否相等·公开模归约(Public Modulo Reduction) [x mod m]p←Public-Modulo-Reduction([x]p,m)·秘密求幂(Private Exponentiation) [xαmod p]p<←Private-Exponentiation([x]p, [α]p)借助于比特分解,我们可以得到这些问题的输入的按位分享,然后我们就可以使用“分而治之”技术来解决这些问题。但是,有一个严重的问题是,比特分解的复杂度较高。具体说,比特分解的渐进交互复杂度是O(ιlogι)(l是输入值的比特长度),高于线性,这就使得所有借助于比特分解来实现的协议的交互复杂度都是高于线性的。在最近的一项工作中,Nishide等人为比特分解的其中两个重要应用,大小比较和相等测试,设计了避免使用比特分解来实现的协议；这两个协议的主要优势是其交互复杂度被降到了线性(即O(l))。那么,自然就出现一个公开问题：对于比特分解的另外两个重要应用,公开模归约和秘密求幂,是否可以得到类似的结论?在本文中,我们解决了此公开问题；我们证明,公开模归约和秘密求幂都可以避免使用比特分解来实现,而且协议的交互复杂度都可以被降到线性。为了解决公开模归约问题,我们首先给出了对比特分解的一个扩展。此扩展包含两个协议：m进制数位分解和m进制数位-比特-分解。输入一个秘密值x的分享,我们的m进制数位分解能够输出对x的所有m进制位的分享；而我们的数位-比特-分解则能够输出对x的所有m进制位的按位分享。而我们的线性公开模归约协议则基于以下事实：给出x的m进制形式,其中的最低m进制位的值就是(x mod m)。也就是说,要解决公开模归约问题(即己知[x]p和m,求[x mod m]p),我们只需提取x的最低m进制位；这正是我们所设计的避免使用比特分解的、具有线性交互复杂度的公开模归约协议所采取的做法。所以公开模归约协议可以看作是数位分解协议的一个简化。进一步地,我们还将前述的(对比特分解的)扩展进一步扩展到混合进制情形；而且更重要的是,作为对这个“进一步扩展”的简化,我们得到了一个效率更高的公开模归约协议。对于秘密求幂问题,本领域的研究者们普遍认为避免使用比特分解来解决此问题是不可能的,当然也就无法得到具有线性交互复杂度的协议。但是我们证明这一点是能够做到的。我们首先设计了一个协议,展示在求解此问题时如何避免对比特分解的调用从而得到线性协议；然后,我们又给出一个方法将此线性协议的复杂度大幅降低。我们最终得到的秘密求幂协议,其效率比已有协议要高得多。