夏　勇， 張明武， 沈　華， 陳泌文

(湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院， 湖北 武漢 430068)

?

一種移動終端隱私保護(hù)的信息匹配方案

夏勇， 張明武， 沈華， 陳泌文

(湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院， 湖北 武漢 430068)

[摘要]移動終端用戶在交友通訊過程中可能泄露用戶雙方的隱私信息，給用戶帶來安全隱患。針對該問題，提出一種移動終端隱私保護(hù)的信息匹配方案：首先利用安全兩方計(jì)算對用戶雙方進(jìn)行預(yù)處理，以達(dá)到物理位置匹配的目的；然后利用各種算術(shù)變換進(jìn)行用戶興趣愛好的匹配；最后利用權(quán)重公式計(jì)算用戶雙方信息的匹配度。通過對方案的正確性、安全性等進(jìn)行分析，顯示本方案可有效地保護(hù)用戶隱私。

[關(guān)鍵詞]隱私保護(hù)； 安全兩方計(jì)算； 正確性； 安全性； 私隱性

近年來安全多方計(jì)算(Secure muti-party Computation,SMC)問題成為密碼學(xué)界的研究熱點(diǎn)，SMC最早在文獻(xiàn)[1]中提出，隨后文獻(xiàn)[2]作了進(jìn)一步的研究。各種問題以及相應(yīng)的解決方案有：關(guān)于隱私信息相似度評估[4]，矩陣相等和特征值[5]，字符串匹配[6]，兩圓距離計(jì)算[7]，兩平行直線間距[8]，線與橢圓相交判定[9]，信息泄露比較[10]，點(diǎn)線關(guān)系判定[11]，信息的叉積協(xié)議[12]等。

針對目前移動終端交友容易帶來安全隱患這一問題，提出一種移動終端隱私保護(hù)的信息匹配方案。方案利用兩方安全計(jì)算用戶之間的距離，通過保密的比較來判斷所要交友的用戶是否在搜尋范圍內(nèi)，實(shí)現(xiàn)物理位置的匹配；利用哈希函數(shù) 、隨機(jī)置換及模指數(shù)運(yùn)算來進(jìn)行兩用戶的興趣愛好信息的交互，實(shí)現(xiàn)興趣愛好的匹配；利用權(quán)重公式來計(jì)算用戶信息的匹配度。這樣不僅保護(hù)了用戶的隱私信息不被泄露，而且還為用戶交友提供了真實(shí)可靠的參考數(shù)據(jù)，在現(xiàn)實(shí)環(huán)境下有很高的實(shí)用性和可靠性。

1預(yù)備知識

1.1半誠實(shí)模型

所謂的半誠實(shí)參與者會嚴(yán)格執(zhí)行協(xié)議的操作步驟，不會中途退出或惡意輸入虛假的數(shù)據(jù)，但是它可能保留所有的中間數(shù)據(jù)，試圖推導(dǎo)其他參與者的私有輸入信息。

1.2保密點(diǎn)積協(xié)議

假設(shè)有兩個參與者Alice和Bob，它們各自擁有秘密輸入向量X={x1,…,xn}和Y=(y1,…,yn)，它們進(jìn)行協(xié)作計(jì)算并在協(xié)議結(jié)束后Alice得到值wA=xi·yi+rB(rB是Bob選取的一個隨機(jī)值)。同時要保證Alice不能從wA中得到有關(guān)rB的值，也不能從已知的信息中推出任何有關(guān)yi的信息；同理Bob不能得到wA的值，也不能推出有關(guān)的xi的信息。

1.3安全兩實(shí)數(shù)和的平方協(xié)議

協(xié)議描述Alice擁有實(shí)數(shù)a，Bob擁有實(shí)數(shù)b，Alice和Bob希望保密計(jì)算(a+b)2。計(jì)算結(jié)束后，Alice得到k1，Bob得到k2，滿足k1+k2=(a+b)2。

步驟1Alice計(jì)算a2，Bob計(jì)算b2；

步驟2Alice和Bob利用安全兩方保密點(diǎn)積協(xié)議計(jì)算a·b：Alice得到K1，Bob得到K2，滿足K1+K2=a·b；

步驟3Alice計(jì)算k1=a2+2K1，Bob計(jì)算k1=a2+2K1；

步驟4k1和k2兩數(shù)相加得：k1+k2=a2+2K1+b2+2K2=(a+b)2。

1.4兩個實(shí)數(shù)大小的保密比較協(xié)議

協(xié)議描述Alice擁有實(shí)數(shù)c，Bob擁有實(shí)數(shù)d,他們保密比較c,d的大小。利用可交換加密方案E來實(shí)現(xiàn)保密比較，假設(shè)Alice的密鑰為KA，Bob的密鑰為KB。

輸入： 實(shí)數(shù)c,d

步驟1Alice加密c得EKA(c)，Bob加密d得EKB(d)；

步驟2Alice將EKA(c)發(fā)送給Bob，Bob將EKB(d)發(fā)送給Alice；

步驟3Alice計(jì)算EKA(EKB(d))，Bob計(jì)算EKB(EKA(c))；

步驟4Alice和Bob交換數(shù)據(jù)，如果EKA(EKB(d))≤EKB(EKA(c))，那么c≥d；否則c

2隱私保護(hù)信息匹配方案

方案描述 假設(shè)Alice和Bob是兩個移動終端用戶，方案如下描述：Alice擁有三維坐標(biāo)保密點(diǎn)P1(x1,y1,z1)及興趣愛好集合A={a1,…,am}，Bob擁有三維坐標(biāo)保密點(diǎn)P2(x2,y2,z2)及興趣愛好集合B={b1,…,bn}，Alice在自身隱私信息不被泄露的條件下尋找有共同興趣愛好的朋友Bob，并且返回信息匹配度的值(圖1)。

圖 1　方案示意圖

輸入Alice輸入三維坐標(biāo)保密點(diǎn)P1(x1,y1,z1)，Bob輸入三維坐標(biāo)保密點(diǎn)P2(x2,y2,z2)，進(jìn)行物理位置匹配，匹配成功后，Alice再輸入興趣愛好集合A={a1,…,am}，Bob再輸入興趣愛好集合B={b1,…,bn}。

輸出兩用戶信息匹配度的值。

圖 2　方案流程附圖

本方案的執(zhí)行過程由四個模塊構(gòu)成(圖2)，依次為：1)預(yù)處理模塊 ；2)物理位置匹配模塊；3)興趣愛好匹配模塊；4)信息匹配度計(jì)算模塊。

2.1預(yù)處理模塊

Alice和Bob希望在不泄露自己保密點(diǎn)信息的情況下，計(jì)算出兩用戶之間的距離

步驟1.1Alice和Bob利用安全兩數(shù)x1、-x2和的平方協(xié)議，保密計(jì)算(x1+(-x2))2；計(jì)算完成后，Alice得到d1A，Bob得到d1B，滿足d1A+d1B=(x1+(-x2))2；

步驟1.2Alice和Bob利用安全兩數(shù)y1、-y2和的平方協(xié)議，保密計(jì)算(y1+(-y2))2；計(jì)算完成后，Alice得到d2A，Bob得到d2B，滿足d2A+d2B=(y1+(-y2))2；

步驟1.3Alice和Bob利用安全兩數(shù)z1、-z2和的平方協(xié)議，保密計(jì)算(z1+(-z2))2；計(jì)算完成后，Alice得到d3A，Bob得到d3B，滿足d3A+d3B=(z1+(-z2))2；

步驟1.4Alice計(jì)算d1=d1A+d2A+d3A，Bob計(jì)算d2=d1B+d2B+d3B，此時d1+d2=(x1-x2)2+(y1-y2)2+(z1-z2)2， 可知兩點(diǎn)距離為：

步驟1.5系統(tǒng)將兩用戶間的距離dreal發(fā)送給Bob。

2.2物理位置匹配模塊

Alice和Bob在不泄露距離信息的情況下，達(dá)到兩用戶物理位置匹配的目的。

假設(shè)Alice所能搜尋的最遠(yuǎn)距離為dmax，它的密鑰為KA，Bob的密鑰為KB，只要Alice想交友的距離dselect在(0,dmax]范圍內(nèi)都可以實(shí)現(xiàn)物理位置的匹配。

步驟2.1Alice隨機(jī)選取所要搜尋的距離dselect(dselect∈(0,dmax])；

步驟2.2Alice加密dselect得EKA(dselcet)，Bob加密dreal得EKA(dreal)；

步驟2.3Alice將EKA(dselect)發(fā)送給Bob，Bob將EKB(dreal)發(fā)送給Alice；

步驟2.4Alice計(jì)算EKA(EKB(dreal))，Bob計(jì)算EKB(EKA(dselect))；

步驟2.5Alice和Bob交換各自數(shù)據(jù)，如果EKA(EKB(dreal))≤EKB(EKA(dselect))，那么Bob在Alice的距離范圍內(nèi)，則物理位置匹配成功，否則匹配失敗。

只有物理位置匹配成功才執(zhí)行以下的興趣愛好匹配模塊，如果匹配失敗的話則提前結(jié)束整個方案。

2.3興趣愛好匹配模塊

在不泄露各自興趣愛好的情況下，得到兩用戶之間興趣愛好匹配的個數(shù)。

第一輪運(yùn)算：

步驟3.1Alice將集合A={a1,…,am}中的每個元素依次代入哈希函數(shù)H1(·)，記為hai=H1(ai),(1≤i≤m)，得到集合A1：

A1={ha1,…,ham}=

步驟3.2Alice選取隨機(jī)數(shù)r1,?(r1∈Zq)，對集合A1中的每個元素做如下運(yùn)算：

Alice將集合A2發(fā)送給用戶Bob；

第二輪運(yùn)算：

得到集合A3：

步驟3.4Bob將集合A3中的每個元素代入隨機(jī)置換函數(shù)∏1(·)，得到集合A4：

步驟3.5Bob將集合B={b1,…,bn}中的每個元素代入隨機(jī)置換函數(shù)∏2(·)，記為ξj=∏2(bj)，(1≤j≤n,j,n,均為正整數(shù))，得到集合B1：

B1={ξ1,…,ξn}=∏2{b1,…,bn}=

Bob將集合A4和集合B4發(fā)送給Alice；

第三輪運(yùn)算：

2.4信息匹配度計(jì)算模塊

進(jìn)行信息匹配計(jì)算，得到信息匹配度。

步驟4.1Alice計(jì)算自身所想搜尋的距離與兩用戶之間的實(shí)際距離的差，記為

△d=dselcet-dreal=

步驟4.2Alice計(jì)算△d占dselect的比例，記為

步驟4.4Alice計(jì)算兩用戶興趣愛好交集的個數(shù)占兩用戶興趣愛好集合的最大個數(shù)的比例，記為

步驟4.5由上述已知的條件，可以利用權(quán)重公式計(jì)算信息匹配度：

F(ρ)=η×ρ%+μ×(1-ρ%)，

即

求出的F(ρ)即為兩用戶的信息匹配度；

3方案的性能分析

3.1正確性

方案中Alice和Bob通過安全兩方計(jì)算得到兩用戶的實(shí)際距離為dreal，如果該距離小于或者等于dselect，則兩用戶的物理位置匹配成功；兩用戶再利用哈希函數(shù)，隨機(jī)置換函數(shù)，模指數(shù)運(yùn)算等一系列的變換來實(shí)現(xiàn)興趣愛好的信息匹配；最后通過權(quán)重公式計(jì)算出相關(guān)信息的匹配度。因此，用戶Alice一定可以得到關(guān)于Bob的物理位置和興趣愛好匹配的百分比值，信息的匹配度也給Alice交友提供了可供參考的數(shù)據(jù)。

3.2安全性用戶的隱私信息沒有泄露。

1)預(yù)處理的安全性

預(yù)處理主要是兩空間三維坐標(biāo)的點(diǎn)安全計(jì)算距離dreal，它依賴的是安全兩實(shí)數(shù)和的平方協(xié)議的正確性和安全性。該協(xié)議只需使用3 次安全兩數(shù)和平方計(jì)算協(xié)議, 即3次一維安全兩方點(diǎn)積協(xié)議, 其計(jì)算復(fù)雜性和通信復(fù)雜性都依賴使用的一維安全兩方點(diǎn)積協(xié)議的計(jì)算復(fù)雜性和通信復(fù)雜性，在距離dreal計(jì)算完成后，用戶雙方并不知道對方的三維坐標(biāo)點(diǎn)。因此，預(yù)處理的整個過程沒有泄露任何有關(guān)用戶的坐標(biāo)信息。

2)物理位置匹配的安全性

物理位置匹配主要利用的是可交換加密方案E來實(shí)現(xiàn)兩距離dselect和dreal的保密比較，在比較的過程中，Alice和Bob只是在各自密鑰加密的情況下，進(jìn)行了數(shù)據(jù)交換，因此，用戶雙方在不知道對方密鑰的條件下，是無法知道對方距離信息的?？山粨Q加密方案 執(zhí)行完成之后，只是得到了兩距離的大小關(guān)系，并沒有泄露相關(guān)的距離信息。

3)興趣愛好匹配的安全性

4)信息匹配度的安全

信息匹配度主要是利用權(quán)重公式

(0<ρ<100)

3.3復(fù)雜性

計(jì)算的復(fù)雜性：Alice和Bob在通信過程中用到了點(diǎn)積協(xié)議和可交換加密方案E，其他都是一系列算術(shù)變換，因此計(jì)算的復(fù)雜性為O(nlnn)。

通信的復(fù)雜性：預(yù)處理模塊中，Alice和Bob需要相互通信1次；物理位置匹配模塊中，Alice和Bob需要相互通信1次；興趣愛好匹配模塊中，Alice和Bob需要相互通信2次；信息匹配模塊中，Alice和Bob需要相互通信1次，因此該方案中，兩用戶總共通信了5次。

4結(jié)束語

本文利用兩方安全計(jì)算和哈希函數(shù)等設(shè)計(jì)了一種移動終端隱私保護(hù)的信息匹配方案。該方案有效的解決了現(xiàn)有的移動終端交友過程中隱私信息容易泄露的問題，不需要不可信第三方的參與，只需要參與計(jì)算的雙方就可以實(shí)現(xiàn)用戶信息的匹配度計(jì)算，且保護(hù)了雙方的隱私信息。本方案是在半誠實(shí)的模型下進(jìn)行的，如何在惡意的模型下實(shí)現(xiàn)同樣的效果有待進(jìn)一步的研究與探索。

[參考文獻(xiàn)]

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

[2]Goldreich O, Micali S, Wigderson A. How to play any mental game[C] // Proceedings of the19th Annual ACM Conference on Theory of Computing[A]. New York: ACM Press, 1987:218-229.

[3]DU Wen-liang，ATALLAH M J． Secure multi-party computation problems and their applications: a review and open problems[C]// Proc of Workshop on New Security Paradigms[A]．New York: ACM Press，2001:11-20.

[4]Carlo Blundo，Emiliano De Cristofaro, Paolo Gasti. Efficient Privacy-Preserving Evaluation of Sample Set Similarity，DPM 2012.

[5]劉新，李順東，陳振華，等. 矩陣相等和矩陣特征值的概率多方保密計(jì)算協(xié)議[J].計(jì)算機(jī)應(yīng)用研究，2015,32(02)：524-527.

[6]袁先平，仲紅，黃宏升，等. 一種字符串近似匹配的安全查詢協(xié)議[J]. 計(jì)算機(jī)工程 ，2011，37(20)：142-144.

[7]劉文，羅守山，楊義先，等. 安全兩方圓計(jì)算協(xié)議[J]. 北京郵電大學(xué)學(xué)報，2009,32(03)：32-35.

[8]辛欣，郝林，湯瑜. 空間兩平行直線間距離的保密計(jì)算協(xié)議[J]. 計(jì)算機(jī)應(yīng)用研究，2013,30(05)：1530-1535.

[9]符祖峰，羅文俊，童玲. 一個保護(hù)私有信息的線段與橢圓相交判定協(xié)議[J]. 計(jì)算機(jī)工程與應(yīng)用，2010,46(17)：77-80.

[10] 秦靜，張振峰，馮登國等. 無信息泄露的比較協(xié)議[J]. 軟件學(xué)報，2004,15(3)：421-427.

[11] 劉文，羅守山，陳萍. 保護(hù)私有信息的點(diǎn)線關(guān)系判定協(xié)議及其應(yīng)用[J]. 北京郵電大學(xué)學(xué)報，2008,31(2)：72-75.

[12] 羅永龍，黃劉生，荊巍巍,等. 保護(hù)私有信息的叉積協(xié)議及其應(yīng)用[J]. 計(jì)算機(jī)學(xué)報，2007,30(2)：248-254.

[責(zé)任編校： 張巖芳]

Information Matching Scheme Protecting Mobile Terminal Privacy

XIAYong，ZhangMingwu，SHENHua，CHENMiwen

(SchoolofComputerScience，HubeiUniv.ofTech.，Wuhan430068，China)

Abstract：Mobile terminals may disclose the privacy information when users are communicating with others, which will bring security risks to users. To solve this problem, this paper presents an information matching scheme protecting mobile terminal privacy. First, it used two party security computations to pretreat users, in order to achieve the physical location of matching purposes; then used various arithmetic transforming to match the user's interests; Finally, used weight formula to calculate the information matching degree. Through analysing the correctness and security of the scheme, it shows that this scheme can improve the users’privacy effectively.

Keywords：privacy-preserving; secure two-party computation; correctness; security; privacy

[中圖分類號]TP393.08

[文獻(xiàn)標(biāo)識碼]：A

[文章編號]1003-4684(2016)01-0076-05

[作者簡介]夏勇(1987-)， 男， 湖北鐘祥人，湖北工業(yè)大學(xué)碩士研究生，研究方向?yàn)榘踩喾接?jì)算[通訊作者] 張明武(1970—)，男，湖北仙桃人，湖北工業(yè)大學(xué)教授，研究方向?yàn)樾畔⒕W(wǎng)絡(luò)安全

[收稿日期]2015-03-20