1、简易求线性方程组的安全多方计算协议摘 要：罗文俊等利用安全两方和多方矩阵乘积协议，给出了解线性方程组的安全多方矩阵计算协议，协议频繁使用了安全两方矩阵乘积协议，不但协议过程复杂，计算效率也很低。利用矩阵求和的安全多方计算协议，给出了新的解线性方程组的安全多方矩阵计算协议，协议过程简单，计算效率很高。在某些资源受限的网络环境中，该协议有重要应用。 关键词：密码协议；安全多方计算；矩阵分解；两方矩阵乘积协议 0 引言 多方安全计算就是拥有秘密输入的多方，希望用各自的秘密输入共同计算一个函数，计算要求每方都能接收到正确的输出（正确性） ，并且每方只能了解自己的输出（保密性） 。 罗文俊等在文献3中研
2、究了在科学计算方向上 Du 博士提出的矩阵乘积的安全多方计算问题，并应用该协议给出了解线性方程组，计算特征值问题的安全多方计算协议，两协议频繁的使用了安全两方矩阵乘积协议，不但协议本身较为复杂，计算效率也很低。 安全多方求和协议4是安全多方计算的一个基本操作，它同样适用于矩阵的求和，本文利用安全多方矩阵求和协议，给出了简单高效的解线性方程组的安全多方计算协议 1 准备知识 1.1 安全多方矩阵求和协议4 假设有 k 个用户参与计算，每个用户只有自己的私有 数据 xi，他们共同希望计算，但任何一个用户都不愿意向其他用 户泄露自己的私有输入 xi， 安全多方求和算法是安全多方计算的一个基本操作，基
3、于秘密共享技术的安全求和协议描述由参考文献4给出。该协议思想为：m 个参与计算的用户 pi 各自将自己的私密数据 xi 随机分成 m 份， ，每个用户 pi 只分别发送各自生成的 xij，给相应的 pj，每个用户收到所 有数据各自在本地进行计算部分和并向所有用户广播计算结果，最后每个用户只各自在本地根据广播数据再次进行求和计算，得结果 。由于协议要求的特殊性，任意一方都得到相同的和，所 以该协议只能容忍 k-2 方合谋。 如果每个参与计算的用户 pi 各自将自己的私密数据 xi 都是一个同型的矩阵，上述协议就成了安全多方矩阵求和协议，它是一个可以容忍k-2 方合谋的协议。 2 求线性方程组的安
4、全多方计算问题 2.1 多方安全线性方程组问题 多方安全线性方程组问题：A1 有一个矩阵 m1 和一个向量b1；An 有一个矩阵 mn 和一个向量 bn；是维矩阵，是 N 维向量。不泄露他们各自的保密输入，要共同解线性方程组。下面我们给出协议： 2.2 多方安全解线性方程组协议 输入：A1 有一个矩阵 m1 和一个向量 b1；An 有一个矩阵 mn 和一个向量 bn；是维矩阵，是 N 维向量。 输出：得到向量 x，满足 。 协议过程： Step1 分别用和运行安全多方矩阵求和协议，分别得到矩阵和（其中 Ri 为阶的方阵，Si 为 N 维向量， ） ，满足， 。 Step2 各自求解方程组，得到
5、解向量 x。 3 协议分析 3.1 保密性 两协议的保密性都建立在安全多方矩阵求和协议的基础上，同安全多方矩阵求和协议一样，它也是一个能容忍 n-2 方合谋攻击的协议。 3.2 计算复杂性 协议都只用到了安全多方矩阵求和协议，而安全多方矩阵求和协议只涉及到矩阵的加法运算，计算效率很高，文献3中的协议均用到安全多方矩阵乘积协议和多次用到安全两方矩阵乘积协议，同文献3中的协议相比，本文的协议效率大大提高。 4 小结 研究特殊领域的安全多方计算问题，是安全多方计算的重要内容，文献3中利用安全两方和多方矩阵乘积协议，给出了解线性方程组合求解特征值的安全多方计算协议，两协议使用两方矩阵乘积协议，计算效率
6、很低。本文利用安全多方矩阵求和协议，给出了新的求解线性方程组解的安全多方计算协议和求解特征值和特征向量的安全多方计算协议，两协议只能容忍最多 n-2 方合谋攻击，安全性略低于文献3中的协议，但是两协议过程简单，计算效率很高，在某些对安全性要求不是很高，对效率要求很高的资源受限环境中有重要应用。 参考文献 1 Du Wenliang. A study of several specific secure two-party computation problemsPh.D. dissertation. Purdue University，USA， 2000 2 Cachin C.， Micali
7、 S.， Stadler M. Computationally private information retrieval with polyogarithmic communication. In：Proceedings of Eurocrypt99， Prague， Czech Republic， 1999，308318 3罗文俊，李祥. 多方安全矩阵乘积协议及应用J.计算机学报， 2005，28（7）：1230-1235. 4 D.Boneh. EfficieniGenerationofSharedRSAKeySJ. JoumaloftheACM，48（4） ，2001.PP.702-722.
