简易求特征值与特征向量的安全多方计算协议

刘镇

摘 要：罗文俊等利用安全两方和多方矩阵乘积协议，给出了求解矩阵特征值的安全多方矩阵计算协议，协议频繁使用了安全两方矩阵乘积协议，不但协议过程复杂，计算效率也很低。利用矩阵求和的安全多方计算协议，给出了新的求解矩阵特征值的安全多方矩阵计算协议，协议过程简单，计算效率很高。在某些资源受限的网络环境中，该协议有重要应用。

关键词：密码协议；安全多方计算；矩阵分解；两方矩阵乘积协议

0 引言

多方安全计算就是拥有秘密输入的多方，希望用各自的秘密输入共同计算一个函数，计算要求每方都能接收到正确的输出（正确性），并且每方只能了解自己的输出（保密性）。

研究特殊的多方安全计算问题，已经成为多方安全计算研究的一个新的重要内容，美国普渡大学的Du博士在他的学位论文[1，2]中，已经研究、总结了一些值得研究的两方安全计算问题。罗文俊等在文献[3]中研究了在科学计算方向上Du博士提出的矩阵乘积的安全多方计算问题，并应用该协议给出了解线性方程组，计算特征值问题的安全多方计算协议，两协议频繁的使用了安全两方矩阵乘积协议，不但协议本身较为复杂，计算效率也很低。

安全多方求和协议[4]是安全多方计算的一个基本操作，它同样适用于矩阵的求和，本文利用安全多方矩阵求和协议，给出了简单高效的求特征值和特征向量的安全多方计算协议。

1 准备知识

安全多方矩阵求和协议[4]

假設有k个用户参与计算，每个用户只有自己的私有

数据xi，他们共同希望计算，但任何一个用户都不愿意向其他用

户泄露自己的私有输入xi，

安全多方求和算法是安全多方计算的一个基本操作，基于秘密共享技术的安全求和协议描述由参考文献[9]给出。该协议思想为：m个参与计算的用户pi各自将自己的私密数据xi随机分成m份，

，每个用户pi只分别发送各自生成的xij，给相应的pj，每个用户收到所有数据各自在本地进行计算部分和并向所有用户广播计算结果，最后每个用户只各自在本地根据广播数据再次进行求和计算，得结果

。由于协议要求的特殊性，任意一方都得到相同的和，所以

该协议只能容忍k-2方合谋。

如果每个参与计算的用户pi各自将自己的私密数据xi都是一个同型的矩阵，上述协议就成了安全多方矩阵求和协议，它是一个可以容忍k-2方合谋的协议。

2 求线性方程组、特征值与特征向量的安全多方计算问题

2.1 多方安全求特征值与特征向量问题

多方安全求特征值与特征向量问题：A1有一个矩阵m1；…；An有一个矩阵mn；是维矩阵。不泄露他们各自的保密输入，要共同求矩阵的特征值与特征向量。

下面我们给出协议：

2.2 多方安全求解特征值与特征向量协议

输出：得到矩阵的特征值λ和对应的特征向量X。

协议过程：

Step1 分别用运行安全多方矩阵求和协议，分别得到矩阵（其中为阶的方阵， ），满足。

Step2 各自求解矩阵的特征值与对应

的特征向量X。

3 协议分析

3.1 保密性

两协议的保密性都建立在安全多方矩阵求和协议的基础上，同安全多方矩阵求和协议一样，它也是一个能容忍n-2方合谋攻击的协议。

3.2 计算复杂性

两协议都只用到了安全多方矩阵求和协议，而安全多方矩阵求和协议只涉及到矩阵的加法运算，计算效率很高，文献[3]中的协议均用到安全多方矩阵乘积协议和多次用到安全两方矩阵乘积协议，同文献[3]中的协议相比，本文的协议效率大大提高。

4 小结

研究特殊领域的安全多方计算问题，是安全多方计算的重要内容，文献[3]中利用安全两方和多方矩阵乘积协议，给出了解线性方程组合求解特征值的安全多方计算协议，两协议使用两方矩阵乘积协议，计算效率很低。本文利用安全多方矩阵求和协议，给出了新的求解线性方程组解的安全多方计算协议和求解特征值和特征向量的安全多方计算协议，两协议只能容忍最多n-2方合谋攻击，安全性略低于文献[3]中的协议，但是两协议过程简单，计算效率很高，在某些对安全性要求不是很高，对效率要求很高的资源受限环境中有重要应用。

参考文献

[1] Chor B.， Gilboa N.. Computationally private information retrieval（extended abstract）. In： Proceedings of the 29th ACSymposium on Theory of Computing， El Paso， Texas， USA， 1997， 304～313

[2] Du Wenliang， Atallah M. J.. Privacy-preserving cooperative scientific computations. In： Proceedings of the 14th IEEEComputer Security Foundations Workshop， Nova Scotia， Cana-da， 2001， 273～282

[5]罗文俊，李祥. 多方安全矩阵乘积协议及应用[J].计算机学报， 2005，28（7）：1230-1235.

[9] D.Boneh. EfficieniGenerationofSharedRSAKeyS[J]. JoumaloftheACM，48（4），2001.PP.702-722.