杜潤(rùn)萌,劉旭紅,李順東,魏 瓊

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2 預(yù)備知識(shí)

2.1 安全性定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

從初等矩陣的定義可以看出,初等矩陣是方陣,并且每次進(jìn)行初等變換都會(huì)有一個(gè)與之相對(duì)應(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)過(guò)有限步的初等行變換,可將矩陣化為行階梯矩陣A′,特點(diǎn)是:可畫出一條階梯線,線的下方全為0,階梯線的豎線后面的第一個(gè)元素為非零元.例如矩陣

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

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

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

命題1有兩個(gè)多項(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個(gè)0 構(gòu)造矩陣A(m+n+1)×(m+1),利用g(x)的系數(shù)構(gòu)造矩陣B(m+n+1)×1.f(x)整除g(x)的充分必要條件是其對(duì)應(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個(gè)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)等價(jià)于AC=B.f(x)整除g(x),而且有唯一的商q(x),等價(jià)于AC=B對(duì)應(yīng)的線性方程組有解,而線性方程組有解的條件是矩陣A與增廣矩陣(A|B)同秩,也就是R(A)=R(A|B).同理可證充分性.

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

3 矩陣與增廣矩陣秩相等問(wèn)題

3.1 問(wèn)題描述

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

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

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

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

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

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

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

3.2 矩陣與增廣矩陣秩相等問(wèn)題保密計(jì)算方案

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

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

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

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

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

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

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

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

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

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

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

(3)Bob 統(tǒng)計(jì)從以上緊挨并連續(xù)等于的個(gè)數(shù)和從開(kāi)始以下0 的個(gè)數(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 對(duì)矩陣進(jìn)行隨機(jī)化處理,Bob 在整個(gè)協(xié)議的執(zhí)行過(guò)程中僅得到Alice 發(fā)送給他的矩陣P′.由于P′原本不是最簡(jiǎn)矩陣,并且有r1,r2,···,rm為Alice 的保密數(shù)據(jù),均可隨機(jī)選取(也可選擇有理數(shù)),即使Bob 有無(wú)限的計(jì)算能力,也無(wú)法推出矩陣P,更無(wú)法推出矩陣A.

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

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

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

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

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

(3)S1計(jì)算P′B′得到矩陣B′′.S1統(tǒng)計(jì)從以上緊挨并連續(xù)等于的個(gè)數(shù)和從開(kāi)始以下0的個(gè)數(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 問(wèn)題描述

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)過(guò)一條直線的平面有無(wú)限多個(gè),所以將其中一個(gè)平面參數(shù)發(fā)送給Alice,Alice 也無(wú)法推斷出直線方程).Alice 利用L1,l21的系數(shù)構(gòu)造矩陣A1、矩陣A2以及矩陣A,其中

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

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

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

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

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

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

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

協(xié)議2保密的計(jì)算空間兩條直線間的位置關(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在半誠(chéng)實(shí)模型下,協(xié)議2 是正確的.

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

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

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

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

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

5.1 問(wèn)題描述

Alice 有一個(gè)多項(xiàng)式f(x)=anxn+an?1xn?1+···+a0x0,Bob 有一個(gè)多項(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)個(gè) 0,構(gòu)造矩陣A(m+1)×(m?n+1),Bob 利用多項(xiàng)式g(x)中的系數(shù)構(gòu)造矩陣B(m+1)×1,如圖3 所示.

因此,多項(xiàng)式整除問(wèn)題就轉(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 有一個(gè)多項(xiàng)式f(x)=x?2,Bob 有一個(gè)多項(xiàng)式g(x)=x2?5x+6.Alice 利用f(x)中的系數(shù),每一列擴(kuò)展1 個(gè)0,構(gòu)造矩陣A,Bob 利用g(x)的系數(shù)構(gòu)造矩陣B,Alice 計(jì)算出初等變換矩陣P3×3發(fā)送給Bob,其中

Bob 收到P后,計(jì)算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)式整除問(wèn)題保密計(jì)算方案

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

輸入:Alice 有一個(gè)多項(xiàng)式f(x)=anxn+an?1xn?1+ ··· +a0x0,Bob 有一個(gè)多項(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在半誠(chéng)實(shí)模型下,協(xié)議3 是正確的.

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

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

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

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

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

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

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

pi表示第i個(gè)素?cá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ù)的整除判定問(wèn)題就轉(zhuǎn)換為多項(xiàng)式整除問(wèn)題.若(f(x)|g(x))∨(f(x)|g(x)),就是兩個(gè)數(shù)據(jù)具有整除關(guān)系;否則不是.具體協(xié)議與協(xié)議3 類似,本文不予給出.

6 性能分析

6.1 效率分析

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

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

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

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

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

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

表2 直線與直線位置關(guān)系判定方案的效率對(duì)比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.語(yǔ)言:MATLAB.協(xié)議1:保密的計(jì)算矩陣與增廣矩陣秩相等問(wèn)題.設(shè)定:矩陣為方陣,方陣內(nèi)每一個(gè)數(shù)據(jù)為8 位大隨機(jī)數(shù),方陣的維數(shù)間隔為1.圖4 描述了協(xié)議1 的執(zhí)行時(shí)間隨著方陣維數(shù)增長(zhǎng)的變化規(guī)律.

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

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

7 結(jié)論

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