徐新麗

(淮陰工學(xué)院 數(shù)理學(xué)院, 江蘇 淮安 223003)

?

保密計(jì)算高維向量差的范數(shù)及其應(yīng)用

徐新麗

(淮陰工學(xué)院 數(shù)理學(xué)院, 江蘇 淮安 223003)

幾何問(wèn)題的安全多方計(jì)算在保密位置判斷、保密數(shù)據(jù)查詢等方面有著重要的應(yīng)用價(jià)值．目前安全多方計(jì)算幾何問(wèn)題的研究主要集中在平面幾何,較少涉及空間幾何．利用兩方置換協(xié)議設(shè)計(jì)了空間幾何中兩個(gè)高維向量差的范數(shù)計(jì)算協(xié)議,并用模擬范例證明此方案的安全性；避免了高次模指數(shù)運(yùn)算,提高了效率，適用于任何高維向量；給出了保密判斷兩組數(shù)據(jù)是否對(duì)應(yīng)成比例的協(xié)議，并將數(shù)據(jù)對(duì)應(yīng)成比例問(wèn)題轉(zhuǎn)化成三角形構(gòu)成問(wèn)題,避免了多次調(diào)用提高了效率．

安全多方計(jì)算; 高維向量; 數(shù)據(jù)對(duì)應(yīng)成比例協(xié)議

0 引言

安全多方計(jì)算最早由Yao[1]提出,是指在不泄漏各方的輸入數(shù)據(jù)(隱私性)的條件下,能正確完成輸入數(shù)據(jù)的函數(shù)計(jì)算．安全多方計(jì)算的特點(diǎn)使得人們能夠最大限度地利用私有數(shù)據(jù)完成所需的計(jì)算任務(wù)而不破壞數(shù)據(jù)的隱私性．因此在保密的科學(xué)計(jì)算[2]、保密數(shù)據(jù)挖掘[3-4]、保密的幾何計(jì)算[5-6]等方面有著廣泛的應(yīng)用．

幾何問(wèn)題的保密計(jì)算是安全多方計(jì)算中一個(gè)重要的組成部分．針對(duì)此類問(wèn)題,Du等人[7]研究了一些具體的安全多方幾何計(jì)算問(wèn)題及其應(yīng)用．M.J.Atallah等人[5]研究了安全兩方點(diǎn)包含問(wèn)題和兩方多邊形相交問(wèn)題．李順東等人[8]研究了立體幾何對(duì)象的位置關(guān)系問(wèn)題．荊巍巍[9]研究了保密計(jì)算兩圓相交面積問(wèn)題．

數(shù)據(jù)對(duì)應(yīng)成比例問(wèn)題是安全計(jì)算幾何的一個(gè)基本問(wèn)題,它要求參與方各自持有一個(gè)私有向量,保密判斷彼此對(duì)應(yīng)分量是否成比例．這個(gè)問(wèn)題在實(shí)際生活中的應(yīng)用非常重要．如:A、B兩國(guó)達(dá)成協(xié)議各自在太空拓展自己的空間航道,以便進(jìn)行一些秘密的實(shí)驗(yàn),A國(guó)已經(jīng)選定了某一空間航道,B國(guó)想知道自己所選的航道是否和A國(guó)的重合,在不泄露各自隱私的情況下完成合作.

以上應(yīng)用中的場(chǎng)景轉(zhuǎn)化成數(shù)學(xué)模型就是判斷空間兩個(gè)直線是否重合問(wèn)題,可進(jìn)一步轉(zhuǎn)化為數(shù)據(jù)對(duì)應(yīng)成比例問(wèn)題．目前關(guān)于這個(gè)方面的研究并不多見(jiàn)．

針對(duì)數(shù)據(jù)對(duì)應(yīng)成比例問(wèn)題,羅永龍等人[10]利用多次調(diào)用點(diǎn)積協(xié)議和比較相等協(xié)議的方法解決了此問(wèn)題;2011年,趙玉等人[11]先利用數(shù)據(jù)加密技術(shù)和同態(tài)加密方案設(shè)計(jì)了兩組數(shù)據(jù)中對(duì)應(yīng)成比例的個(gè)數(shù)協(xié)議,再調(diào)用個(gè)數(shù)協(xié)議判斷兩組數(shù)據(jù)是否對(duì)應(yīng)成比例．這些方案,由于多次調(diào)用基礎(chǔ)協(xié)議,計(jì)算量大,方案并不高效．本文主要工作有：利用兩方置換協(xié)議,設(shè)計(jì)了空間高維向量差的范數(shù)保密計(jì)算協(xié)議1；在協(xié)議1的基礎(chǔ)上,給出了一個(gè)應(yīng)用，并將兩組數(shù)據(jù)是否對(duì)應(yīng)成比例問(wèn)題轉(zhuǎn)化成三角形構(gòu)成問(wèn)題,設(shè)計(jì)了數(shù)據(jù)對(duì)應(yīng)成比例協(xié)議2；協(xié)議1避免了高次模指數(shù)運(yùn)算,適用于任何高維向量,具有普遍意義，避免了多次調(diào)用基礎(chǔ)協(xié)議問(wèn)題，提高了效率．

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

1.1 安全多方計(jì)算的安全性定義

1) 半誠(chéng)實(shí)參與者

安全多方計(jì)算的協(xié)議運(yùn)行環(huán)境分為半誠(chéng)實(shí)參與者模型和惡意攻擊者模型[12-13],半誠(chéng)實(shí)參與者指協(xié)議方將誠(chéng)實(shí)地執(zhí)行協(xié)議,不會(huì)篡改輸入和輸出信息,但可能會(huì)保留計(jì)算的中間結(jié)果,試圖推導(dǎo)出協(xié)議之外的信息或者他人的信息．

2) 半誠(chéng)實(shí)模型下的安全性定義

Goldreich[12-13]利用比特承諾和零知識(shí)證明理論設(shè)計(jì)了一個(gè)編譯器,這個(gè)編譯器可以將在半誠(chéng)實(shí)參與者條件下保密計(jì)算函數(shù)f的協(xié)議π自動(dòng)生成在惡意參與者條件下也能保密計(jì)算f的協(xié)議π′．新的協(xié)議π′可以迫使惡意參與者以半誠(chéng)實(shí)方式參與協(xié)議的執(zhí)行,否則就會(huì)被發(fā)現(xiàn)．因此大多數(shù)情況下,我們只設(shè)計(jì)半誠(chéng)實(shí)模型下的協(xié)議．當(dāng)我們?cè)O(shè)計(jì)出所需要的半誠(chéng)實(shí)模型下的安全多方協(xié)議時(shí),只要按照Goldreich[12-13]的通用轉(zhuǎn)化方法就可以將原協(xié)議轉(zhuǎn)化為惡意模型下的新協(xié)議．基于這一結(jié)論,本文也只給出半誠(chéng)實(shí)模型下的協(xié)議和相應(yīng)的安全性模擬范例．

設(shè)f(x,y)為概率多項(xiàng)式函數(shù),π是計(jì)算f的協(xié)議,設(shè)Alice擁有x,Bob擁有y,他們要在不暴露x,y的前提下,合作計(jì)算函數(shù)f(x,y)=(f1(x,y),f2(x,y))．計(jì)算的目的是為了讓Alice和Bob分別得到函數(shù)f的兩個(gè)分量f1(x,y),f2(x,y)．Alice在執(zhí)行協(xié)議π的過(guò)程中所得到的視圖記為view1(x,y),輸出記作output1(x,y);同理,Bob的視圖記為view2(x,y),輸出記作output2(x,y)．Goldreich給出計(jì)算不可區(qū)分性的半誠(chéng)實(shí)參與者的安全兩方計(jì)算的定義,表述如下:

定義1[13]協(xié)議π保密地計(jì)算了f(x,y),如果存在概率多項(xiàng)式時(shí)間模擬器S1與S2使得以下兩式同時(shí)成立:

(1)

(2)

此定義說(shuō)明了任何一方參與者視圖中的信息只能從自己輸入和所獲得的輸出中得到,即說(shuō)明任何一方參與者視圖中不包含額外的信息,這樣就保證了在協(xié)議執(zhí)行過(guò)程中,任何一方得不到其他方的私有信息．因此要證明一個(gè)兩方計(jì)算協(xié)議是保密的,就必須構(gòu)造使得式(1)和式(2)成立的模擬器S1與S2．

1.2 同態(tài)加密

同態(tài)加密的概念是Rivest,Adleman,Dertouzos等人[14]1978年提出的．同態(tài)加密的特殊性質(zhì)使我們可以直接對(duì)密文進(jìn)行某些運(yùn)算來(lái)代替對(duì)明文的運(yùn)算取得同樣的效果,這樣不影響明文數(shù)據(jù)的機(jī)密性．同態(tài)加密方法在云計(jì)算和多方保密計(jì)算中都將發(fā)揮重要作用．

Paillier同態(tài)加密算法[9]具有下述性質(zhì):

1.3 安全兩方置換協(xié)議

安全兩方置換問(wèn)題:Alice有一個(gè)秘密向量X=(x1,x2,…,xn),Bob有一個(gè)置換函數(shù)π和一個(gè)秘密向量Y=(y1,y2,…,yn)．Alice需要得到π(X+Y),Alice不能了解π與Y的任意值yi,Bob不能了解X的任意值xi．文[5]給出一個(gè)基于同態(tài)加密方案的兩方安全置換協(xié)議如下：

輸入： Alice有一個(gè)秘密向量X;Bob有一個(gè)置換函數(shù)π和一個(gè)秘密向量Y.

輸出： Alice得到π(X+Y)，

1) 假設(shè)(G,E,D)是Paillier同態(tài)加密方案,τ是設(shè)定的安全參數(shù)．Alice運(yùn)行G(τ)生成同態(tài)加密方案的公鑰和私鑰,用公鑰加密向量X得到E(X)=(E(x1),E(x2),…,E(xn)).

2) Alice將E(X)和公鑰一起發(fā)送給Bob.

3) Bob用公鑰加密Y得E(Y)=(E(y1),E(y2),…,E(yn)),利用同態(tài)的性質(zhì)計(jì)算E(X+Y)=E(X)+E(Y),然后用置換函數(shù)π對(duì)E(X+Y)進(jìn)行置換得π(E(X+Y))．并將結(jié)果發(fā)送給Alice．

4) Alice解密π(E(X+Y))得π(X+Y)．

2 空間高維向量差的范數(shù)

1) 問(wèn)題的描述

兩個(gè)向量差的范數(shù):Alice持有n維向量A=(a1,a2,…,an),Bob持有n維向量B=(b1,b2,…,bn)．Alice和Bob在不泄露各自向量的情況下,計(jì)算向量差的范數(shù):

2) 問(wèn)題的轉(zhuǎn)化和解決

在保密求解‖A-B‖時(shí),若直接對(duì)(ai-bi)調(diào)用前文兩方置換協(xié)議,存在的問(wèn)題是:用同態(tài)加密算法做減法時(shí),結(jié)果可能會(huì)超出明文的范圍,影響解密結(jié)果．

為避免這種情況,本文提出另一種解決方法.

由于

因此

于是得到兩個(gè)向量差范數(shù)的平方:

3) 具體協(xié)議

以下協(xié)議假設(shè)所有的參與者都是在半誠(chéng)實(shí)模型下,網(wǎng)絡(luò)之間傳輸都是公開(kāi)信道．

協(xié)議1 保密計(jì)算高維空間向量差的范數(shù).

輸入: Alice保密輸入n維向量A=(a1,a2,…,an),Bob保密輸入n維向量B=(b1,b2,…,bn),輸出: Alice得到‖A-B‖.

1) Alice和Bob調(diào)用前文的基本兩方置換協(xié)議使Alice得到π(A+B)=(ai+bi,an+bn,…,aj+bj),π是Bob擁有的置換函數(shù)．

3) Bob將計(jì)算的結(jié)果發(fā)送給Alice,Alice將會(huì)計(jì)算出‖A-B‖2,從而得到‖A-B‖．

3 應(yīng)用

3.1 保護(hù)隱私的數(shù)據(jù)成比例判定問(wèn)題

1) 問(wèn)題的描述

已知Alice和Bob分別有一組數(shù)據(jù),記作(a1,a2,…,an)和(b1,b2,…,bn),在不泄露各自秘密的情況下,判斷兩組數(shù)據(jù)是否對(duì)應(yīng)成比例．

2) 問(wèn)題的轉(zhuǎn)化和解決

3) 具體協(xié)議

協(xié)議2 保密判斷兩組數(shù)據(jù)是否對(duì)應(yīng)成比例.

輸入: Alice保密輸入一組數(shù)據(jù)(a1,a2,…,an),Bob保密輸入一組數(shù)據(jù)(b1,b2,…,bn),

輸出: 兩組數(shù)據(jù)對(duì)應(yīng)成比例或不成比例.

1) 令(a1,a2,…,an)=A,(b1,b2,…,bn)=B.

2) Alice和Bob共同調(diào)用協(xié)議1,Alice得到了b=‖B‖和兩個(gè)向量差的范數(shù)c=‖A-B‖.

3) Alice擁有a=‖A‖、b和c,要判斷a、b、c是否能構(gòu)成三角形,就要判斷兩邊之和是否大于第三邊,即判斷a+c>b,b+c>a，a+b>c是否同時(shí)成立．如果成立,兩組數(shù)據(jù)不對(duì)應(yīng)成比例;反之,對(duì)應(yīng)成比例．

4 安全性分析

應(yīng)用安全性模擬范例證明本文兩個(gè)協(xié)議的安全性．由于協(xié)議2是以協(xié)議1為基本協(xié)議設(shè)計(jì)得到,安全性依靠協(xié)議1保障,因此以證明協(xié)議1安全性為主,對(duì)于協(xié)議2只給出安全性結(jié)論．

定理1 協(xié)議1保密計(jì)算高維空間向量差的范數(shù)．

證明 通過(guò)構(gòu)造滿足1)和2)的模擬器S1,S2來(lái)證明本定理．S1工作過(guò)程如下:

1) 給定輸入(A,‖A-B‖),S1隨機(jī)選取一個(gè)n維向量B′=(b1′,b2′,…,bn′),使得‖A-B′‖=‖A-B‖,用A、B′進(jìn)行模擬.

在本協(xié)議中,

view1(A,B)={A,π(A+B),‖A+B‖,‖A‖,‖B‖,‖A-B‖},

令

S1(A,‖A+B‖)={A,π(A+B′),‖A+B′‖,‖A‖,‖B′‖,‖A-B′‖},

因?yàn)椤珹-B′‖=‖A-B‖,所以

同理,用類似的方法構(gòu)造S2,使得

定理2 協(xié)議2保密計(jì)算高維空間平行四邊形的面積．

用類似的方法可以證明定理2,這里不再贅述．

5 效率分析與比較

協(xié)議2和文[10][11]在計(jì)算復(fù)雜性、通信復(fù)雜性以及性能方面的分析和比較如下：

計(jì)算復(fù)雜度: 文[10][11]都使用了公鑰加密算法,因此以加解密的次數(shù)作為衡量計(jì)算復(fù)雜性的指標(biāo)．文[10]加解密O(mn)次,文[11]加解密O(5n-5)次,協(xié)議2加解密O(2n+1)次．因此,協(xié)議2的計(jì)算復(fù)雜度較低．

通信復(fù)雜度: 衡量通信復(fù)雜度的指標(biāo)用協(xié)議交換信息的比特?cái)?shù),或者用通信輪數(shù),在多方保密計(jì)算研究中通常用輪數(shù)文[10]的通信輪數(shù)為4n,文[11]的通信輪數(shù)為3n+1,協(xié)議2的通信輪數(shù)為4．

從以上比較可以看出,當(dāng)n>3時(shí),協(xié)議2比現(xiàn)有協(xié)議的計(jì)算復(fù)雜度低,而且通信復(fù)雜度為一個(gè)常數(shù)級(jí)的,不隨著參數(shù)而發(fā)生變化．因此,協(xié)議2的效率較高．

在協(xié)議2與文[10][11]中的協(xié)議研究范圍相同,因此在性能方面不進(jìn)行比較．

6 總結(jié)

幾何問(wèn)題是安全多方計(jì)算中重要的組成部分,該問(wèn)題在軍事和其他方面有重要的應(yīng)用．本文在半誠(chéng)實(shí)模型下給出了空間幾何中兩個(gè)高維向量差的范數(shù)協(xié)議,分析了協(xié)議的正確性、安全性和復(fù)雜性．然后在此協(xié)議的基礎(chǔ)上,給出了基于此協(xié)議的一個(gè)實(shí)際應(yīng)用，最終解決了保護(hù)私有信息的兩組數(shù)據(jù)對(duì)應(yīng)成比例問(wèn)題．

[1] Yao A C. Protocols for secure computations[C].Proceedings of 23rd IEEE Symposium on Foundations of Computer Science,1982:160-164.

[2] Du W L, Atallah M J. Privacy-preserving cooperative scientific computations[C].Proceedings of 14th IEEE Computer Security Foundations Workshop Lecture,2001: 273-282.

[3] Agrawal R, Srikant R. Privacy-preserving data mining[C].Proceedings of ACM International Conference on Management of Data and Symposium on Principles of Database Systems,2000:439-450.

[4] 楊高明,楊靜,張健沛. 聚類的(A,k)-匿名數(shù)據(jù)發(fā)布[J].電子學(xué)報(bào),2011,39(8):1941-1946.

[5] Atallah M J, Du W. Secure multi-party computational geometry[M]. Algorithms and Data Structures：Springer Berlin Heidelberg,2001:165-179.

[6] LI S D, Du Y Q. Secure two-party computational geometry[J].Journal of Computer Science and Technology,2005,20(2):258-263.

[7] Du W L, Atallah M J. Secure multi-party computation problems and their applications: A review and open problems[C].Proceedings of New Security Paradigms Workshop, 2001：11-20.

[8] Li S D,Wu C Y, Wang D S, et al. Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences, 2014(282): 401-413.

[9] 荊巍巍. 安全多方計(jì)算中若干基礎(chǔ)協(xié)議及應(yīng)用的研究[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué),2008.

[10] 羅永龍,黃劉生,荊巍巍,等. 空間幾何對(duì)象相對(duì)位置判定中的私有信息保護(hù)[J].計(jì)算機(jī)研究與發(fā)展,2006,43(3):410-416.

[11] 趙玉,仲紅,易磊. 安全判定兩組數(shù)據(jù)對(duì)應(yīng)成比例的新方法[J].微型機(jī)與應(yīng)用,2011,30(13):36-38.

[12] Goldreich O, Micali S, Wigderson A. How to play ANY mental game[C].Proceedings of the 19th Annual ACM Conference on Theory of Computing,1987: 218-229.

[13] Goldreich O. Foundations of cryptography: Basic applications[M].London: Cambridge University Press,2004:599-729.

[14] Rivest R L, Adleman L, Dertouzos M L. On data banks and privacy homomorphisms[J].Foundations of secure computation,1978,4(11):168-180.

[責(zé)任編輯：李春紅]

Privacy-Preserving Computation of the Norm of High-Dimensional Vector Difference and Its Applications

XU Xin-li

(Faculty of Mathematics and Physics, Huaiyin Institute of Technology, Huaian Jiangsu 223003, China)

Secure multi-party computation of the geometric problems is significant to privacy-preserving location estimation,data query, etc.But most of the existing literature of geometric problems have focused on plane geometry,while few have addressed spatial geometry.In this paper, we first compute securely the norm of high-dimensional vector difference using secure two-party permutation protocol,and further prove the security of this scheme with simulation paradigm. Then based on this scheme,we design two applications: one is privacy-preserving computation of the area of parallelogram in spacial geometry(protocol 2).The scheme adopts secure two-party permutation protocol, which avoids high-order modular exponentiation in other known schemes. It makes our scheme efficient.Our scheme is suitable for any high-dimensional vector except three-dimensional one, which makes it more universal than others. And the other is privacy-preserving judgment of whether two sets of data is proportional to the corresponding (protocol 3).In protocol 3, we change the problem of data proportional to the corresponding into the problem of composing triangle skillfully,which avoids repeatedly using the basic protocol,solves the problem of two sets of data proportional correspondly directly and raises the efficiency.

secure multiparty computation; high-dimensional vector; data proportional correspondly protocol

2016-06-11

徐新麗(1965-),女,江蘇淮安人,講師,主要從事應(yīng)用數(shù)學(xué)、數(shù)學(xué)課程論與教學(xué)論研究. E-mail: xuxl1965@163.com

TP309

A

1671-6876(2016)04-0295-05