保護私有信息的方程求解計算協(xié)議研究

葛永（中共銅陵市委黨校，安徽　銅陵　244000）

保護私有信息的方程求解計算協(xié)議研究

葛永
（中共銅陵市委黨校，安徽銅陵244000）

摘要：信息技術(shù)的快速發(fā)展為多個不同實體在保護私有數(shù)據(jù)的情況下聯(lián)合計算提供了保障.計算可以發(fā)生在互不信任的實體之間，甚至可以發(fā)生在兩個存在競爭關(guān)系的實體之間.而方程求解作為科學(xué)計算、金融分析等領(lǐng)域經(jīng)常用到的一種計算，被廣泛的應(yīng)用在銀行、軍事、通信等領(lǐng)域，如何在大數(shù)據(jù)時代背景下，保護自己的私有信息的同時進行合作計算、求解方程并且得到自己需要的信息變得越來越重要.本文設(shè)計了兩個保護私有信息的安全方程求解協(xié)議.

關(guān)鍵詞：方程求解；安全多方計算；保護私有信息；協(xié)議

安全多方計算問題最早由Yao提出，安全多方計算是一種協(xié)議，此協(xié)議的兩個最基本的安全要素就是保證協(xié)議的正確性和各參與方輸入的私密性，多方在一起用一種特殊的方法計算含有許多變量的任何函數(shù)，但除了知道這個函數(shù)的值之外，一方均不知道其他任何成員方輸入的任何消息.安全多方計算協(xié)議的設(shè)計用到了許多的基礎(chǔ)密碼學(xué)協(xié)議，同時作為密碼協(xié)議之一的此協(xié)議中的一些理論和解決思路又可以應(yīng)用到許多其他密碼學(xué)協(xié)議之中.利用安全多方計算協(xié)議，既可以實現(xiàn)私有數(shù)據(jù)的計算，同時又可以保護私有信息的不泄露.因此，安全多方計算的研究意義重大，可以廣泛的應(yīng)用于現(xiàn)實生活中.

1安全多方計算基礎(chǔ)知識

1.1參與者

參與者，參與協(xié)議執(zhí)行過程中的各方.而安全多方計算協(xié)議設(shè)計的難易程度往往取決于參與者的行為，按照參與者的行為，可以將參與者的類型分為三種：誠實參與者、半誠實參與者、惡意參與者.

1.2安全多方計算模型

安全多方計算模型可以概括為如下數(shù)學(xué)模型：n個協(xié)議參與者（）需要共同執(zhí)行函數(shù)，要求函數(shù)計算過程中，任意的參與者（i）輸入信息不被其他參與者知道.

安全多方計算模型一般分為兩種模型：半誠實模型與惡意模型：

半誠實模型下安全多方計算協(xié)議的設(shè)計較惡意模型安全多方計算協(xié)議設(shè)計容易得多，協(xié)議中有惡意參與者，大多數(shù)情況下協(xié)議是得不到正確結(jié)果的.如要保證在惡意模型中多方計算協(xié)議能得到正確的結(jié)果，則需要使用較多的密碼學(xué)技術(shù).本文研究設(shè)計安全多方計算協(xié)議均是建立在半誠實模型下的.

1.3安全多方計算的安全需求

1.3.1安全性

參與協(xié)議的任何一方除了知道自己的信息外，對其他各方的信息一無所知.只能從自己的輸入、中間結(jié)果及輸出中去推其他各方的信息.

1.3.2正確性

設(shè)計的協(xié)議要確保任意一方的輸出都是正確的，滿足需求.

2保護私有信息的方程求解協(xié)議

例如A國擁有強大的軍事導(dǎo)彈技術(shù)力量，B國擁有頂尖的偵查技術(shù)，可以對C國某地區(qū)進行偵查形成地圖坐標(biāo).A國與B國想在不泄露自己私有信息的情況下聯(lián)合發(fā)射導(dǎo)彈對C國某地區(qū)進行定點軍事打擊.在數(shù)據(jù)被兩方甚至多方聯(lián)合持有的情況下，已有的計算方法沒有考慮到保護參與方的私有數(shù)據(jù).關(guān)于安全兩方方程求解問題和協(xié)議、多方方程求解協(xié)議、求解方程的二分法，在文獻（甘志《安全多方計算協(xié)議的研究與應(yīng)用》）中有提及到，但并未給出具體可行的求解協(xié)議.本文給出了一個兩方保護私有信息方程求解問題，并給構(gòu)造了解決這一問題的協(xié)議.

2.1點積協(xié)議

Alice擁有一個私密向量X=（），Bob擁有一個私密向量Y=（）.Alice和Bob都想在不泄露自己私密向量的情況下，通過交互合作計算，Alice得知u，Bob得知v，其中滿足u=XY+v=，且Alice不能得到的值和任意的私有信息，Bob得不到u的值和任意.

2.2兩方多項式求值協(xié)議

輸入：Alice有一個多項式，Bob有一個數(shù)，在不泄露Alice任何信息的情況下，Bob得到.

解決思路：因為Alice擁有一個多項式，實際上等價于知道了這個多項式的系數(shù)向量（），所以，可以使用上述點積協(xié)議，將Alice這個多項式的系數(shù)向量（）與Bob的私有向量（）進行向量點積協(xié)議運算，這樣通過運算就可以得到，但這樣會向Bob暴露Alice的多項式的維數(shù)，因此在使用用點積協(xié)議進行運算之前，要使用一種方法來對Alice多項式的度進行數(shù)據(jù)隱藏，但不能影響協(xié)議的正確運行.從而對此協(xié)議進行了如下改進:

Step1：Alice與Bob通過協(xié)商，選擇適當(dāng)?shù)臄?shù)N作為向量點積運算的度（N≥n），雙方同時將自己私有數(shù)據(jù)應(yīng)給出的向量的維數(shù)擴展到N，對于Alice而言，增加的維數(shù)項均為零，即（）；

Step2：Alice與Bob將擴展后的向量作為點積協(xié)議的輸入數(shù)據(jù)，因為維數(shù)運算是在密文上的運算，所以Alice增加的維數(shù)項為0數(shù)量，Bob并不知道，但Bob有的概率能猜測到；

Step3：Alice和Bob利用上述點積協(xié)議，Alice將得到一個數(shù)u，而Bob得到一個數(shù)v，滿足u=；

Step4：Alice將數(shù)u發(fā)送給Bob；

Step5：Bob計算u-v得到.

因為此協(xié)議的正確性和保密性是建立在點積協(xié)議的基礎(chǔ)上，所以此協(xié)議是正確安全的.

2.3波爾察諾二分法

方程f（x）在區(qū)間[a，b]上是單值連續(xù)函數(shù)，若f （a）f（b）＜0，則在區(qū)間[a，b]內(nèi)至少有一個實根.

二分法求根

Step1：選擇中點c=；

Step2：判斷f（a）、f（）、f（c）的符號

（1）若f（c）和f（）符號相同，則區(qū)間[a，c]內(nèi)存在零點；

（2）若f（c）和f（）符號相同，則區(qū)間[c，b]內(nèi)存在零點；

（3）若f（c）=0，則c是零點.

缺點：

（1）二分法只能找到f（x）=0的一個根；

（2）f（x）在區(qū)間[a，b]上是單值連續(xù)函數(shù)，若f（a）f（b）＞0，不表明f（x）=0沒有根，這時二分法是失效的.

2.4問題描述

方程f（x）在區(qū)間[a，b]上是單值連續(xù)函數(shù)，且f （a）f（b）＜0，Alice擁有方程f（x)，Bob擁有區(qū)間[a，b]，通過交互計算求解方程f（x)=0的根，且Bob除了知道方程的一個根外，不知道Alice方程f（x)的任何信息，Alice不知道Bob私有區(qū)間[a，b]的任何信息.

2.5保護私有信息的方程求解協(xié)議

假設(shè)：對根的誤差要求為ε

Step1：Bob利用兩方多項式求值協(xié)議計算f （a）、f（b）；

Step2：Bob計算區(qū)間[a，b]中點C=；

Step3：Bob利用兩方多項式求值協(xié)議計算f （c），若f（c）=0，則c就是方程f（x)的根，協(xié)議執(zhí)行結(jié)束；否則順序執(zhí)行協(xié)議；

Step4：Bob計算f（a）f（c），若f（a）f（c）＞0，則將c的值賦給a，即a=c；否則將c的值賦給b，即b=c；

Step5：Bob計算b-a的值，若b-a＞ε，則轉(zhuǎn)向Step2；否則結(jié)束，Bob任取r∈（[]＜ε）中的一點作為方程f（x)的根.

2.6協(xié)議分析

此協(xié)議的安全性是建立在兩方多項式求值協(xié)議的基礎(chǔ)上，所以Bob不知道Alice方程f（x)的任何信息，Alice不知道Bob私有區(qū)間[a，b]的任何信息，協(xié)議是安全的；此協(xié)議的正確性是建立在波爾察諾二分法求解方程根的基礎(chǔ)上，所以協(xié)議也是正確的；時間復(fù)雜度分析此協(xié)議次兩方多項式求值協(xié)議.

3保護私有信息的一般求解線性方程組協(xié)議

保護私有信息的線性方程組求解問題（PPC-LSE）是科學(xué)計算中的一個重要問題，在金融及通信等領(lǐng)域有著廣泛的應(yīng)用.近年來，該領(lǐng)域取得了一系列的研究成果，對線性方程組特征值、特征向量、兩方線性方程及多方線性方程組的求解問題都有著不同的安全多方求解協(xié)議，但對于一般的線性方程組Ax=b的安全求解協(xié)議研究的較少.為解決此問題，本文設(shè)計了一個保護私有信息的線性方程組求解協(xié)議.

3.1數(shù)據(jù)隱藏

對于x∈R，在實數(shù)域R中選擇一個秘密隨機數(shù)k（k≠0），則k*x可以有效的保護x的隱私，即在需要保護的隱私數(shù)據(jù)中乘以一個隨機數(shù)以達到隱藏私有真實數(shù)據(jù)的目的.數(shù)據(jù)隱藏的目的是保護私有數(shù)據(jù)不泄露給其他參與方，同時要求隱藏后的數(shù)據(jù)應(yīng)能滿足多方計算的需求.

3.2高斯消元法

高斯消元法也稱作順序消元法.其求解基本思想是在系數(shù)矩陣的增廣矩陣進行行列變換、消元期間，把其系數(shù)矩陣的增廣矩陣逐步化為上三角矩陣，將原方程組轉(zhuǎn)化為等價的上三角方程組求解，然后通過回代過程逐一求解各個未知數(shù).

3.3問題描述

高斯消元法求兩方計算線性方程組的解，假定：一方Alice擁有齊次線性方程組Ax=0（即秘密輸入矩陣A），另一方Bob擁有非齊次方程組Ax=b中的向量b（即秘密輸入b）.協(xié)議執(zhí)行完后Bob得到解向量x，而Alice不知道Bob的任何信息.

3.4一般求解線性方程組協(xié)議

參與方：Alice輸入私密矩陣A（n階方陣）、Bob輸入私密向量b

假設(shè)條件：信道安全、參與方都是半誠實的

Step1：Bob隨機選擇一個非零實數(shù)k，并將k*b發(fā)送給Alice；

Step2：Alice利用高斯消元法求解方程組Ax' =k*b，并將方程組的解x'情況發(fā)送給Bob；

Step3：Bob根據(jù)接受的解x'的情況求方程Ax=b的解.由方程組的性質(zhì)知：若方程Ax'=k*b無解，則方程Ax=b無解；若方程Ax'=k*b有無數(shù)解，則方程Ax'=b有無數(shù)解；若方程Ax=k*b有唯一解，則方程Ax=b有唯一解，x=（1/k)*x'.

3.5協(xié)議分析

3.5.1正確性分析

根據(jù)方程組的性質(zhì)和高斯消元法求解線性方程知，上述構(gòu)造的兩方計算線性方程組協(xié)議是正確的.

3.5.2安全性分析

兩方計算線性方程組協(xié)議，使用了數(shù)據(jù)隱藏技術(shù)，且信道安全、參與方都是半誠實的，所以Alice不知道Bob的任何信息，不能求得Bob的私有向量b，并且Bob也不能推測Alice的私有矩陣A.由此得知，此協(xié)議是安全的.

3.5.3復(fù)雜度分析

因為Step1需完成n次乘法，Step2高斯消元法中需完成乘除法總數(shù)為次，Step3最多需完成n次除法，所以總的時間復(fù)雜度為.通信次數(shù)為2n次.

4　小結(jié)

本文設(shè)計的方程求解協(xié)議的不足均是建立在半誠實模型下的研究，對于一般的線性方程求解協(xié)議僅考慮在保護兩方私有信息的情況下，對于多方的線性方程組和惡意模型下的方程求解協(xié)議設(shè)計研究比較復(fù)雜，將在后續(xù)的工作中進行探討.

參考文獻：

〔1〕George Coulouris，Jean Dollimore，TimKindberg，Distributed Systems：Concepts and Design (Fourth Edition). Boston：Addison Wesley /Pearson Education，2005.

〔2〕S.Goldwasser. Multi -party Computation：Past and Present.In Preceedings of the 16th annual ACM symposium on Principles of distributed computing，Santa Barbara，CA USA，August 21 -24 1997.

〔3〕A.C.Yao. Protocols For Secure Computations. In proceedings of the 23rd Annual IEEE symposium on Foundations of Computer Science，160-164，1982.

〔4〕羅永龍.安全多方計算中的若干關(guān)鍵問題及其應(yīng)用研究[D].安徽：中國科學(xué)技術(shù)大學(xué)，2005.27-47.

〔5〕Ling Lezhen，Liao Junguo. Anonymous Electronic Voting Protocol with Traceability [C]. //Proceedings of 6th International Conference on Internet Technology and Secured Transactions，Abu Dhabi，United Arab Emirates，2011：59-66.

〔6〕甘志.安全多方計算協(xié)議的應(yīng)用與研究[D].上海：上海交通大學(xué)，2005.53-60.

〔7〕曹天杰，張永平，汪楚嬌.安全協(xié)議[M].北京：北京郵電大學(xué)出版社，2009.

〔8〕王莉，王卿文.保護私有信息的一般線性方程組計算協(xié)議[J].應(yīng)用數(shù)學(xué)與計算數(shù)學(xué)，2014（9）.

中圖分類號：TP309

文獻標(biāo)識碼：A

文章編號：1673-260X（2015）07-0040-03