簡易求線性方程組的安全多方計算協議

劉鎮

摘 要：羅文俊等利用安全兩方和多方矩陣乘積協議，給出了解線性方程組的安全多方矩陣計算協議，協議頻繁使用了安全兩方矩陣乘積協議，不但協議過程復雜，計算效率也很低。利用矩陣求和的安全多方計算協議，給出了新的解線性方程組的安全多方矩陣計算協議，協議過程簡單，計算效率很高。在某些資源受限的網絡環境中，該協議有重要應用。

關鍵詞：密碼協議；安全多方計算；矩陣分解；兩方矩陣乘積協議

0 引言

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

羅文俊等在文獻[3]中研究了在科學計算方向上Du博士提出的矩陣乘積的安全多方計算問題，并應用該協議給出了解線性方程組，計算特征值問題的安全多方計算協議，兩協議頻繁的使用了安全兩方矩陣乘積協議，不但協議本身較為復雜，計算效率也很低。

安全多方求和協議[4]是安全多方計算的一個基本操作，它同樣適用于矩陣的求和，本文利用安全多方矩陣求和協議，給出了簡單高效的解線性方程組的安全多方計算協議

1 準備知識

1.1 安全多方矩陣求和協議[4]

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

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

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

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

，每個用戶pi只分別發送各自生成的xij，給相應的pj，每個用戶收到所

有數據各自在本地進行計算部分和并向所有用戶廣播計算結果，最后每個用戶只各自在本地根據廣播數據再次進行求和計算，得結果

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

以該協議只能容忍k-2方合謀。

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

2 求線性方程組的安全多方計算問題

2.1 多方安全線性方程組問題

多方安全線性方程組問題：A1有一個矩陣m1和一個向量b1；…；An有一個矩陣mn和一個向量bn；是維矩陣，是N維向量。不泄露他們各自的保密輸入，要共同解線性方程組。下面我們給出協議：

2.2 多方安全解線性方程組協議

輸入：A1有一個矩陣m1和一個向量b1；…；An有一個矩陣mn和一個向量bn；是維矩陣，是N維向量。

輸出：得到向量x，滿足

。

協議過程：

Step1 分別用和運行安全多方矩陣求和協議，分別得到矩陣和（其中Ri為階的方陣，Si為N維向量，），滿足，。

Step2 各自求解方程組，得到解向量x。

3 協議分析

3.1 保密性

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

3.2 計算復雜性

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

4 小結

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

參考文獻

[1] Du Wenliang. A study of several specific secure two-party computation problems[Ph.D. dissertation]. Purdue University，USA， 2000

[2] Cachin C.， Micali S.， Stadler M.. Computationally private information retrieval with polyogarithmic communication. In：Proceedings of Eurocrypt99， Prague， Czech Republic， 1999，308～318

[3]羅文俊，李祥. 多方安全矩陣乘積協議及應用[J].計算機學報， 2005，28（7）：1230-1235.

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