基于偽隨機置換的朋友發(fā)現(xiàn)系統(tǒng)

王凱月+張政寧+杜阿美+崔含笑+胡錦廣

摘 要：近年來，隨著移動社交軟件的迅速發(fā)展，便攜式移動終端已經(jīng)滲透到人們生活的方方面面。在這些軟件中，人們經(jīng)常用到其中的一項功能—朋友發(fā)現(xiàn)，但是目前這個功能對于用戶并不安全，大量隱私信息被云服務(wù)商所獲取。針對此現(xiàn)象，文章基于目前隱私集合比較的現(xiàn)狀，運用偽隨機置換和安全多方計算協(xié)議并加以改進，設(shè)計出基于偽隨機置換的朋友發(fā)現(xiàn)系統(tǒng)，本系統(tǒng)使用戶找到他們集合的交集而且不泄露除交集以外的信息，具有一定推廣價值。

關(guān)鍵詞：移動社交；偽隨機置換；隱私保護；朋友發(fā)現(xiàn)

在信息技術(shù)和互聯(lián)網(wǎng)技術(shù)日新月異的今天，社交網(wǎng)絡(luò)服務(wù)越來越多地被人們使用，如微信和MSN等，每個人的朋友圈也在日益擴大。朋友的朋友在社會中也發(fā)揮著重要作用，不僅體現(xiàn)在就業(yè)市場上，還有其他業(yè)務(wù)，如房地產(chǎn)市場或產(chǎn)品推薦。社交網(wǎng)絡(luò)的高聚類系數(shù)[1]進一步表明，朋友的朋友是我們社會和情感環(huán)境的重要組成部分，并且可能成為我們直接的朋友。本文認為，一個共同的朋友至少表明兩個人之間存在潛在的“匹配”關(guān)系。

假如兩個陌生人在街上相遇時，他們想要確定是否有共同的朋友，因此需要比較他們手機的聯(lián)系人，我們針對此問題進行研究。與此同時，隱私保護受到大家越來越多的關(guān)注。如今，市場上開發(fā)的移動社交軟件都或多或少地存在隱私泄露的問題。據(jù)DCCI互聯(lián)網(wǎng)數(shù)據(jù)中心和360互聯(lián)網(wǎng)安全中心聯(lián)合發(fā)布的《2014年下半年Android手機隱私安全報告》數(shù)據(jù)顯示[2]，軟件泄漏、系統(tǒng)漏洞泄漏、云端網(wǎng)絡(luò)泄漏等都是Android手機用戶隱私泄露的幾大問題。如何在開放的網(wǎng)絡(luò)環(huán)境下保障移動社交軟件用戶的數(shù)據(jù)安全存儲和計算，成為非常緊迫和嚴峻的問題。

本文針對移動社交軟件在生活中出現(xiàn)的隱私安全問題，設(shè)計出了基于安全多方計算（Secure Multi-Party Computation，SMC）和偽隨機置換（Pseudo Random Permutation，PRP）的朋友發(fā)現(xiàn)系統(tǒng)。該系統(tǒng)在提高效率的基礎(chǔ)上，使用了惡意模型以保證用戶個人隱私的安全。

1 預(yù)備知識

2 基于偽隨機置換朋友發(fā)現(xiàn)系統(tǒng)模型的建立

2.1 模型介紹

假設(shè)Alice和Bob是兩個移動終端用戶，簡單方案如下描述：他們想在自身隱私不被泄露的條件下尋找手機通訊錄里的共同好友，并且返回共同的手機聯(lián)系人?；趥坞S機置換朋友發(fā)現(xiàn)系統(tǒng)模型如圖1所示。

本系統(tǒng)的具體模型如下：本系統(tǒng)由客戶端與服務(wù)端組成，用Android手機作為客戶端，電腦暫時作為一個服務(wù)端。在客戶端基于PRP和SMC使用惡意服務(wù)器模型，對數(shù)據(jù)進行加密處理，并通過socket通信將加密后的數(shù)據(jù)傳輸至服務(wù)器。服務(wù)器經(jīng)過密文對比后，返回相同的密文，然后在客戶端進行密文解密后，最終得到交集。本文使用手機聯(lián)系人作為集合，進行集合比較，得到相同的手機聯(lián)系人信息，實現(xiàn)了上述的模型和方法，保護了隱私信息。

整體系統(tǒng)由3個線程組成，服務(wù)端和客戶端相對應(yīng)：（1）服務(wù)端創(chuàng)建組播，發(fā)送服務(wù)端的IP，客戶端接收組播信息，得到服務(wù)端的IP地址；（2）服務(wù)端監(jiān)控端口號5020，等待客戶的密文信息，服務(wù)端不斷監(jiān)聽5020端口，得到兩組客戶端集合后，與客戶端建立端口號1994的TCP連接，返回交集數(shù)據(jù)，客戶端提取手機聯(lián)系人信息，進行加密處理；（3）服務(wù)端密文對比，返回客戶端結(jié)果，客戶端解密服務(wù)端返回信息并顯示。

2.2 模型分析

2.2.1 惡意服務(wù)器模型

以前的協(xié)議只能對半誠實的服務(wù)器保證安全，因為服務(wù)器可以返回任意結(jié)果作為交集，而客戶端并不知道這是否為真正的交集。為了克服這一點，本文作了如下改善：

設(shè)置和輸入：讓F：{0，1}k×U→{0，1}≥K為一個PRP和t，λ≥1.P1和P2分別將集合S1?U和S2?U作為輸入，而服務(wù)器沒有輸入。

（1）P1選擇集，這樣，并把P2發(fā)送他們；（2）P1檢查，構(gòu)造正確，否，中止；（3）P1和P2使用FCT同意一個隨機位鍵K；（4）對于每一方，發(fā)送集合Ti=πi（FK（Siλ+Δi）） 到服務(wù)器，πi是一個隨機排列?i=D0+Di；（5）服務(wù)器返回交集I=T1∩T2；（6）每一方Pi中止，如果：（a）D0 FK-1（I）或Di∩FK-1 （I）≠?；（b）存在x∈Si，x||α∈FK-1（I）和x||β?FK-1 （I）；（7）每一方計算和輸出（FK-1 （I）-D0 ）-λ。

2.2.2 洗牌算法

洗牌算法是對一組起始數(shù)列中的各個元素的位置進行重新調(diào)整，以此得到新的數(shù)列。結(jié)合本文背景，應(yīng)用的洗牌算法如下：

已知有N個聯(lián)系人，在洗牌前將聯(lián)系人信息放在數(shù)組array[N]中。令i=N；對隨機數(shù)發(fā)生器進行初始化，隨機取（1～i）之間的一個聯(lián)系人，與array[i]交換；i減1；如果i>1，則跳到步驟2；完成洗牌。

因為在該算法中，本文將余下的聯(lián)系人中的最后一張位置調(diào)整到剛抽掉的位置上，而不是將抽掉的聯(lián)系人后面部分全部前移，所以在時間以及空間復(fù)雜度上都有較好的表現(xiàn)。

3 結(jié)語

針對當(dāng)前朋友發(fā)現(xiàn)系統(tǒng)存在的隱私泄露問題，本文運用偽隨機函數(shù)、混淆填充、洗牌算法對數(shù)據(jù)進行處理，保證了用戶隱私數(shù)據(jù)的安全性，使其可以抵御社交網(wǎng)絡(luò)的各種攻擊，使用戶之間進行安全的信息匹配，達到了隱私保護的效果。在隱私保護越來越成為熱點的趨勢下，如何降低隱私保護方法的計算復(fù)雜度，提高服務(wù)質(zhì)量，都有待進一步研究。

作者簡介：王凱月（1995— ），女，河南新鄉(xiāng)，本科。

[參考文獻]

[1]LUCIANODA FC，OSVALDO N. OLIVEIRA JR，et al. Analyzing and modeling real-world phenomena with complex networks：a survey of applications[J].Advances in Physics，2011（3）：329-412.

[2]蔡麗華.淺談如何正確處理群眾文化兩個效益的關(guān)系[J].華章， 2011（1）：210-211.

[3]GOLDWASSER S. Multi party computations：past and present[C].Washington：Proceedings of the 16th annual ACM symposium on principles of distributed computing，1997：21-24.

[4]YAO AC. Protocols for secure computations[C].Washington：Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science，2008：160-164.

[5]EMILIANO D C，GENE T. Experimenting with fast private set intersection[J].Trust and Trustworthy Computing，2012（7）：55-73.

[6]GOLDREICH O， MICALI S， WIGDERSON A. A completeness theorem for protocols with honest majority[C].New York：Proceedings of the 19th Annual ACM Symposium on Theory of Computing，1987：218-229.

[7]GOLDREICH O. Secure multi-party computation [EB/OL].（1998-04-10）[2017-07-10].http：//www.wisdom.weizman.ac.il/oded/pp.html.

[8]RAINER A，RUEPPEL.計算機數(shù)據(jù)保護—序列密碼的分析與設(shè)計[M].呂佩爾，譯.北京：人民郵電出版社，1988.

[9]WADE T，LAWRENCE CW.密碼學(xué)概論[M].鄒紅霞，譯.北京：人民郵電出版社，2004.

[10]DAVID S.數(shù)據(jù)保密與安全[M].蔡建，梁志敏，譯.北京：清華大學(xué)出版社，2005.

[11]ROGAWAY P，BELLARE M，BLACK J，et al. OCB：a block-cipher mode of operation for efficient authenticated encryption[J].Acm Transactions on Information & System Security，2001（3）：196-205.

Abstract： In recent years， with the rapid development of mobile social software， portable mobile terminals have penetrated into all aspect of peoples lives. In these software， people often use one of these functions——friend find. But this function is insecure for subscribers currently， vast quantities of privacy information is obtained by cloud service providers. Aiming at this phenomenon， the paper based on the current situation of comparison of privacy collections， friend find system based on pseudo random permutation is designed by using pseudo random permutation and secure multi-party computation protocol to improve. The system allows users to find the intersection of their collection and do not disclose information other than the intersection， with a certain value to promote.

Key words： mobile social； pseudo random permutation； privacy protection； friend find