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

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

(湖北工業大學計算機學院， 湖北 武漢 430068)

?

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

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

(湖北工業大學計算機學院， 湖北 武漢 430068)

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

[關鍵詞]隱私保護； 安全兩方計算； 正確性； 安全性； 私隱性

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

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

1預備知識

1.1半誠實模型

所謂的半誠實參與者會嚴格執行協議的操作步驟，不會中途退出或惡意輸入虛假的數據，但是它可能保留所有的中間數據，試圖推導其他參與者的私有輸入信息。

1.2保密點積協議

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

1.3安全兩實數和的平方協議

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

步驟1Alice計算a2，Bob計算b2；

步驟2Alice和Bob利用安全兩方保密點積協議計算a·b：Alice得到K1，Bob得到K2，滿足K1+K2=a·b；

步驟3Alice計算k1=a2+2K1，Bob計算k1=a2+2K1；

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

1.4兩個實數大小的保密比較協議

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

輸入： 實數c,d

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

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

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

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

2隱私保護信息匹配方案

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

圖 1　方案示意圖

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

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

圖 2　方案流程附圖

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

2.1預處理模塊

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

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

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

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

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

步驟1.5系統將兩用戶間的距離dreal發送給Bob。

2.2物理位置匹配模塊

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

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

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

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

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

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

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

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

2.3興趣愛好匹配模塊

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

第一輪運算：

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

A1={ha1,…,ham}=

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

Alice將集合A2發送給用戶Bob；

第二輪運算：

得到集合A3：

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

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

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

Bob將集合A4和集合B4發送給Alice；

第三輪運算：

2.4信息匹配度計算模塊

進行信息匹配計算，得到信息匹配度。

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

△d=dselcet-dreal=

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

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

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

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

即

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

3方案的性能分析

3.1正確性

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

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

1)預處理的安全性

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

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

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

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

4)信息匹配度的安全

信息匹配度主要是利用權重公式

(0<ρ<100)

3.3復雜性

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

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

4結束語

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

[參考文獻]

[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].計算機應用研究，2015,32(02)：524-527.

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

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

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

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

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

[11] 劉文，羅守山，陳萍. 保護私有信息的點線關系判定協議及其應用[J]. 北京郵電大學學報，2008,31(2)：72-75.

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

[責任編校： 張巖芳]

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

[文獻標識碼]：A

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

[作者簡介]夏勇(1987-)， 男， 湖北鐘祥人，湖北工業大學碩士研究生，研究方向為安全多方計算[通訊作者] 張明武(1970—)，男，湖北仙桃人，湖北工業大學教授，研究方向為信息網絡安全

[收稿日期]2015-03-20