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

徐新麗

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

?

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

徐新麗

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

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

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

0 引言

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

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

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

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

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

1 預(yù)備知識

1.1 安全多方計算的安全性定義

1) 半誠實參與者

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

2) 半誠實模型下的安全性定義

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

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

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

(1)

(2)

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

1.2 同態(tài)加密

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

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

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

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

輸入： Alice有一個秘密向量X;Bob有一個置換函數(shù)π和一個秘密向量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ì)計算E(X+Y)=E(X)+E(Y),然后用置換函數(shù)π對E(X+Y)進(jìn)行置換得π(E(X+Y))．并將結(jié)果發(fā)送給Alice．

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

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

1) 問題的描述

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

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

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

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

由于

因此

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

3) 具體協(xié)議

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

協(xié)議1 保密計算高維空間向量差的范數(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將計算的結(jié)果發(fā)送給Alice,Alice將會計算出‖A-B‖2,從而得到‖A-B‖．

3 應(yīng)用

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

1) 問題的描述

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

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

3) 具體協(xié)議

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

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

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

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

2) Alice和Bob共同調(diào)用協(xié)議1,Alice得到了b=‖B‖和兩個向量差的范數(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ù)據(jù)不對應(yīng)成比例;反之,對應(yīng)成比例．

4 安全性分析

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

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

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

1) 給定輸入(A,‖A-B‖),S1隨機(jī)選取一個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′‖},

因為‖A-B′‖=‖A-B‖,所以

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

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

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

5 效率分析與比較

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

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

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

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

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

6 總結(jié)

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

[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é)報,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] 荊巍巍. 安全多方計算中若干基礎(chǔ)協(xié)議及應(yīng)用的研究[D].合肥：中國科學(xué)技術(shù)大學(xué),2008.

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

[11] 趙玉,仲紅,易磊. 安全判定兩組數(shù)據(jù)對應(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