基于偽隨機置換的朋友發現系統

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

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

關鍵詞：移動社交；偽隨機置換；隱私保護；朋友發現

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

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

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

1 預備知識

2 基于偽隨機置換朋友發現系統模型的建立

2.1 模型介紹

假設Alice和Bob是兩個移動終端用戶，簡單方案如下描述：他們想在自身隱私不被泄露的條件下尋找手機通訊錄里的共同好友，并且返回共同的手機聯系人。基于偽隨機置換朋友發現系統模型如圖1所示。

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

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

2.2 模型分析

2.2.1 惡意服務器模型

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

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

（1）P1選擇集，這樣，并把P2發送他們；（2）P1檢查，構造正確，否，中止；（3）P1和P2使用FCT同意一個隨機位鍵K；（4）對于每一方，發送集合Ti=πi（FK（Siλ+Δi）） 到服務器，πi是一個隨機排列?i=D0+Di；（5）服務器返回交集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 洗牌算法

洗牌算法是對一組起始數列中的各個元素的位置進行重新調整，以此得到新的數列。結合本文背景，應用的洗牌算法如下：

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

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

3 結語

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

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

[參考文獻]

[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]蔡麗華.淺談如何正確處理群眾文化兩個效益的關系[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.計算機數據保護—序列密碼的分析與設計[M].呂佩爾，譯.北京：人民郵電出版社，1988.

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

[10]DAVID S.數據保密與安全[M].蔡建，梁志敏，譯.北京：清華大學出版社，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