矩陣與增廣矩陣秩相等問題的保密計算及應(yīng)用*

杜潤萌,劉旭紅,李順東,魏 瓊

1.陜西師范大學(xué) 計算機(jī)科學(xué)學(xué)院,西安 710119

2.陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,西安 710119

1 引言

矩陣是現(xiàn)代科技領(lǐng)域必不可少的工具,在自然科學(xué)、工程和社會科學(xué)的各個領(lǐng)域都有著重要的應(yīng)用價值,矩陣是圖像處理、線性規(guī)劃、各種網(wǎng)絡(luò)研究的關(guān)鍵工具和手段.矩陣的秩是反映矩陣固有特性的一個重要參數(shù)[1],用矩陣方法解決問題的核心手段是利用矩陣的秩,所以科學(xué)計算中的許多與矩陣相關(guān)的問題都可以歸約到矩陣秩的計算,許多保密的科學(xué)計算問題也都可用矩陣秩的保密計算協(xié)議解決.因此,矩陣秩的保密計算是安全多方計算的一個基本問題,有著重要的意義.

安全多方計算(secure multiparty computation,SMC)是指在不泄露自己隱私數(shù)據(jù)的情況下,多個參與者利用他們的私有數(shù)據(jù)進(jìn)行合作計算,計算結(jié)束后沒有參與方能獲得多于規(guī)定輸出的信息,是近年來國際密碼學(xué)界的研究熱點(diǎn)[2].SMC 最初是由姚期智教授提出來的,Goldreich 等人[3,4]對安全多方計算的理論進(jìn)行了深入研究,證明了在一定的條件下,任意函數(shù)f(x1,···,xn)的安全多方計算都是可以實(shí)現(xiàn)的,并且給出了基于不經(jīng)意傳輸?shù)慕鉀Q方案.這樣的通用解決方案有重要的理論意義,奠定了安全多方計算的理論基礎(chǔ),但是用通用解決方案解決實(shí)際的安全多方計算問題是不合理的,對具體的問題應(yīng)該研究具體的解決方案.同時Goldreich 利用比特承諾[5]和零知識證明[6]設(shè)計了一個編譯器,借助這個編譯器,可以自動生成一個對于半誠實(shí)參與者和惡意參與者都安全的多方計算協(xié)議,該協(xié)議可以強(qiáng)迫惡意參與者以半誠實(shí)的方式參與協(xié)議的執(zhí)行過程,否則將被發(fā)現(xiàn).

安全多方計算的研究在計算科學(xué)中占有重要的地位和廣泛的應(yīng)用前景,這激勵著人們研究各種具體的安全多方計算問題[7].所研究的問題可以總結(jié)為以下幾類:保密的科學(xué)計算問題[8];保密的統(tǒng)計分析問題[9];保密的數(shù)據(jù)挖掘問題[10];其他安全多方計算問題.關(guān)于科學(xué)計算的兩方安全計算問題,美國普渡大學(xué)的Du 博士在其論文中還指出了科學(xué)計算其他值得研究的問題[11]:矩陣特征值、特征向量、行列式、矩陣因子分解等.Cramer 和Damg?rd 在線性秘密共享下首次研究了線性代數(shù)中各種各樣的安全計算問題:如矩陣的行列式、矩陣的秩、線性方程組、特征多項(xiàng)式等問題,并給出了解決方案[12].

文獻(xiàn)[13]給出了一個判定加密矩陣的奇異性的協(xié)議.基于此協(xié)議,解決了計算加密矩陣的秩和線性方程組解的問題.但該文利用矩陣的奇異性去判斷矩陣的秩,要求矩陣必須為n×n的方陣,因而解決方案不具有普遍意義.此外,方案采用同態(tài)加密體制,計算復(fù)雜性較高.在國內(nèi),線性代數(shù)問題同樣得到了廣泛深入的研究.文獻(xiàn)[14]將Du 的工作推廣到多方的情形.方案需要多次調(diào)用兩矩陣乘積協(xié)議以及不經(jīng)意傳輸協(xié)議,計算復(fù)雜性與通信復(fù)雜性都很高.文獻(xiàn)[15]提出的保密計算矩陣秩的協(xié)議,需要Alice 和Bob 兩個人合作計算一個m×n矩陣的秩,但計算復(fù)雜性是O(mn2).文獻(xiàn)[16]基于安全點(diǎn)積協(xié)議設(shè)計了個多方向量組秩的協(xié)議.但求矩陣秩的時候需要調(diào)用mn次點(diǎn)積協(xié)議,計算復(fù)雜性是O(m2n),其中m表示參與者個數(shù),n表示每個參與者所擁向量的維數(shù),這個方案的計算復(fù)雜性也較高.

綜上所述,現(xiàn)有的關(guān)于矩陣秩的保密計算協(xié)議存在幾個方面的不足:解決方案的適用性有限;基于公鑰加密算法設(shè)計的方案計算復(fù)雜性較高;用矩陣的秩解決的實(shí)際問題有限.針對這些問題,本文假設(shè)Alice擁有一個矩陣Am×n,Bob 擁有一個矩陣Bm×1,設(shè)計了一個安全高效的計算增廣矩陣(A|B)秩的協(xié)議.將矩陣秩的計算推廣到一般的矩陣,提出了不需要加密運(yùn)算的高效保密計算協(xié)議,并以此判斷矩陣與增廣矩陣秩是否相等.判斷矩陣與增廣矩陣秩是否相等的保密計算可以作為一個基本建筑模塊,用于構(gòu)建許多安全多方計算問題的協(xié)議,包括保密判定空間直線與直線(平面與直線、平面與平面)的位置關(guān)系、保密判斷多項(xiàng)式整除、保密判斷集合包含問題和任意數(shù)整除問題、保密判斷線性方程組解的數(shù)目等應(yīng)用,拓寬了矩陣秩的保密計算的應(yīng)用領(lǐng)域.

空間兩直線位置關(guān)系問題的多方保密計算方案在實(shí)際應(yīng)用場景中具有重要的研究意義.例如:航空公司A 和航空公司B 在同樣的兩個國家之間分別設(shè)計了一條航線圖L1和L2,他們想在不泄露自己航線圖的情況下保密地判定L1和L2是否相交,確保航線的安全性.所以他們需要合作計算兩條空間航線是否相交.現(xiàn)實(shí)中很多問題都可以歸約到空間位置關(guān)系的保密判定,因此研究這個問題有著重要的應(yīng)用價值.由于平面和直線在直角坐標(biāo)系下可分別用三元線性方程和三元線性方程組來表示,而線性方程組解的數(shù)目和系數(shù)矩陣關(guān)系密切,因此可用保密判定矩陣與其增廣矩陣的秩是否相等的方法來判斷空間直線與直線(平面與直線、平面與平面)的位置關(guān)系.

本文研究矩陣與增廣矩陣秩的相等問題的保密計算,主要貢獻(xiàn)如下:

(1)研究了矩陣與增廣矩陣的秩是否相等的安全多方計算問題,提出了一種新的、不需要加密運(yùn)算的、適用于一般矩陣的高效解決方案,為解決其他多方保密計算問題提供一種新的方法.

(2)在保密判斷矩陣和增廣矩陣秩是否相等協(xié)議的基礎(chǔ)上,提出了保密判斷空間兩條直線位置關(guān)系的協(xié)議,方案安全且高效.

(3)在保密判斷矩陣和增廣矩陣秩是否相等協(xié)議的基礎(chǔ)上,提出了保密判斷兩個多項(xiàng)式是否可以整除的協(xié)議,也為解決其他多方保密計算問題提供一種新的途徑.

本文第2 節(jié)介紹了協(xié)議相關(guān)預(yù)備知識;第3–5 節(jié)設(shè)計了三種協(xié)議;第6 節(jié)分析了方案的效率;第7 節(jié)給出了文章的總結(jié).

2 預(yù)備知識

2.1 安全性定義

半誠實(shí)參與者[17]本文方案的安全性均假設(shè)安全多方計算的參與者為半誠實(shí)參與者.半誠實(shí)參與者是指參與者在協(xié)議執(zhí)行過程中將完全按照協(xié)議忠實(shí)地執(zhí)行協(xié)議,但他們也會保留計算的中間結(jié)果試圖推導(dǎo)出其他參與者的輸入.

隱私的模擬范例[18]如果對于任意一個半誠實(shí)的參與者,在執(zhí)行協(xié)議的過程中,參與者所獲得信息都可以通過他自己的輸入和輸出進(jìn)行模擬,而且得到的消息序列與實(shí)際過程得到的消息序列不可區(qū)分,就說明協(xié)議是安全的.如果一個多方計算協(xié)議能夠進(jìn)行這樣的模擬,即說明所有參與者都不可能從協(xié)議的執(zhí)行過程中得到其他參與者任何有價值的信息.這就是研究安全多方計算問題時普遍接受的模擬范例.

一些記號假設(shè)雙方計算的參與者分別是Alice 和Bob.

(1)設(shè)f=(f1,f2)是一個概率多項(xiàng)式時間函數(shù),π表示計算f的雙方計算協(xié)議.

(2)當(dāng)輸入為(x,y)時,Alice(Bob)在執(zhí)行協(xié)議π的過程中所得到的信息序列記為其中r1(r2)表示Alice(Bob)選擇的隨機(jī)數(shù);表示Alice(Bob)第i次收到的信息.

(3)輸入為(x,y)時,執(zhí)行協(xié)議π以后,Alice(Bob)的輸出結(jié)果記為

定義1(半誠實(shí)參與者的保密性)對于一個函數(shù)f,如果存在概率多項(xiàng)式時間算法S1與S2(也稱這樣的多項(xiàng)式時間算法為模擬器)使得

其中表示計算上不可區(qū)分,則認(rèn)為π保密地計算f.

2.2 矩陣相關(guān)知識

矩陣的秩在m×n矩陣A中任取k行、k列(1kmin{m,n}),位于這k行、k列交叉點(diǎn)處的元素按原來次序組成的k階行列式稱為A的一個k階子式.矩陣A中不等于零的子式的最高階數(shù)稱為A的秩,記為R(A).

初等行變換設(shè)A為m×n矩陣,可對A實(shí)施以下三類初等行變換,將A化為行階梯矩陣或最簡行階梯矩陣.

(1)第一類初等行變換:將A的第i行與第j行交換位置;

(2)第二類初等行變換:將A的第i行乘以非零常數(shù)λ;

(3)第三類初等行變換:將A的第i行的λ倍加到第j行.初等變換不會改變矩陣的秩.

初等矩陣[19]由單位矩陣E經(jīng)過一次初等變換得到的矩陣稱為初等矩陣.

從初等矩陣的定義可以看出,初等矩陣是方陣,并且每次進(jìn)行初等變換都會有一個與之相對應(yīng)的初等矩陣.共有三類初等矩陣,如圖1 所示.

圖1 三類初等矩陣Figure 1 3 kinds of primary matrix

其中,P(i,j)表示互換矩陣E的第i行與第j行,P(i(c))表示用數(shù)域中非零數(shù)c乘E的第i行,P(i,j(k))表示把矩陣E的第j行的k倍加到第i行.由于本文中全部用的初等行變換,所以與列變換相應(yīng)的初等矩陣不做討論.

用初等變換化矩陣為行階梯矩陣任意矩陣Am×n經(jīng)過有限步的初等行變換,可將矩陣化為行階梯矩陣A′,特點(diǎn)是:可畫出一條階梯線,線的下方全為0,階梯線的豎線后面的第一個元素為非零元.例如矩陣

即為一個行階梯矩陣.因此存在初等矩陣P1,P2,···,Ps,使得下式

成立,記P=Ps···P2P1.

2.3 多項(xiàng)式整除與矩陣秩的關(guān)系

命題1有兩個多項(xiàng)式f(x)=anxn+an?1xn?1+···+a0x0,q(x)=cmxm+cm?1xm?1+···+c0x0,令g(x)=f(x)q(x).利用f(x)的系數(shù)并且每一列擴(kuò)展m個0 構(gòu)造矩陣A(m+n+1)×(m+1),利用g(x)的系數(shù)構(gòu)造矩陣B(m+n+1)×1.f(x)整除g(x)的充分必要條件是其對應(yīng)的系數(shù)矩陣滿足R(A)=R(A|B).

證明:必要性:g(x)=f(x)q(x)=a0c0x0+(a1c0+a0c1)x1+···+(asc0+as?1c1+···+a1cs?1+a0cs)xs+···+(am+nc0+am+n?1c1+···+a0cm+n)xm+n

從上式可以得出

其中in,jm.

利用f(x)的系數(shù)并且每一列擴(kuò)展m個0 構(gòu)造矩陣A(m+n+1)×(m+1),利用q(x)的系數(shù)構(gòu)造矩陣C(m+1)×1.令A(yù)與C作相乘的運(yùn)算,可以得到矩陣B,如圖2 所示.

圖2 AC =BFigure 2 AC =B

從圖2 中比較A,B,C中的元素可以得出:

因此f(x)q(x)=g(x)等價于AC=B.f(x)整除g(x),而且有唯一的商q(x),等價于AC=B對應(yīng)的線性方程組有解,而線性方程組有解的條件是矩陣A與增廣矩陣(A|B)同秩,也就是R(A)=R(A|B).同理可證充分性.

綜上所述,f(x)整除g(x)的充分必要條件是其對應(yīng)的系數(shù)矩陣滿足R(A)=R(A|B).

3 矩陣與增廣矩陣秩相等問題

3.1 問題描述

Alice 有一個矩陣Am×n,Bob 有一個矩陣Bm×1,利用A,B構(gòu)造增廣矩陣(A|B),其中

Alice 和Bob 都想在不暴露自己私有數(shù)據(jù)的情況下,判斷矩陣A和增廣矩陣(A|B)的秩是否相等.

協(xié)議的基本原理Alice 計算初等變換矩陣Pm×m發(fā)送給Bob,其中矩陣A′=PA.Bob 收到P后,計算PB得到矩陣B′發(fā)送給Alice.Alice 判斷矩陣A的秩與增廣矩陣(A|B)的秩是否相等.為方便表達(dá),定義如下謂詞:

例如,Alice 有一個矩陣A3×3,Bob 有一個矩陣B3×1,Alice 計算出初等變換矩陣P3×3發(fā)送給Bob,其中

Bob 收到P后,計算PB得到矩陣B′,其中

Bob 將矩陣B′發(fā)送給Alice.Alice 比較矩陣A′與增廣矩陣(A′|B′)秩的大小,其中

由此可知,R(A′)=R(A′|B′)=3,輸出P(A,(A|B))=2.上述原理是我們計算矩陣與增廣矩陣秩是否相等的基本思路,不涉及任何保密問題,保密計算矩陣秩的具體協(xié)議參看協(xié)議1.

3.2 矩陣與增廣矩陣秩相等問題保密計算方案

協(xié)議1保密的計算矩陣與增廣矩陣秩相等問題.

輸入:Alice 有一個矩陣Am×n,Bob 有一個矩陣Bm×1.

輸出:P(A,(A|B)).

(1)Alice 計算初等變換矩陣Pm×m.Alice 對矩陣P隨機(jī)化處理得到矩陣P′,其中

其中,ri是Alice 選取的有理數(shù)隨機(jī)數(shù).Alice 將P′發(fā)送給Bob.

(2)Bob 計算P′B得到矩陣B′,其中

Bob 統(tǒng)計從以上緊挨并連續(xù)等于的個數(shù)和從開始以下0 的個數(shù),分別記為p,q.Bob 將p,q發(fā)送給Alice.

(3)Alice 根據(jù)p,q進(jìn)行判斷.若R(A)=R(A|B)

定理1在半誠實(shí)模型下,協(xié)議1 是正確的.

證明:(1)Alice 計算初等變換矩陣P和P′=P(r1,...,rm),其正確性是由對矩陣進(jìn)行初等行變換不會改變的矩陣的秩保證的.

(2)Bob 計算B′=P′B,這樣就可以保證Bob 與Alice 做的是同樣的初等變換.

(3)Bob 統(tǒng)計從以上緊挨并連續(xù)等于的個數(shù)和從開始以下0 的個數(shù),分別記為p,q.Bob將p,q發(fā)送給Alice.根據(jù)矩陣的秩的定義,Alice 根據(jù)p,q進(jìn)行判斷即可得到增廣矩陣(A|B)的秩.

因此,協(xié)議1 是正確的.

協(xié)議1 的安全性分析為了分析協(xié)議1 的安全性,需要詳細(xì)分析在協(xié)議執(zhí)行后可能推斷出的潛在信息.

首先考慮Alice 矩陣的安全性.Alice 對矩陣進(jìn)行隨機(jī)化處理,Bob 在整個協(xié)議的執(zhí)行過程中僅得到Alice 發(fā)送給他的矩陣P′.由于P′原本不是最簡矩陣,并且有r1,r2,···,rm為Alice 的保密數(shù)據(jù),均可隨機(jī)選取(也可選擇有理數(shù)),即使Bob 有無限的計算能力,也無法推出矩陣P,更無法推出矩陣A.

同樣的,Alice 只知道p,q,所以Alice 也無法推斷出矩陣B.

定理2在半誠實(shí)模型下,協(xié)議1 是安全的.

證明:我們通過構(gòu)造使得(1)和(2)成立的模擬器S1和S2來證明本定理,首先構(gòu)造S1.

(1)S1接受輸入(A,P(A,(A|B))),根據(jù)P(A,(A|B))的值構(gòu)造矩陣B′,用A,B′進(jìn)行模擬.

(2)S1計算矩陣A的初等變換矩陣P,按照協(xié)議1 對P進(jìn)行隨機(jī)化處理得到矩陣P′.

(3)S1計算P′B′得到矩陣B′′.S1統(tǒng)計從以上緊挨并連續(xù)等于的個數(shù)和從開始以下0的個數(shù),分別記為p′,q′.

(4)S1比較R(A|B′)和R(A|B)是否相等.

在本協(xié)議中view1(A,B)={A,P,R(B),P(A,(A|B))}.令S1(A,P(A,(A|B)))={A,P,R(B′),P(A,(A|B′))},由于P(A,(A|B))=P(A,(A|B′)),則R(B)=R(B′),所以可以推出

類似地,還可以構(gòu)造S2使下式成立

4 空間兩條直線的位置關(guān)系

4.1 問題描述

Alice 有一條空間直線L1,Bob 有一條空間直線L2,方程分別為

Alice 和Bob 都想在不暴露自己私有數(shù)據(jù)的情況下,判斷這兩條空間直線的位置關(guān)系.

協(xié)議的基本原理Bob 利用平面方程l22的參數(shù)構(gòu)造矩陣B1,矩陣B2以及矩陣B,其中

Bob 將平面方程l21的參數(shù)a31,a32,a33,a34發(fā)送給Alice(由于經(jīng)過一條直線的平面有無限多個,所以將其中一個平面參數(shù)發(fā)送給Alice,Alice 也無法推斷出直線方程).Alice 利用L1,l21的系數(shù)構(gòu)造矩陣A1、矩陣A2以及矩陣A,其中

Alice 和Bob 利用矩陣A1,A2,B1,B2構(gòu)造矩陣(A1B1)、矩陣(A2B2)以及增廣矩陣(AB),其中

因此,判定空間兩條直線間的位置關(guān)系的問題就轉(zhuǎn)化為矩陣(A1B1)與增廣矩陣(AB)秩的關(guān)系.當(dāng)R(A1B1)=R(AB)=3 時,L1與L2相交于一點(diǎn);當(dāng)R(A1B1)=R(AB)=2 時,L1與L2重合;當(dāng)R(A1B1)=2 且R(AB)=3 時,L1與L2平行;當(dāng)R(A1B1)=3 且R(AB)=4 時,L1與L2為兩條異面直線.為方便表達(dá),定義如下謂詞:

例如,Alice 有一條空間直線L1,Bob 有一條空間直線L2,方程分別為

Alice 和Bob 利用矩陣A1,A2,B1,B2構(gòu)造矩陣(A1B1)、矩陣(A2B2)以及增廣矩陣(AB),其中

對矩陣(A1B1)和增廣矩陣(AB)進(jìn)行初等行變換,將矩陣(A1B1)和增廣矩陣(AB)化為行階梯矩陣(A1B1)′,(AB)′,其中

由此可知,R(A1B1)=2 且R(AB)=3,所以L1與L2平行,輸出P(L1,L2)=2.

4.2 空間兩條直線的位置關(guān)系保密計算方案

協(xié)議2保密的計算空間兩條直線間的位置關(guān)系.

輸入:Alice 有一條空間直線L1,Bob 有一條空間直線L2.

輸出:P(L1,L2).

(1)Bob 將l21的參數(shù)a31,a32,a33,a34發(fā)送給Alice.Alice 和Bob 調(diào)用協(xié)議1 中的(1)–(2).

(2)Alice 比較R(AB)與R(A1B1)的大小.若R(AB)=4,輸出P(L1,L2)=3;若R(A1B1)=R(AB)=3,輸出P(L1,L2)=0;若R(A1B1)=R(AB)=2,輸出P(L1,L2)=1;若R(A1B1)=2 且R(AB)=3,輸出P(L1,L2)=2.

定理3在半誠實(shí)模型下,協(xié)議2 是正確的.

證明:證明方法與定理1 的證明類似,是根據(jù)矩陣秩的定義和初等變換不改變矩陣的秩保證其正確性.

協(xié)議2 的安全性分析協(xié)議2 的安全性分析與協(xié)議1 的安全性分析類似.

定理4在半誠實(shí)模型下,協(xié)議2 是安全的.

證明:證明方法與定理1 的證明類似,也可采用構(gòu)造模擬器的方法.

5 多項(xiàng)式整除問題

5.1 問題描述

Alice 有一個多項(xiàng)式f(x)=anxn+an?1xn?1+···+a0x0,Bob 有一個多項(xiàng)式g(x)=bmxm+bm?1xm?1+···+b0x0.Alice 和Bob 都想在不暴露自己私有數(shù)據(jù)的情況下,判斷多項(xiàng)式f(x)是否可以整除g(x).若f(x)可以整除g(x),記f(x)|g(x);若f(x)不可以整除g(x),記f(x)?g(x).

協(xié)議的基本原理Alice 利用多項(xiàng)式f(x)中的系數(shù),每一列擴(kuò)展(m?n)個 0,構(gòu)造矩陣A(m+1)×(m?n+1),Bob 利用多項(xiàng)式g(x)中的系數(shù)構(gòu)造矩陣B(m+1)×1,如圖3 所示.

因此,多項(xiàng)式整除問題就轉(zhuǎn)換為矩陣A與增廣矩陣(A|B)秩的關(guān)系.若R(A)=R(A|B),則f(x)|g(x);若R(A)R(A|B),則f(x)?g(x).為方便表達(dá),定義如下謂詞:

圖3 矩陣A 和矩陣BFigure 3 Matrix A and B

例如,Alice 有一個多項(xiàng)式f(x)=x?2,Bob 有一個多項(xiàng)式g(x)=x2?5x+6.Alice 利用f(x)中的系數(shù),每一列擴(kuò)展1 個0,構(gòu)造矩陣A,Bob 利用g(x)的系數(shù)構(gòu)造矩陣B,Alice 計算出初等變換矩陣P3×3發(fā)送給Bob,其中

Bob 收到P后,計算PB得到矩陣B′,其中

Bob 將矩陣B′發(fā)送給Alice.Alice 比較矩陣A′與增廣矩陣(A′|B′)秩的大小,其中

由此可知,R(A′)=R(A′|B′)=2,所以f(x)|g(x),輸出P(f(x),g(x))=1.

5.2 多項(xiàng)式整除問題保密計算方案

協(xié)議3保密的計算多項(xiàng)式整除問題

輸入:Alice 有一個多項(xiàng)式f(x)=anxn+an?1xn?1+ ··· +a0x0,Bob 有一個多項(xiàng)式g(x)=bmxm+bm?1xm?1+···+b0x0.

輸出:P(f(x),g(x)).

(1)Bob 構(gòu)造矩陣B(m+1)×1,將m發(fā)送給Alice.

(2)若m

(3)Alice 和Bob 調(diào)用協(xié)議1 中(1)–(2).

(4)Alice 進(jìn)行判斷.若R(A′)=R(A′|B′′),輸出P(f(x),g(x))=1;否則輸出P(f(x),g(x))=0.

定理5在半誠實(shí)模型下,協(xié)議3 是正確的.

證明:證明方法與定理1 的證明類似,是根據(jù)矩陣秩的定義和初等變換不改變矩陣的秩保證其正確性.

協(xié)議3 的安全性分析協(xié)議3 的安全性分析與協(xié)議1 的安全性分析類似.

定理6在半誠實(shí)模型下,協(xié)議3 是安全的.

證明:證明方法與定理1 的證明類似,也可采用構(gòu)造模擬器的方法.

5.3 多項(xiàng)式整除問題的應(yīng)用

集合包含問題Alice 有一個集合A={a1,a2,···,an},Bob 有一個集合B={b1,b2,···,bm}.Alice和Bob 都想在不暴露自己私有數(shù)據(jù)的情況下,判斷一個集合是否包含另一個集合.若一個集合不包含另一個集合,記(A?B)∩(B?A);若一個集合包含另一個集合,記(A?B)∪(B?A).Alice和Bob 都將集合中的數(shù)據(jù)用多項(xiàng)式的形式表達(dá)出來[20].例如,集合A={1,,3,2},即多項(xiàng)式f(x)=(x?1)(2x?1)(x?3)(x?2).因此,集合包含問題就轉(zhuǎn)換為多項(xiàng)式整除問題.若(f(x)|g(x))∪(f(x)|g(x)),就是一個集合包含另一個集合;否則不是.具體協(xié)議與協(xié)議3 類似,本文不予給出.

整除問題Alice 有一個機(jī)密數(shù)x(x0),Bob 有一個機(jī)密數(shù)y(y0).Alice 和Bob 都想在不暴露自己私有數(shù)據(jù)的情況下,判斷一個數(shù)是否整除另一個數(shù).若兩個數(shù)據(jù)不具有整除關(guān)系,記(x?y)∧(y?x);若兩個數(shù)據(jù)具有整除關(guān)系,記(x|y)∨(y|x).根據(jù)算術(shù)基本定理,任一整數(shù)z都可以表示為

pi表示第i個素數(shù),即p1=2,p2=3,···,令[p]=Alice 和Bob 利用x,y,[p]構(gòu)造集合[pA],[pB].例如,數(shù)據(jù)z=24,即[p]={2,4,8,3}.因此,數(shù)的整除判定問題就轉(zhuǎn)換為多項(xiàng)式整除問題.若(f(x)|g(x))∨(f(x)|g(x)),就是兩個數(shù)據(jù)具有整除關(guān)系;否則不是.具體協(xié)議與協(xié)議3 類似,本文不予給出.

6 性能分析

6.1 效率分析

本文的基礎(chǔ)協(xié)議(協(xié)議1)本質(zhì)是通過保密計算增廣矩陣的秩,以此保密判斷矩陣的秩和增廣矩陣的秩是否相等.因此在與其他文獻(xiàn)做對比時,為了統(tǒng)一標(biāo)準(zhǔn),均以求解矩陣的秩來比較方案的計算復(fù)雜性和通信復(fù)雜性.

計算復(fù)雜性分析文獻(xiàn)[15]求矩陣秩的時候調(diào)用了向量比等協(xié)議,其計算開銷是n·(mn+2m+2)Me,m,n表示Alice 和Bob 兩個人合作計算一個m維n列矩陣的秩,Me是模指數(shù)運(yùn)算(下同).文獻(xiàn)[16]求矩陣秩的時候需要調(diào)用mn次點(diǎn)積協(xié)議,計算開銷是m2nMe,m表示參與者個數(shù),n表示每個參與者所擁有向量的維數(shù).在計算復(fù)雜性理論中,當(dāng)模指數(shù)運(yùn)算與普通的運(yùn)算數(shù)量差不多的時候,普通的基本運(yùn)算所消耗的時間一般可以忽略不計.文獻(xiàn)[15,16]均有復(fù)雜的模指數(shù)運(yùn)算,而我們的協(xié)議只有簡單的初等變換運(yùn)算,因此與文獻(xiàn)[15,16]中的協(xié)議相比,我們的協(xié)議計算復(fù)雜性可以忽略.

本文的方案主要利用了矩陣的初等行變換運(yùn)算,所以分析計算復(fù)雜性時,只考慮協(xié)議執(zhí)行中最費(fèi)時的初等行變換運(yùn)算,其他運(yùn)算忽略不計.現(xiàn)以3×3 維的矩陣為例,在我們的實(shí)驗(yàn)條件下求矩陣的初等變換矩陣的計算開銷約3 毫秒,對矩陣進(jìn)行一次隨機(jī)化處理的計算開銷約1 毫秒,總共耗時約4 毫秒.4×4維矩陣求一次初等變換矩陣和隨機(jī)化處理的計算開銷約6 毫秒,依次類推,實(shí)驗(yàn)數(shù)據(jù)顯示求一次初等變換矩陣和隨機(jī)化處理的計算開銷是隨著矩陣維數(shù)的增長大致線性增長.由于計算開銷與計算設(shè)備和計算軟件密切相關(guān),本文假設(shè)求一次初等變換矩陣是x毫秒,執(zhí)行一次m×n維矩陣隨機(jī)化處理是h毫秒.本文協(xié)議1–3 均需要求一次初等變換矩陣和執(zhí)行一次矩陣隨機(jī)化處理,計算開銷均為(x+h)毫秒.

通信復(fù)雜性分析衡量通信復(fù)雜度的指標(biāo)是用協(xié)議交換信息的比特數(shù),或者用通信輪數(shù),在安全多方計算研究中通常用輪數(shù).文獻(xiàn)[15]通信輪數(shù)是n·(mn+2m+)輪.文獻(xiàn)[16]通信復(fù)雜度主要產(chǎn)生在調(diào)用點(diǎn)積協(xié)議時產(chǎn)生的信息交互,通信輪數(shù)為mn2輪.本文中協(xié)議1 的通信復(fù)雜性是3 輪,協(xié)議2 的通信復(fù)雜性是4 輪,協(xié)議3 的通信復(fù)雜性是4 輪,所以本文協(xié)議的計算復(fù)雜性和通信復(fù)雜度都比較低.矩陣的秩計算方案的計算復(fù)雜性和通信復(fù)雜性比較見表1.

表1 矩陣的秩計算方案的效率對比Table 1 Comparison of all solutions on matrix rank calculation

另外給出本文在應(yīng)用部分的協(xié)議2(空間兩條直線的位置關(guān)系)與文獻(xiàn)[21]在效率和安全性方面的分析與比較(見表2).文獻(xiàn)[21]調(diào)用了內(nèi)積協(xié)議,其中方案中調(diào)用的內(nèi)積協(xié)議總次數(shù)和用戶需要進(jìn)行的模指數(shù)運(yùn)算的次數(shù)作為衡量計算復(fù)雜性的指標(biāo),其它運(yùn)算忽略不計.模指數(shù)運(yùn)算記為Me.

表2 直線與直線位置關(guān)系判定方案的效率對比Table 2 Comparison of solutions on location relation between line and line

實(shí)驗(yàn)仿真由于協(xié)議2 和協(xié)議3 與協(xié)議1 類似,所以實(shí)驗(yàn)仿真只模擬協(xié)議1.

操作系統(tǒng):Windows7(64 位).操作軟件:MATLAB R2014a.語言:MATLAB.協(xié)議1:保密的計算矩陣與增廣矩陣秩相等問題.設(shè)定:矩陣為方陣,方陣內(nèi)每一個數(shù)據(jù)為8 位大隨機(jī)數(shù),方陣的維數(shù)間隔為1.圖4 描述了協(xié)議1 的執(zhí)行時間隨著方陣維數(shù)增長的變化規(guī)律.

圖4 協(xié)議1 的執(zhí)行時間隨著方陣維數(shù)增長的變化規(guī)律Figure 4 Consume time of protocol increases with the dimension of square matrix

由圖4 可知,以毫秒為單位測出的執(zhí)行時間隨方陣維數(shù)的增長大致呈線性增長.綜上所述,協(xié)議1–3不僅具有較高的安全性,而且計算雙方的通信代價及計算復(fù)雜度都比較低.

7 結(jié)論

本文研究矩陣與增廣矩陣的秩是否相等的問題,設(shè)計了一個不需要借助密碼學(xué)原語、具有信息論安全、計算復(fù)雜性低且通信效率高的安全多方保密計算協(xié)議.在保密判斷矩陣和增廣矩陣秩是否相等協(xié)議的基礎(chǔ)上,提出了保密判斷兩個多項(xiàng)式是否可以整除的協(xié)議,利用該協(xié)議可以解決有理數(shù)集合包含問題、數(shù)的整除問題.本文還提出可以利用矩陣和增廣矩陣秩是否相等保密高效的解決空間直線與直線的位置關(guān)系.本文研究的這些問題都是基于半誠實(shí)模型的,對于多方保密計算的研究與應(yīng)用有重要的理論意義,對其他密碼學(xué)應(yīng)用也有一定意義,未來將研究惡意模型下的保密計算矩陣與增廣矩陣的秩是否相等的問題.