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

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

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

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

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

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

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

1安全多方計(jì)算基礎(chǔ)知識(shí)

1.1參與者

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

1.2安全多方計(jì)算模型

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

安全多方計(jì)算模型一般分為兩種模型：半誠(chéng)實(shí)模型與惡意模型：

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

1.3安全多方計(jì)算的安全需求

1.3.1安全性

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

1.3.2正確性

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

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

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

2.1點(diǎn)積協(xié)議

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

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

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

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

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

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

Step3：Alice和Bob利用上述點(diǎn)積協(xié)議，Alice將得到一個(gè)數(shù)u，而B(niǎo)ob得到一個(gè)數(shù)v，滿足u=；

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

Step5：Bob計(jì)算u-v得到.

因?yàn)榇藚f(xié)議的正確性和保密性是建立在點(diǎn)積協(xié)議的基礎(chǔ)上，所以此協(xié)議是正確安全的.

2.3波爾察諾二分法

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

二分法求根

Step1：選擇中點(diǎn)c=；

Step2：判斷f（a）、f（）、f（c）的符號(hào)

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

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

（3）若f（c）=0，則c是零點(diǎn).

缺點(diǎn)：

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

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

2.4問(wèn)題描述

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

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

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

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

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

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

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

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

2.6協(xié)議分析

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

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

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

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

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

3.2高斯消元法

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

3.3問(wèn)題描述

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

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

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

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

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

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

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

3.5協(xié)議分析

3.5.1正確性分析

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

3.5.2安全性分析

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

3.5.3復(fù)雜度分析

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

4　小結(jié)

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

參考文獻(xiàn)：

〔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〕羅永龍.安全多方計(jì)算中的若干關(guān)鍵問(wèn)題及其應(yīng)用研究[D].安徽：中國(guó)科學(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〕甘志.安全多方計(jì)算協(xié)議的應(yīng)用與研究[D].上海：上海交通大學(xué)，2005.53-60.

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

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

中圖分類(lèi)號(hào)：TP309

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-260X（2015）07-0040-03