簡易求特征值與特征向量的安全多方計算協(xié)議

劉鎮(zhèn)

摘 要：羅文俊等利用安全兩方和多方矩陣乘積協(xié)議，給出了求解矩陣特征值的安全多方矩陣計算協(xié)議，協(xié)議頻繁使用了安全兩方矩陣乘積協(xié)議，不但協(xié)議過程復(fù)雜，計算效率也很低。利用矩陣求和的安全多方計算協(xié)議，給出了新的求解矩陣特征值的安全多方矩陣計算協(xié)議，協(xié)議過程簡單，計算效率很高。在某些資源受限的網(wǎng)絡(luò)環(huán)境中，該協(xié)議有重要應(yīng)用。

關(guān)鍵詞：密碼協(xié)議；安全多方計算；矩陣分解；兩方矩陣乘積協(xié)議

0 引言

多方安全計算就是擁有秘密輸入的多方，希望用各自的秘密輸入共同計算一個函數(shù)，計算要求每方都能接收到正確的輸出（正確性），并且每方只能了解自己的輸出（保密性）。

研究特殊的多方安全計算問題，已經(jīng)成為多方安全計算研究的一個新的重要內(nèi)容，美國普渡大學(xué)的Du博士在他的學(xué)位論文[1，2]中，已經(jīng)研究、總結(jié)了一些值得研究的兩方安全計算問題。羅文俊等在文獻(xiàn)[3]中研究了在科學(xué)計算方向上Du博士提出的矩陣乘積的安全多方計算問題，并應(yīng)用該協(xié)議給出了解線性方程組，計算特征值問題的安全多方計算協(xié)議，兩協(xié)議頻繁的使用了安全兩方矩陣乘積協(xié)議，不但協(xié)議本身較為復(fù)雜，計算效率也很低。

安全多方求和協(xié)議[4]是安全多方計算的一個基本操作，它同樣適用于矩陣的求和，本文利用安全多方矩陣求和協(xié)議，給出了簡單高效的求特征值和特征向量的安全多方計算協(xié)議。

1 準(zhǔn)備知識

安全多方矩陣求和協(xié)議[4]

假設(shè)有k個用戶參與計算，每個用戶只有自己的私有

數(shù)據(jù)xi，他們共同希望計算，但任何一個用戶都不愿意向其他用

戶泄露自己的私有輸入xi，

安全多方求和算法是安全多方計算的一個基本操作，基于秘密共享技術(shù)的安全求和協(xié)議描述由參考文獻(xiàn)[9]給出。該協(xié)議思想為：m個參與計算的用戶pi各自將自己的私密數(shù)據(jù)xi隨機(jī)分成m份，

，每個用戶pi只分別發(fā)送各自生成的xij，給相應(yīng)的pj，每個用戶收到所有數(shù)據(jù)各自在本地進(jìn)行計算部分和并向所有用戶廣播計算結(jié)果，最后每個用戶只各自在本地根據(jù)廣播數(shù)據(jù)再次進(jìn)行求和計算，得結(jié)果

。由于協(xié)議要求的特殊性，任意一方都得到相同的和，所以

該協(xié)議只能容忍k-2方合謀。

如果每個參與計算的用戶pi各自將自己的私密數(shù)據(jù)xi都是一個同型的矩陣，上述協(xié)議就成了安全多方矩陣求和協(xié)議，它是一個可以容忍k-2方合謀的協(xié)議。

2 求線性方程組、特征值與特征向量的安全多方計算問題

2.1 多方安全求特征值與特征向量問題

多方安全求特征值與特征向量問題：A1有一個矩陣m1；…；An有一個矩陣mn；是維矩陣。不泄露他們各自的保密輸入，要共同求矩陣的特征值與特征向量。

下面我們給出協(xié)議：

2.2 多方安全求解特征值與特征向量協(xié)議

輸出：得到矩陣的特征值λ和對應(yīng)的特征向量X。

協(xié)議過程：

Step1 分別用運(yùn)行安全多方矩陣求和協(xié)議，分別得到矩陣（其中為階的方陣， ），滿足。

Step2 各自求解矩陣的特征值與對應(yīng)

的特征向量X。

3 協(xié)議分析

3.1 保密性

兩協(xié)議的保密性都建立在安全多方矩陣求和協(xié)議的基礎(chǔ)上，同安全多方矩陣求和協(xié)議一樣，它也是一個能容忍n-2方合謀攻擊的協(xié)議。

3.2 計算復(fù)雜性

兩協(xié)議都只用到了安全多方矩陣求和協(xié)議，而安全多方矩陣求和協(xié)議只涉及到矩陣的加法運(yùn)算，計算效率很高，文獻(xiàn)[3]中的協(xié)議均用到安全多方矩陣乘積協(xié)議和多次用到安全兩方矩陣乘積協(xié)議，同文獻(xiàn)[3]中的協(xié)議相比，本文的協(xié)議效率大大提高。

4 小結(jié)

研究特殊領(lǐng)域的安全多方計算問題，是安全多方計算的重要內(nèi)容，文獻(xiàn)[3]中利用安全兩方和多方矩陣乘積協(xié)議，給出了解線性方程組合求解特征值的安全多方計算協(xié)議，兩協(xié)議使用兩方矩陣乘積協(xié)議，計算效率很低。本文利用安全多方矩陣求和協(xié)議，給出了新的求解線性方程組解的安全多方計算協(xié)議和求解特征值和特征向量的安全多方計算協(xié)議，兩協(xié)議只能容忍最多n-2方合謀攻擊，安全性略低于文獻(xiàn)[3]中的協(xié)議，但是兩協(xié)議過程簡單，計算效率很高，在某些對安全性要求不是很高，對效率要求很高的資源受限環(huán)境中有重要應(yīng)用。

參考文獻(xiàn)

[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]羅文俊，李祥. 多方安全矩陣乘積協(xié)議及應(yīng)用[J].計算機(jī)學(xué)報， 2005，28（7）：1230-1235.

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