基于閾值的向量保密計算*

王穎囡, 竇家維, 葛 雪

陜西師范大學 數學與信息科學學院, 西安710119

1 引言

在實際生活中, 很多問題都可以抽象為向量比較問題從而得以解決. 例如公司A 要找尋商業合作伙伴, 但希望合作公司在某些方面能達到一定的條件(例如總資產、信譽值等), 對這些條件進行一定的標準化即可表示為向量x= (x1,··· ,xn), 而B 公司的數據也可表示成對應的向量y= (y1,··· ,yn), 要判定公司A 與公司B 是否能達成合作就轉化為判定xi ＞yi的分量個數是否達到了公司A 自己的設定值t.此外, 在進行樣本特征匹配檢測時, 僅需要判定兩特征串相同字符個數是否達到某個閾值, 若達到設定的閾值, 就說明兩者匹配, 否則不匹配, 將兩特征串表示成向量x= (x1,··· ,xn),y= (y1,··· ,yn), 則問題就轉化為判定xi=yi的分量個數是否達到了閾值t. 由此可見, 向量為解決一些實際問題提供了基本方法. 但在很多情況下, 向量中的數據涉及到人們的隱私, 人們不希望在計算的過程中泄露信息. 因此在保護隱私的前提下進行向量計算有很大的實際意義. 安全多方計算作為密碼學的一個重要研究方向, 可以很好地解決這一問題.

安全多方計算是一種保護隱私數據的計算方式, 是指參與者利用其私有數據進行合作計算, 并得到所需結果, 同時在計算結束后, 每個參與者不能獲得其他參與者隱私數據的任何額外信息. Yao 在文獻[1]中最早提出兩方安全計算問題, 隨后, Goldreich 等人提出了安全多方計算問題, 并對其進行了深入的研究[2,3], 他們證明了所有的安全多方計算問題理論上都是可解的并提出了通用的解決方案, 推動了安全多方計算的研究發展. 由于通用方案的復雜性較高而不實用, 人們需要針對具體問題尋求具體的簡單高效的解決方案. 目前已研究的問題主要包括保密的科學計算[4,5]、保密的計算幾何問題[6-8]、保密的數據挖掘[9]、保密的集合運算[10,11]、保密的向量計算[12-18]以及其他安全多方計算問題.

目前, 有關向量的安全計算問題的研究包括向量的求和[12]、向量的線性組合[13]、向量內積的計算[14]、向量優勢計算[15-18]. 文獻[15] 首次提出安全向量優勢問題, 即對于向量x= (x1,··· ,xn),y=(y1,··· ,yn), 保密判定是否x,y的所有分量具有關系xi ＞yi. 文獻[15] 將兩個向量x,y分別轉化為4n維向量并借助百萬富翁協議對于向量中對應分量分別進行大小比較, 從而得到所需結果, 計算復雜性較高.文獻[16] 將向量的每個分量轉化為二進制數表示, 通過對二進制數大小比較的方法解決向量優勢問題, 由于在協議中需要加密每個二進制串, 協議的復雜性也非常高.

文獻[17] 對于向量優勢問題進行了推廣, 研究向量優勢統計問題, 即統計向量x,y中, 滿足xi ＞yi,i ∈[1,n] 的分量個數, 雖然相比文獻[15,16] 計算復雜性有所降低, 但協議需要借助茫然第三方幫助執行. 文獻[18] 在研究向量優勢統計問題時假設向量的所有分量限制在某個全集內取值, 應用編碼方法解決問題, 由于所設計協議要求數據在一個全集內取值, 并且協議的計算復雜性與全集的勢線性相關, 這些都限制了協議的應用范圍. 我們也注意到, 文獻[17,18] 中構造的向量優勢保密統計協議無法直接用于解決向量優勢問題, 這是由于在向量x關于向量y不具有向量優勢情形下, 將會泄露滿足xi ＞yi,i ∈[1,n]的分量個數, 這在向量優勢保密判定中是不允許的.

從上面分析可知, 對于向量優勢統計問題, 或者更進一步, 判斷向量x,y中滿足xi ＞yi,i ∈[1,n] 的分量個數是否達到某個閾值t的問題(稱其為向量優勢閾值問題), 以及對于向量優勢判定問題需要設計更高效的安全計算協議.

另一方面, 向量相等問題在實際中有很多應用, 這個問題作為兩數相等判定問題的推廣, 可通過約定向量分量位數從而把向量與整數一一對應(例如約定分量位數為2, 將向量(2,1,0,42) 對應于整數02010042), 并應用已有的兩數相等比較協議[4]獲得解決. 而對于某些實際應用問題, 比如在上面所述的信息匹配問題, 我們需要保密判定兩個向量x和y中滿足xi=yi,i ∈[1,n] 的分量個數是否達到某個閾值t, 而不希望泄露其他信息(稱其為向量等分量數閾值問題), 這一問題很難直接應用兩數相等比較協議獲得解決. 在之前的工作中, 為解決這一問題, 我們將向量的各個分量限制在一個全集中, 并給出了具體的解決方案. 但全集的限制也增加了協議的局限性, 因此設計新的無全集限制的向量等分量數閾值計算協議是必要的.

本文主要研究上面所提出的向量優勢閾值問題(包括向量優勢判定問題) 與向量等分量數閾值問題,對于這些問題設計高效的保密計算協議. 本文主要貢獻如下:

(1) 對向量優勢統計與向量等分量數統計問題進行擴展, 將其與閾值結合, 解決向量優勢閾值問題與等分量數閾值保密計算問題. 特別地, 當設置閾值t為向量的維數時即可獲得向量優勢問題與向量相等判定問題的解決方案.

(2) 以Paillier 加密方案為基礎, 靈活運用加密算法的加法同態性, 并以命題2 和注解2 所給的性質和保密比較兩數大小的方法為基礎, 結合問題轉化及加密選擇等技巧, 在無全集限制條件下對于上述問題設計保密計算協議. 應用模擬范例嚴格證明了協議的安全性. 所得到的向量優勢判定協議與已有相關結果比較, 具有較低的計算復雜度與通信復雜度.

(3) 本文所研究問題具有重要的實際意義, 所設計的協議具有廣泛的應用性, 可作為基本工具解決更多的實際應用問題(具體參看第6 節推廣應用部分).

2 預備知識

2.1 安全性定義

半誠實模型 半誠實參與者[3]是指在協議執行過程中按照協議要求忠實地履行協議的參與者, 與此同時, 他們可能會收集和保留在協議執行過程中獲得的所有信息, 并在協議執行后試圖根據這些信息推算出其他參與者數據的額外信息. 若在協議中, 所有的參與者均為半誠實參與者, 稱這樣的計算模型為半誠實模型. 本文協議均在半誠實模型下設計.

安全性定義模擬范例是目前多方保密計算研究中普遍采用的證明方法. 在執行協議過程中, 如果任何半誠實參與者所獲得的信息都可以通過自己的輸入和輸出進行模擬, 若模擬時得到的消息序列與實際過程得到的消息序列不可區分, 即參與者從協議執行過程中得不到其他參與者的任何有價值信息, 就認為該協議是安全的. 本文采用模擬范例對協議進行安全性證明. 具體過程如下.

假設有概率多項式時間函數f(x,y) : (x,y)→(f1(x,y),f2(x,y)),π為計算函數f的一個兩方協議.記協議的參與者為Alice 和Bob, 他們的輸入分別為x,y, 協議執行中Alice 得到的信息序列記為

2.2 Paillier 加密方案

因此Paillier 加密方案具有加法同態性.

Paillier 密碼系統是語義安全的. 一個密碼系統是語義安全的, 意味著同一明文可以加密成多個不同的密文形式, 并且所有密文在計算上都是不可區分的.

注解1 關于Paillier 加密方案的安全性簡單敘述如下: 首先, 由于Paillier 加密方案是概率加密方案, 因此是IND-CPA 安全的; 又由于Paillier 加密方案具有加法同態性, 因此不具有IND-CCA2 安全性. Paillier 加密方案是否具有同態加密方案中最強的IND-CCA1 安全性是眾多學者近年來一直努力解決的一個公開問題. 近期文獻[20] 關于這一問題給出了下面的結果: Paillier 方案是IND-CCA1 安全的當且僅當DCRSCCR問題是困難的(上面所出現的各種縮寫符號的具體含義以及對于研究結果的詳細論證請參閱文獻[20]). 一個密碼系統是IND-CPA 安全的(即語義安全的), 意味著同一明文可以加密成多個不同的密文形式, 并且所有密文都是計算不可區分的. 在這個安全性概念中, 任何具有概率多項式時間圖靈機的敵手都無法獲得關于給定密文所對應明文的任何信息. 本文主要以Paillier 加密方案為基礎設計協議, 在下文中所做的密文乘積運算和模乘運算均是在模N2的意義下進行的.

3 向量優勢閾值問題保密計算

3.1 問題描述及計算原理

問題描述 為了敘述方便, 我們首先引入下面概念和函數.

定義1 對于兩個n維向量x= (x1,··· ,xn) 和y= (y1,··· ,yn), 將兩個向量中滿足關系xi ＞yi,i ∈[1,n] 的元素個數稱為x關于y的優勢度, 用記號F(x,y) 表示.

對于給定的向量x,y以及一個正整數t, 定義函數Ft(x,y) 如下: 如果F(x,y)≥t, 令Ft(x,y)=1,否則令Ft(x,y)=0, 并稱Ft(x,y) 為向量優勢閾值函數.

定義2 假設C=E(h) 是應用Paillier 加密方案中公鑰pk 加密的0 或1 的密文,C?1為其在密文空間乘法群中的逆元. 根據Paillier 加密算法的加法同態性可知,T(C) =E(1)C?1=E(1?h), 即如果C為0 的密文, 則T(C) 為1 的密文; 如果C為1 的密文, 則T(C) 為0 的密文, 即密文T(C) 對于C所對應的明文1 或0 進行了翻轉. 在此意義下我們稱T(C)=E(1)C?1為翻轉運算.

本節中我們希望研究的問題是: 假設Alice 和Bob 分別擁有私密向量x和y, 并有一個商定好的閾值t, 他們希望合作保密計算函數Ft(x,y), 計算結束后不泄露兩個私密向量的任何額外信息.

基本結論 在下面討論中, 需要用到一些基本結論, 首先對其進行陳述并給出證明.

命題1 對任意整數a,b, 有下面結論成立:

(a)a ＞b當且僅當2a ＞2b+1;

(b)a ≥b當且僅當2a+1＞2b.

命題1 的作用在計算原理部分以及本節最后注解2 中有特別說明.

本文主要是應用Paillier 加密方案設計協議, 我們希望根據某一密文的解密結果來判定其對應明文的符號, 因此證明下面命題.

命題2 在Paillier 加密方案中, 假設a,b在明文空間ZN中取值. 令C=E(a)E(b)?1以及w=D(C). 則有下面結論:

(a)w=0 當且僅當a=b;

(b) 如果0≤a,b ＜N/2, 則可知: 0＜w ＜N/2 當且僅當a ＞b;N/2＜w ＜N當且僅當a ＜b.證明: 根據Paillier 加密算法的加法同態性,C=E(a)E(b)?1=E(a ?bmodN), 對C進行解密,解密結果為w=D(C)=a ?bmodN.

(a) 首先,w=a ?bmodN= 0 當且僅當存在整數k, 使得a ?b=kN. 又根據a,b ∈ZN, 可知?N ＜a ?b ＜N, 于是可知a ?b=kN成立當且僅當k=0, 即a=b.

(b) 在條件0≤a,b ＜N/2 之下,?N/2＜a ?b ＜N/2. 有下面結論成立:

(i) 首先可知w=a ?bmodN ?=N/2;

(ii) 由(a) 可知, 如果a=b, 則有w=0;

(iii) 若a ＞b, 則有0＜a ?b ＜N/2, 因此0＜w=a ?bmodN=a ?b ＜N/2;

(iv) 若a ＜b, 則有?N/2＜a ?b ＜0, 因此N/2＜w=a ?bmodN=a ?b+N ＜N.綜上, 命題2(b) 得證.

注解2 在下文中主要應用命題2 的基本思想保密比較兩個數的大小關系. 假設Alice 和Bob 的私密數據分別為x和y, 且Alice 具有私鑰, 比較方法為: (i) Alice 加密x并將E(x) 發送給Bob; (ii) Bob 選擇隨機正整數r, 計算C= [E(x)E(y)?1]r, 將C發送給Alice; (iii) Alice 解密C, 得到m=r(x ?y)modN.

記a=rx,b=ry, 如果a,b滿足命題2(b) 的條件, 則由命題2, Alice 根據m的值可以獲得x,y的大小關系, 而Alice(或Bob) 不能獲得數據y(或x) 的任何額外信息.

計算原理 向量優勢閾值問題的保密計算主要分為兩部分, 首先計算h=F(x,y), 在此基礎上進一步比較h與t的大小關系. 具體如下:

(1) 假設在協議中Alice 和Bob 應用Paillier 加密算法進行保密計算, Alice 具有私鑰.

(a) 為了在計算F(x,y) 的過程中隱藏向量x與y中有哪些分量對應相等, Alice 和Bob 需要分別將x和y轉化為u=(u1,··· ,un) 和v=(v1,··· ,vn), 其中ui=2xi和vi=2yi+1(此時必有ui ?=vi). 由命題1(a) 可知,F(x,y) =F(u,v). 因此可將計算F(x,y) 的問題轉化為計算F(u,v).

(b) 為了保密計算F(u,v), 基本思想是利用加密算法的加法同態性進行有關計算, 使得Alice 持有向量t= (r1(u1?v1),··· ,rn(un ?vn)) := (t1,··· ,tn), Bob 持有隨機向量r=(r1,··· ,rn)(其中每個分量為非零隨機整數).

(2) Alice 和Bob 合作進行加密選擇運算, 以確定F(u,v). 具體過程如下.

(a) Alice 加密. Alice 對向量t中各分量ti的符號信息(即正或負) 進行標記, 如果ti為正(負),則以hi=1(hi=0) 進行標記. Alice 加密hi, 并將E(h1),··· ,E(hn) 發送給Bob;

(b) Bob 進行選擇運算. Bob 根據自己持有的隨機向量r中各分量ri,i ∈[1,n] 的符號對于E(hi)選擇不同的運算方式, 以便將hi的符號信息轉化為ui ?vi的符號信息. 具體運算方式是, 當ri為正時保持E(hi) 不變; 當ri為負時, 對密文E(hi) 進行翻轉運算得到T[E(hi)].此時u,v中具有ui ＞vi性質的分量對應1 的密文, 其他分量對應0 的密文.

(c) 應用加密算法的加法同態性, 根據(b) 最后得到的密文即可計算得到F(u,v) 的密文.

(3) 根據F(u,v) 的密文以及閾值t, 以命題1(b) 與命題2 為基礎可以判定兩者大小關系, 最終得到Ft(u,v), 即Ft(x,y).

由于在計算中多次應用命題2, 因此在協議設計中對于輸入數據以及隨機數的選擇范圍需有一定限制,以保證應用命題2 所得結果是正確的. 具體協議設計如下.

3.2 協議設計

3.3 協議的正確性和安全性

下面分別證明協議1 的正確性和安全性. 我們有下面結果.

定理1 協議1 能夠正確地計算向量優勢閾值函數Ft(x,y).

證明: (1) 在協議第(2) 步中, Bob 對于Alice 發來的加密數據E(u), 選擇隨機向量r計算wi. 根據Paillier 加密方案的加法同態性,wi=E(ri(ui ?vi)modN), 因此Alice 在協議第(3) 步得到的解密結果是di=ri(ui ?vi)modN.

綜合(i)(ii) 可知, 在協議第(4)(a) 步中, 對于每個i ∈[1,n], Bob 計算得到的密文數據Hi為1 的密文當且僅當ui ＞vi, 而Hi為0 的密文當且僅當ui ＜vi. 協議第(4)(b) 步中Bob 計算所有H1,··· ,Hn的乘積H, 由加密算法的加法同態性可知乘積密文H即為F(u,v) 的密文.

(4) 協議第(4)(c) 和第(5) 步主要是根據F(u,v) 的密文H對F(u,v) 與閾值t進行大小比較.

由于對每個i ∈[1,n],wi=[E(ui)E(vi)?1]ri, 其中ri為Bob 選擇的非零隨機整數, Alice 解密后得到di=ri(ui ?vi)modN. 這時考慮兩種情形: 如果0＜di ＜N/2, Alice 可知di=ri(ui ?vi); 如果N/2＜di ＜N, Alice 可知di=ri(ui ?vi)+N. 這時由于ri為Bob 選擇的隨機數,ui又不等于vi, 因此無論對于哪種情形, 對于Alice 來說di都和隨機數不可區分, 因此對于Alice 來說,wc≡w′.

同理, Alice 在解密S=[E(1)H2E(2t)?1]r后得到s=r(2h+1?2t)modN, 其中h=F(u,v). 這時仍需要考慮兩種情形: 如果0＜s ＜N/2, 則Alice 可知s=r(2h+1?2t); 如果N/2＜s ＜N, 則Alice 可知s=r(2h+1?2t)+N. 由正確性證明過程知, Alice 根據s的取值范圍僅可獲知(2h+1?2t)的正負, 從而獲知h和t的大小關系, 這是協議規定的輸出結果. 由于r為Bob 選擇的任意隨機正整數,無論對于哪種情形,S對于Alice 來說都和隨機數不可區分, 故有Sc≡S′. 又由于Ft(x,y′) =Ft(x,y),因此

綜上所述, 在半誠實模型下協議1 是CPA 安全的, 如果DCRSCCR問題是困難的, 協議1 還是CCA1安全的.

注解3 協議1 所解決的向量優勢閾值保密計算問題可看成是向量優勢保密判定問題的拓展. 因為當設置閾值t=n時, 協議1 可用于解決向量優勢保密判定問題, 此時, 根據協議1 的輸出結果, 如果Ft(x,y)=1, 則知F(x,y)≥n, 說明x是y的優勢向量; 否則, 即可知x不是y的優勢向量.

注解4 (1) 在協議1 中, 我們首先將計算F(x,y) 的問題轉化為計算F(u,v) 的問題, 這個轉化過程在保證安全性部分是非常重要的. 這是因為若不進行轉化, 在協議1 的(3)(a) 步, Alice 解密wi會得到di=ri(xi ?yi)modN. 此時若存在j ∈[1,n], 使得dj= 0, Alice 根據命題2 將得到xj=yj, 即得到Bob 向量中yj的值. 此外, Alice 還可根據使得di= 0 的元素個數獲知滿足xi=yi的分量個數. 這些信息都是協議不允許泄露的額外信息. 因此在協議中需要將xi,yi轉化為ui= 2xi,vi= 2yi+1, 以保證di=ri(ui ?vi)modN恒不為0.

(2) 在協議第二部分, 比較h=F(u,v) 與閾值t的大小時, 也是將問題轉化為確定r(2h+1?2t) 的正負問題. 若不進行轉化, 在Alice 解密后會得到s=r(h ?t), 從而得到h=t是否成立, 這一信息也是協議不允許泄露的額外信息. 通過轉化保證了在解密S后得到的s=D(S)=r(2h+1?2t)modN ?=0,從而根據命題2, Alice 僅能得知2h+1＞2t或2h+1＜2t, 即h ≥t或h ＜t.

我們注意到, 文獻[21] 設計了一個云服務器外包計算方式的數據比較大小協議, 在此協議中用到了類似命題1(b) 的轉換技巧. 在本文協議1(或下面的協議2) 中, 需要計算滿足xi ＞yi(或xi=yi) 的個數h(或l), 以及其與閾值的大小關系, 即h ≥t(或l ≥t) 是否成立, 命題1(a)(b) 的轉化技巧在協議設計中都將發揮作用.

4 向量等分量數閾值保密計算

問題描述 類似地, 為了本部分敘述方便, 我們引入下面概念和函數.

定義3 對于兩個n維向量x= (x1,··· ,xn) 和y= (y1,··· ,yn), 將兩個向量中滿足關系xi=yi,i ∈[1,n] 的分量個數稱為x與y的等分量數, 用記號L(x,y) 來表示.

對于給定的向量x,y以及一個正整數t, 定義函數Lt(x,y) 如下: 如果L(x,y)≥t, 令Lt(x,y)=1,否則令Lt(x,y)=0. 并稱Lt(x,y) 為等分量數閾值函數.

本節中我們希望研究的問題是: 假設Alice 和Bob 分別擁有私密向量x和y, 并有一個商定好的閾值t, 他們希望合作保密計算函數Lt(x,y), 計算結束后不泄露兩個私密向量的任何額外信息.

計算原理

由于協議2 的(1)-(4)(a) 步實際上是對不同的輸入并行(兩次) 執行協議1 的(1)-(4)(a) 步, 協議的第(4)(b)(c) 與第(5) 步執行都類似于協議1 的相應執行過程. 由協議1 類似可得, 如果DCRSCCR問題是困難的, Paillier 加密方案就是CCA1 安全的, 協議2 就是CCA1 安全的. 類似于協議1, 可證明協議2 的安全性, 此處不再贅述, 僅給出下面定理.

定理4 在半誠實模型下協議2 是CPA 安全的.

注解5 協議2 所解決的向量等分量數閾值保密計算問題可看成向量相等判定問題的推廣. 由于當設置閾值t=n時, 此時若Lt(x,y)=1, 則說明l ≥n, 即兩向量相等; 否則說明兩向量不相等.

5 協議效率分析

5.1 本文協議復雜性分析

為了便于分析和比較, 在進行計算復雜性分析時, 僅考慮費時較多的模指數運算, 忽略其他簡單運算.在Paillier 加密方案中, 一次加密或解密各需要2 次模指數運算, 下面將以執行協議所需要的模指數運算次數來衡量計算復雜性.

假設向量的維數為n, 在協議1 中, Alice 共需進行2n次加密運算與n+1 次解密運算, Bob 需要進行n+2 次加密運算與n+2 次模指數運算. 此外, 記滿足ri ＜0,i ∈[1,n] 的隨機數個數為c1, 在協議中Bob 需進行c1次翻轉運算, 相當于進行c1次模指數運算(每次翻轉運算采用相同的1 的密文E(1)).綜上, 協議1 共需進行3n+2 次加密運算,n+1 次解密運算與n+c1+2 次模指數運算, 共相當于進行了8n+c1+7 次模指數運算. 當c1=n時, 協議1 具有最高的計算復雜度, 需進行9n+7 次模指數運算.

在協議2 中, Alice 共需進行4n次加密運算與2n+1 次解密運算. Bob 需進行2n+2 次加密運算與3n+2 次模指數運算. 此外, 若記滿足ri,?ri的隨機數個數為c2, 則在協議中需進行c2次翻轉運算, 即進行c2次模指數運算. 綜上, 協議2 共需進行6n+2 次加密運算, 2n+1 次解密運算與3n+c2+2 次模指數運算, 相當于進行了17n+c2+7 次模指數運算. 當c2=2n時, 協議2 具有最高的計算復雜度, 需進行19n+7 次模指數運算.

本文協議的通信復雜性以通信輪數來衡量. 在協議1 中, (1)-(2) 步Alice 和Bob 進行了1 輪通信,(3)-(4) 步又進行了1 輪通信, 故通信復雜性為2. 同樣地, 協議2 的(1)-(2), (3)-(4) 步Alice 和Bob 分別進行了1 輪通信, 故共需進行2 輪通信.

5.2 與已有協議對比分析

當閾值t=n時, 本文協議1 即為安全向量優勢協議. 文獻[15,16] 對這一問題進行了研究, 在文獻[15] 中, 協議4 計算向量優勢問題. 在協議的前兩步中, Alice 需要進行4n次加密與4n次解密, Bob需要進行1 次加密運算. 相當于共進行12n+2 次模指數運算. 此外, 協議最后兩步還需調用4n次百萬富翁協議以及4n次相等測試協議才能得到結果. 協議的前兩步共需要進行1 輪通信, 在并行執行時, 百萬富翁協議與相等測試部分各需要1 輪通信, 故協議的通信復雜度為3. 在文獻[16] 中, 運用具有加法同態的ElGamal 加密方案解決這一問題. 在加法同態的ElGamal 加密方案中, 進行1 次加密相當于進行3次模指數運算, 解密則需要進行1 次模指數運算. 若約定二進制數位數為k, 在協議1 中Alice 對自己的向量數據需進行nk次加密運算, 此外還需要進行kn次解密運算, 相當于共進行3nk+k次模指數運算.Bob 則需要進行2nk+2 次加密運算以及kn次模指數運算, 相當于共進行了3nk+kn+6 次模指數運算. 因此, 文獻[16] 中向量優勢判定協議計算復雜度為6nk+2kn+6. 在協議執行中, Alice 與Bob 之間共進行了1 輪通信. 由此可知, 相比文獻[15,16], 本文協議1 效率更高.

此外, 文獻[18] 應用Paillier 加密方案研究向量優勢統計問題, 若全集的勢為m, 向量的維數為n, 在協議執行過程中共需要進行mn次加密運算與1 次解密運算, 即2(mn+1) 次模指數運算. 本文協議1 作為向量優勢統計問題的推廣問題, 相比文獻[18] 去除了元素范圍的限制, 在元素范圍取值較大時(即m較大時) 本文協議1 也有著明顯的優勢.

5.3 實驗分析

為了進一步測試本文協議的執行效率與實際可行性, 設計模擬實驗來測試執行協議所需要的時間.

實驗測試環境: Windows 10 64 位(家庭版) 操作系統, 處理器是Intel(R)Core(TM)i5-6600 CPU@3.30 GHz, 內存是8.00 GB, 用Java 語言在MyEclipse 上運行實現.

實驗方法: 通過模擬實驗測試本文協議所用時間, 根據協議執行時間驗證方案效率. 在本文中, 在向量維數n分別為2,4,6,··· ,20 時, 對n的每個設定值進行1000 次模擬實驗, 并統計協議1 與協議2 的執行時間的平均值.

協議1 與協議2 的運行時間如圖1 所示. 由圖1 可知, 隨著向量維數的增大, 協議1 和協議2 的執行時間都線性增加, 協議2 的執行時間高于協議1.

當向量維數較高時, 協議1, 2 的執行時間也隨之線性增加. 經實驗, 對于較高維數的向量, 本文協議仍適用. 當向量維數為500 維時, 執行協議1 耗時13 415 毫秒, 近似于13 秒. 執行協議2 耗時27 918 毫秒,近似于28 秒.

圖1 協議1,2 的執行時間隨向量維數增大的變化規律Figure 1 Execution time of protocol 1,2 with increase of vector dimension

6 推廣應用

6.1 區間關系判定

區間關系保密判定問題在實際生活中有著廣泛的應用. 例如公司A 與公司B 希望進行商品交易,在進行價格協商時需要先確認兩公司是否有達成交易的可能性. 假設A 公司認為商品的理想出售價格在a1到b1之間, B 公司則想以最低a2, 最高b2的價格購買A 公司的商品. 因此首先需要判定區間(a1,b1),(a2,b2) 是否相交, 即兩者是否有達成交易的可能. 由于區間(a1,b1) 中a1,b1分別表示A 公司能接受的最低成交價與預計的最高成交價,a2,b2分別表示B 公司開出的購買價格范圍, 這兩個區間均屬于公司的商業機密. 因此需要在保證兩方數據隱私的情況下對兩區間關系進行判定, 以判定兩公司是否有達成交易的可能. 利用本文所設計的協議即可解決這一問題. 具體描述如下.

問題描述: 假設Alice 有私密區間(a1,b1), Bob 有私密區間(a2,b2), 他們希望保密判定兩區間是否相交.

基本原理: 如圖2 所示, 區間(a1,b1),(a2,b2) 相交當且僅當b1＞a2,a1＜b2.

圖2 兩區間相交Figure 2 Intersection of two intervals

首先,Alice 和Bob 商定一個較大的正數d,使得b1,b2＜d. 記向量x=(d?a1,b1),y=(d?b2,a2),設閾值t= 2. 于是判定兩區間是否相交的問題即可轉化為計算向量優勢閾值函數Ft(x,y) 的問題, 調用協議1 即可.

6.2 字符串模式匹配

保護隱私的字符串模式匹配在信息查詢與過濾、病毒檢測、生物信息檢測等方面都有著廣泛的應用.例如在郵件收發中, 系統會根據郵件內容是否包含某些不良信息決定是否對郵件進行攔截. 但考慮到郵件屬于私密信件, 用戶不希望泄露給其他方, 包括系統. 因此需要在不泄露郵件內容的情況下判定其中是否包含不良信息. 此時, 將需要攔截的關鍵詞構成不良信息庫, 通過對這些關鍵詞與郵件內容進行保密的字符串模式匹配即可實現保護隱私的郵件攔截. 由此可見, 保護隱私的字符串模式匹配問題研究有很大的實際意義. 利用本文所設計的協議即可解決這一問題. 具體描述如下.

問題描述Alice 有目標字符串A=a1···an, Bob 有模式字符串B=b1···bm(m ≤n). 他們希望保密判定在A中是否存在子串SAi=ai···ai+m?1=B.

計算原理 首先運用ASCII 碼將每個字符與一個三位十進制數一一對應(例如對于字符串‘Love’, 字符‘L’ 對應的ASCII 碼為076, ‘o’ 對應為111, ‘v’ 對應為118, ‘e’ 對應為101, 因此‘Love’ 所對應的數字串即為076111118101). Bob 將字符串B所對應的數字串記為y. Alice 將字符串A=a1···an以m個連續字符為單位進行分割, 記分割后的字符串依次為SA1=a1···am,··· ,SA,n?m+1=an?m+1···am.并分別用xA1,··· ,xA,n?m+1表示其所對應的數字串. 令閾值t=1,數組x=(xA1,··· ,xA,n?m+1),y=(y,··· ,y) 應用協議2 計算向量x,y的等分量數與t的大小關系Lt(x,y) 即可得到匹配結果. 若Lt(x,y) = 1, 則說明滿足xAi=y的元素個數至少為1, 即必存在k ∈[1,n ?m+1], 使得xAk=y. 由于xAk與字符串SAk,y與字符串B一一對應, 故必存在SAk=B, 即A,B模式匹配, 反之則不匹配.

7 結論

本文在安全向量優勢問題的基礎上, 將向量優勢統計與閾值計算相結合, 研究更為一般的問題, 即向量優勢與等分量數閾值計算問題. 若閾值與向量維數相等, 則為安全向量優勢與向量相等問題. 本文針對這兩個問題設計了高效的計算協議, 同時, 將所設計的協議作為基本工具去解決其他安全多方計算問題,具體例舉了區間關系判定問題與方程組解的判定問題. 在下一步工作中, 將繼續研究在惡意模型下的高效安全向量計算方案.