王穎囡, 竇家維, 葛 雪

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

1 引言

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

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

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

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

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

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

本文主要研究上面所提出的向量優(yōu)勢閾值問題(包括向量優(yōu)勢判定問題) 與向量等分量數(shù)閾值問題,對(duì)于這些問題設(shè)計(jì)高效的保密計(jì)算協(xié)議. 本文主要貢獻(xiàn)如下:

(1) 對(duì)向量優(yōu)勢統(tǒng)計(jì)與向量等分量數(shù)統(tǒng)計(jì)問題進(jìn)行擴(kuò)展, 將其與閾值結(jié)合, 解決向量優(yōu)勢閾值問題與等分量數(shù)閾值保密計(jì)算問題. 特別地, 當(dāng)設(shè)置閾值t為向量的維數(shù)時(shí)即可獲得向量優(yōu)勢問題與向量相等判定問題的解決方案.

(2) 以Paillier 加密方案為基礎(chǔ), 靈活運(yùn)用加密算法的加法同態(tài)性, 并以命題2 和注解2 所給的性質(zhì)和保密比較兩數(shù)大小的方法為基礎(chǔ), 結(jié)合問題轉(zhuǎn)化及加密選擇等技巧, 在無全集限制條件下對(duì)于上述問題設(shè)計(jì)保密計(jì)算協(xié)議. 應(yīng)用模擬范例嚴(yán)格證明了協(xié)議的安全性. 所得到的向量優(yōu)勢判定協(xié)議與已有相關(guān)結(jié)果比較, 具有較低的計(jì)算復(fù)雜度與通信復(fù)雜度.

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

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

2.1 安全性定義

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

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

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

2.2 Paillier 加密方案

因此Paillier 加密方案具有加法同態(tài)性.

Paillier 密碼系統(tǒng)是語義安全的. 一個(gè)密碼系統(tǒng)是語義安全的, 意味著同一明文可以加密成多個(gè)不同的密文形式, 并且所有密文在計(jì)算上都是不可區(qū)分的.

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

3 向量優(yōu)勢閾值問題保密計(jì)算

3.1 問題描述及計(jì)算原理

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

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

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

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

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

基本結(jié)論 在下面討論中, 需要用到一些基本結(jié)論, 首先對(duì)其進(jìn)行陳述并給出證明.

命題1 對(duì)任意整數(shù)a,b, 有下面結(jié)論成立:

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

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

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

本文主要是應(yīng)用Paillier 加密方案設(shè)計(jì)協(xié)議, 我們希望根據(jù)某一密文的解密結(jié)果來判定其對(duì)應(yīng)明文的符號(hào), 因此證明下面命題.

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

(a)w=0 當(dāng)且僅當(dāng)a=b;

(b) 如果0≤a,b ＜N/2, 則可知: 0＜w ＜N/2 當(dāng)且僅當(dāng)a ＞b;N/2＜w ＜N當(dāng)且僅當(dāng)a ＜b.證明: 根據(jù)Paillier 加密算法的加法同態(tài)性,C=E(a)E(b)?1=E(a ?bmodN), 對(duì)C進(jìn)行解密,解密結(jié)果為w=D(C)=a ?bmodN.

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

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

(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 在下文中主要應(yīng)用命題2 的基本思想保密比較兩個(gè)數(shù)的大小關(guān)系. 假設(shè)Alice 和Bob 的私密數(shù)據(jù)分別為x和y, 且Alice 具有私鑰, 比較方法為: (i) Alice 加密x并將E(x) 發(fā)送給Bob; (ii) Bob 選擇隨機(jī)正整數(shù)r, 計(jì)算C= [E(x)E(y)?1]r, 將C發(fā)送給Alice; (iii) Alice 解密C, 得到m=r(x ?y)modN.

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

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

(1) 假設(shè)在協(xié)議中Alice 和Bob 應(yīng)用Paillier 加密算法進(jìn)行保密計(jì)算, Alice 具有私鑰.

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

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

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

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

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

(c) 應(yīng)用加密算法的加法同態(tài)性, 根據(jù)(b) 最后得到的密文即可計(jì)算得到F(u,v) 的密文.

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

由于在計(jì)算中多次應(yīng)用命題2, 因此在協(xié)議設(shè)計(jì)中對(duì)于輸入數(shù)據(jù)以及隨機(jī)數(shù)的選擇范圍需有一定限制,以保證應(yīng)用命題2 所得結(jié)果是正確的. 具體協(xié)議設(shè)計(jì)如下.

3.2 協(xié)議設(shè)計(jì)

3.3 協(xié)議的正確性和安全性

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

定理1 協(xié)議1 能夠正確地計(jì)算向量優(yōu)勢閾值函數(shù)Ft(x,y).

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

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

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

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

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

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

注解3 協(xié)議1 所解決的向量優(yōu)勢閾值保密計(jì)算問題可看成是向量優(yōu)勢保密判定問題的拓展. 因?yàn)楫?dāng)設(shè)置閾值t=n時(shí), 協(xié)議1 可用于解決向量優(yōu)勢保密判定問題, 此時(shí), 根據(jù)協(xié)議1 的輸出結(jié)果, 如果Ft(x,y)=1, 則知F(x,y)≥n, 說明x是y的優(yōu)勢向量; 否則, 即可知x不是y的優(yōu)勢向量.

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

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

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

4 向量等分量數(shù)閾值保密計(jì)算

問題描述 類似地, 為了本部分?jǐn)⑹龇奖? 我們引入下面概念和函數(shù).

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

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

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

計(jì)算原理

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

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

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

5 協(xié)議效率分析

5.1 本文協(xié)議復(fù)雜性分析

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

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

在協(xié)議2 中, Alice 共需進(jìn)行4n次加密運(yùn)算與2n+1 次解密運(yùn)算. Bob 需進(jìn)行2n+2 次加密運(yùn)算與3n+2 次模指數(shù)運(yùn)算. 此外, 若記滿足ri,?ri的隨機(jī)數(shù)個(gè)數(shù)為c2, 則在協(xié)議中需進(jìn)行c2次翻轉(zhuǎn)運(yùn)算, 即進(jìn)行c2次模指數(shù)運(yùn)算. 綜上, 協(xié)議2 共需進(jìn)行6n+2 次加密運(yùn)算, 2n+1 次解密運(yùn)算與3n+c2+2 次模指數(shù)運(yùn)算, 相當(dāng)于進(jìn)行了17n+c2+7 次模指數(shù)運(yùn)算. 當(dāng)c2=2n時(shí), 協(xié)議2 具有最高的計(jì)算復(fù)雜度, 需進(jìn)行19n+7 次模指數(shù)運(yùn)算.

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

5.2 與已有協(xié)議對(duì)比分析

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

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

5.3 實(shí)驗(yàn)分析

為了進(jìn)一步測試本文協(xié)議的執(zhí)行效率與實(shí)際可行性, 設(shè)計(jì)模擬實(shí)驗(yàn)來測試執(zhí)行協(xié)議所需要的時(shí)間.

實(shí)驗(yàn)測試環(huán)境: Windows 10 64 位(家庭版) 操作系統(tǒng), 處理器是Intel(R)Core(TM)i5-6600 CPU@3.30 GHz, 內(nèi)存是8.00 GB, 用Java 語言在MyEclipse 上運(yùn)行實(shí)現(xiàn).

實(shí)驗(yàn)方法: 通過模擬實(shí)驗(yàn)測試本文協(xié)議所用時(shí)間, 根據(jù)協(xié)議執(zhí)行時(shí)間驗(yàn)證方案效率. 在本文中, 在向量維數(shù)n分別為2,4,6,··· ,20 時(shí), 對(duì)n的每個(gè)設(shè)定值進(jìn)行1000 次模擬實(shí)驗(yàn), 并統(tǒng)計(jì)協(xié)議1 與協(xié)議2 的執(zhí)行時(shí)間的平均值.

協(xié)議1 與協(xié)議2 的運(yùn)行時(shí)間如圖1 所示. 由圖1 可知, 隨著向量維數(shù)的增大, 協(xié)議1 和協(xié)議2 的執(zhí)行時(shí)間都線性增加, 協(xié)議2 的執(zhí)行時(shí)間高于協(xié)議1.

當(dāng)向量維數(shù)較高時(shí), 協(xié)議1, 2 的執(zhí)行時(shí)間也隨之線性增加. 經(jīng)實(shí)驗(yàn), 對(duì)于較高維數(shù)的向量, 本文協(xié)議仍適用. 當(dāng)向量維數(shù)為500 維時(shí), 執(zhí)行協(xié)議1 耗時(shí)13 415 毫秒, 近似于13 秒. 執(zhí)行協(xié)議2 耗時(shí)27 918 毫秒,近似于28 秒.

圖1 協(xié)議1,2 的執(zhí)行時(shí)間隨向量維數(shù)增大的變化規(guī)律Figure 1 Execution time of protocol 1,2 with increase of vector dimension

6 推廣應(yīng)用

6.1 區(qū)間關(guān)系判定

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

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

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

圖2 兩區(qū)間相交Figure 2 Intersection of two intervals

首先,Alice 和Bob 商定一個(gè)較大的正數(shù)d,使得b1,b2＜d. 記向量x=(d?a1,b1),y=(d?b2,a2),設(shè)閾值t= 2. 于是判定兩區(qū)間是否相交的問題即可轉(zhuǎn)化為計(jì)算向量優(yōu)勢閾值函數(shù)Ft(x,y) 的問題, 調(diào)用協(xié)議1 即可.

6.2 字符串模式匹配

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

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

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

7 結(jié)論

本文在安全向量優(yōu)勢問題的基礎(chǔ)上, 將向量優(yōu)勢統(tǒng)計(jì)與閾值計(jì)算相結(jié)合, 研究更為一般的問題, 即向量優(yōu)勢與等分量數(shù)閾值計(jì)算問題. 若閾值與向量維數(shù)相等, 則為安全向量優(yōu)勢與向量相等問題. 本文針對(duì)這兩個(gè)問題設(shè)計(jì)了高效的計(jì)算協(xié)議, 同時(shí), 將所設(shè)計(jì)的協(xié)議作為基本工具去解決其他安全多方計(jì)算問題,具體例舉了區(qū)間關(guān)系判定問題與方程組解的判定問題. 在下一步工作中, 將繼續(xù)研究在惡意模型下的高效安全向量計(jì)算方案.