基于隱私匹配的服務代理發現方法

耿魁，萬盛，李鳳華,，何媛媛，王瀚儀

(1. 西安電子科技大學綜合業務網理論與關鍵技術國家重點實驗室，陜西 西安 710071；2. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093)

基于隱私匹配的服務代理發現方法

耿魁1，萬盛1，李鳳華1,2，何媛媛2，王瀚儀2

(1. 西安電子科技大學綜合業務網理論與關鍵技術國家重點實驗室，陜西 西安 710071；2. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093)

針對代理發現中用戶對代理的性能、成本和安全性等方面的需求，以及需求匹配過程中的隱私保護問題，基于 Paillier同態加密算法，提出一種新的綜合考慮代理和用戶屬性及其偏好的私有數據信息匹配算法，包括建立基于歐氏距離的相似度函數、利用加密算法進行匹配、計算相似度和確定匹配的代理鏈4個步驟。該算法引入半可信主代理從全局層面管理所有子代理的業務類型和連接狀況，并承擔主要的計算開銷，同時將歐氏距離與Paillier同態加密算法有機結合，支持具有偏好信息的多元屬性數據匹配，能夠有效保障用戶和子代理的安全性。最終，通過安全性分析與性能仿真，證明所提出方案的安全性和有效性。

代理；服務代理發現；隱私匹配；同態加密

1 引言

隨著網絡技術的快速發展和信息共享系統的大量應用，泛在網絡中局域網、互聯網、物聯網和移動網等多種網絡廣泛互連互通，信息呈爆炸式增長，出現了過載現象，服務數量的大規模性、服務描述的異構性以及設備服務的資源高度受限性和移動性等特征日益凸顯，為了向用戶準確地提供所需的信息和服務，朋友發現、代理發現和服務發現等基于匹配的應用應運而生，成為泛在網絡的重要應用，已受到了學術界和工業界的廣泛關注。用戶與活躍在鄰近區域的代理及時通信，找到在性能、成本和安全性等方面最優的路徑，更快速、更準確地獲取信息和服務。然而，用戶和代理通過交換服務屬性集合優化訪問路徑的同時，用戶和代理的處理能力、時延、能耗、服務費用和抗攻擊能力等敏感信息將暴露給對方，從而為雙方的數據安全和隱私信息帶來潛在威脅。因此，對用戶個人隱私和代理敏感數據的保護刻不容緩。

針對私有數據匹配問題，近年來大量文獻提出了解決方法。大多數方法假設每個匹配參與方擁有一個屬性集合，采用匹配參與雙方共同屬性的個數為相似度，共同屬性越多，用戶越匹配，整個匹配過程不泄露雙方個人敏感信息，但是，這些方案存在一定的局限性。匹配函數只考慮了共同屬性的個數，忽視了每個用戶對各個屬性偏好程度的差異；基于交換加密、同態加密等加密方法的隱私信息匹配方案安全性較高，但是，計算開銷較大，難以在移動終端上運行；基于布隆過濾器、混淆等非加密方法的隱私信息匹配方案計算開銷較小，但是，大量隨機數導致通信量大幅增加，并且安全性較弱。因此，將復雜的計算工作交由第三方代理來完成是一種常見的解決思路。

為了解決上述問題，本文提出一種與屬性偏好相關的私有數據信息匹配算法，其主要貢獻如下。

1)將Paillier同態加密應用于代理發現算法的設計中，針對用戶的個性化服務請求提供最匹配的作業代理鏈。

2)引入主代理從全局層面管理所有子代理的業務類型和連接狀況，并在利用Paillier同態加密方法的語義安全性保證算法安全性的前提下，由主代理承擔主要的計算開銷，以緩解用戶終端的計算壓力。

3)支持具有偏好信息的多元屬性數據匹配，更細粒度地滿足用戶及代理在服務性能和隱私保護方面的需求。同時，執行加密運算前將屬性的偏好程度轉化為二元值，有助于降低計算開銷。

2 相關工作

本文涉及的代理發現這一概念，是建立在第三方不可信的基礎上進行的，因而本文方案的主要工作是在隱私保護的前提下實現代理發現。能夠保障信息不被泄露的算法有很多種，大體分為加密算法和非加密算法，本文采用的是同態加密算法中的Paillier算法，在方案中起到了隱私保護的關鍵作用。

有不少學者會通過非加密的算法實現隱私保護，以便減輕執行過程中的消耗。Zheng等[1]提出了一個基于位置隱私保護的握手協議，利用布隆過濾器進行一對多的匹配，構建時空位置標記，從無線電在設備的周圍環境中捕獲的信號（Wi-Fi等）來標記位置，以防止位置欺騙。Sun等[2]也根據布隆過濾器進行基于共同興趣愛好的朋友隱私匹配，雖然上述方案均未采用加密算法，使整體方案的消耗很小，但是卻有匹配精確度的偏差。Lu等[3]針對移動醫療急救場景提出SPOC協議，并在方案中引入隨機數，通過混淆來保證隱私安全，然而利用窮舉法，還是有信息被破解的可能。

出于對安全性的考慮，更多學者會利用加密算法來實現高強度的隱私保護。例如，Agrawal等[4]提出了基于交換加密的雙方秘密共享方案，Vaidya等[5]提出了 N方秘密共享方案，Niu等[6]提出P-match，利用交換加密進行基于鄰近的朋友發現，并考慮到用戶的興趣權重因素。而在各種加密方案中，同態加密方法更是不勝枚舉，Li等[7]利用同態加密和二維多項式，實現多方匹配的語義安全。Kerschbaum等[8]也利用同態加密，在雙方不泄露個人信息的前提下求出集合交集。Li等[9]基于鄰近的移動社交網絡，提出了分布式的保護隱私信息匹配方案FindU，建立3個不同的隱私級別，利用Shamir秘密共享方法結合同態加密，進行安全多方計算，實現多方匹配，可以抵抗多方同謀的情形。Zhang等[10]利用 Paillier同態加密方法，根據不同的隱私需求設計不同的方案，并考慮到了用戶對不同興趣的偏好程度，由此建立了基于鄰近的隱私信息匹配協議。Thapa等[11]針對在線社交網絡，利用Paillier加密算法設計了3個不同隱私級別的非對稱的基于鄰近的隱私信息匹配方案，其社交網絡中的用戶不僅通過朋友關系彼此相連，還按社會團體進行分類，并提出新的相似度函數。Chu等[12]提出了隱私保護的二部匹配框架，基于二部圖結構中的匈牙利方法和Paillier同態加密方法，來尋找最佳匹配，在保障用戶隱私的前提下，利用服務器的計算能力對多媒體進行分析研究。文獻[13]提出了一對一基于社交網絡隱私信息匹配的方案，運用 ElGamal和Paillier加密算法，使用戶雙方可以不同時在線進行匹配。Wang等[14]針對社交網絡中的群組隱私匹配，利用Paillier加密算法，選出與用戶的興趣集合最匹配的群組。Niu等[15]同樣基于Paillier算法，考慮到用戶屬性的權重來進行朋友發現。上述在不同場景下的文獻，均采用了Paillier加密算法，可見該算法的實用性與安全性。

3 隱私匹配機制

3.1 預備知識

本文采用同態加密算法——Paillier加密算法，來保護用戶和各個子代理的隱私信息，由于Paillier算法對數據加密后，具有同態性質，所以可直接通過對加密后的信息進行操作，而不需要已知明文，這樣保障了在交換信息過程中的安全性。下面介紹Paillier算法的具體操作。

1)密鑰生成。任意選取 2個大素數 p、q，使GCD(pq,(p?1)(q?1))=1。記選取隨機整數使其中則用戶U的公鑰為數對lt;N,g＞，私鑰為λ。

3.2 參數設置

用戶在請求服務時，請求信息交給第三方代理后（主代理），主代理將對服務請求信息進行分解，服務請求將被多個不同類型、不同級別的子代理進行處理，形成一個作業代理鏈。根據不同下級子代理的類型、級別、業務能力以及代理之間的連通性，實際上可選的下級子代理有多種方案，為完成用戶請求作業的下級代理所組成的作業代理鏈也存在多條。

在具體執行時，主代理可通過子代理之間的業務屬性連通性，發現多條可完成用戶服務請求的作業代理鏈。主代理需要根據用戶提出的服務要求（例如時延、費用、安全等級等），以及各個子代理的服務屬性值，找出一條最符合用戶需求的作業代理鏈。

對 任 意 x∈ [0,w ? 1],定 義 函 數 h( x)=其中，當時， xl=1；當時， xl=0。定義用戶U的服務屬性權重向量為每個子代理 Vi的服務屬性權重向量為由定義可知，對均為 0 或 1。

本文將用戶 U與子代理 Vi的服務屬性權重向量，在不泄露具體信息的情況下,借助主代理進行匹配，使用戶得到評價值 f( U,Vi)，算出用戶與整條作業代理鏈的整體評價值，并與其他作業代理鏈進行比較。評價值越小，表示該作業代理鏈與用戶的服務越接近。本文中選取作為衡量評價值的函數。

在本方案中，忽略通信信道的安全問題，著重考慮來自內部參與者的攻擊。假定內部參與信息交換傳輸的三方：用戶、主代理、多個子代理，是誠實但好奇（HBC,honest but curious)，即參與者能誠實的執行既定方案，不會對信息進行偽造，但卻會盡可能分析方案執行過程中所有獲得的信息，試圖獲取其他參與者的隱私信息。

基于上述攻擊模型，當本文方案執行結束，用戶、主代理、多個子代理，不能知道關于其他參與者服務屬性的任何信息。

3.3 系統架構

本文提出基于 Paillier同態加密算法的作業代理鏈發現方法，其系統架構如圖1所示。以用戶通過一個不完全可信的第三方代理來完成餐飲、醫療等服務，下面舉例對系統中相關背景進行介紹。

圖1 系統架構

2)主代理通過廣播方式，將其需要交通類和餐飲類的信息發送給其鄰近的子代理，各個子代理根據自身的業務類型和連通性，將確認信息反饋給主代理。

3)主代理根據接收的信息，綜合出可選的作業代理鏈，然后根據同態加密算法，對用戶和子代理的密文信息進行處理，并根據用戶最終反饋的結果選擇最合適的作業代理鏈來完成用戶的請求作業。

3.4 匹配算法

由于用戶與每個子代理的匹配過程都是相同的，所以為了簡便，下面以子代理Vi為例，來對匹配過程進行說明。設子代理Vi的整體服務屬性值為服務屬性權重向量為

顯然，

為保護用戶和各個子代理的隱私信息，本文通過同態加密，用戶使用自身的加密公鑰對服務要求進行加密，同時，各個作業代理鏈上的子代理也使用用戶的加密公鑰加密自身的服務屬性值。用戶U和子代理Vi分別已知和為了讓用戶知道只需要在保證隱私的前提下，讓用戶計算的數值即可，由此衍生出本文的具體方案，操作如下。

1)用戶U首先用Paillier加密算法給自己的服務屬性權重向量加密。U的服務屬性權重向量為由定義可知，對任意成立，而當時，

腦癱是小兒常見的神經系統疾病，是指患兒出生后1個月內因非進行性腦受損所致，臨床表現存在多樣性，現如今小兒腦癱發病率呈明顯上升趨勢，隨著醫學技術的不斷進步，其存活率已得到改善[8-9]。手術為癥狀嚴重者的主要治療手段，能夠有效改善患兒功能，多于全麻下進行，七氟醚為小兒麻醉的誘導藥物，其起效快速，對氣道刺激較小，能夠促進氣道平滑肌松弛，對肌松藥的強化作用明顯優于恩氟醚及異氟醚[10]。但存在惡心嘔吐、咽部不適等不足，加之手術疼痛能夠引起蘇醒期躁動，導致患兒煩躁不安。既往多予以氯胺酮或者阿片類藥物鎮痛以預防躁動，但其可能導致呼吸抑制，影響患兒清醒質量[11]。

2)在收到用戶的服務請求信息 ReqInfo=lt;ReqData,后，主代理根據請求信息ReqInfo以及各個子代理的業務屬性、連通性，采用廣播方式，獲取到多條作業代理鏈，對于每條代理鏈上的每個子代理 Vi，進行如下操作。

3)主代理將ReqInfo發送給Vi，Vi對自己的服務屬性權重向量進行處理。Vi的服務屬性權重向量為其中， v?i,s=1 對任意成立，而當時，

子代理利用服務請求信息ReqInfo，計算

子代理 Vi選取隨機數利用用戶公鑰lt;N,g＞對進行加密，得到子代理將的值發送給主代理。

在此之后，主代理將每條作業代理鏈上所有子代理的信息相乘，計算

并將結果發給用戶。

5)用戶使用自己的私鑰，解密

得到

4 安全性分析與性能仿真

4.1 安全性分析

在方案執行之后，用戶將會得知每條作業代理鏈的評價值，子代理和主代理不會得知相關的有效信息。

1)用戶U的安全性

2)子代理的安全性

在整個方案中，子代理 Vi將和透露給主代理，如上所述，主代理在不清楚私鑰的情況下不能得到子代理和主代理的服務屬性信息以及它們之間的共有信息。

根據上述分析，在主代理不一定可信的情況下，用戶和主代理得不到子代理的服務屬性值，除了用戶的加密公鑰信息，子代理和主代理也無法拿到用戶的服務屬性取值。

4.2 結果分析

假設在本文的方案中，通過主代理，從k個子代理中發現了h條服務鏈，并設用戶和子代理均有m個服務要求，每個要求的偏好取值區間為[0,w?1]。在整個方案中，根據 Paillier同態加密算法的特點，取模數N的長度為1 024 bit，則主要涉及到1 024-bit模乘、2 048-bit模乘、1 024-bit模冪和 2 048-bit模冪的運算，分別記為 mul1、mul2、exp1、exp2。考慮到主代理的運行配置遠優于用戶和子代理的時間，因此將主代理的上述運算記為 mul3、mul4、exp3、exp4，以示區別。本文選取了文獻[17]和文獻[18]的方案，從離線計算量、在線計算量、通信量和執行時間的角度與本方案來量化對比。由于文獻[17]與文獻[18]的方案均為兩方匹配，所以為使3個方案具有可比性，考慮在加入第三方的條件下使發起方與k個響應者進行匹配，3個方案理論上的計算開銷和通信量如表1所示。

本文的仿真運算將以便攜式計算機（處理器：Intel Core P8700，2.53 GHz；內存：4 GB RAM；操作系統：Ubuntu 14.04）作為用戶和子代理的運行配置，以服務器（處理器：Intel Xeon E5-2690，2.9 GHz；內存：32 GB RAM；操作系統：CentOS 6.3）作為主代理的運行配置。在便攜式計算機上執行mul1、mul2、exp1、exp2運算，以及在服務器上執行 mul3、mul4、exp3、exp4運算的最大時間、最小時間、平均時間、中位數以及標準差如表2和表3所示。

根據實際情況，取w=10。圖2(a)表示的是方案離線的計算量，根據理論值可以看出，離線計算量只與m有關，并且本文方案與文獻[18]方案計算量相同，略小于文獻[17]方案。由于在整個過程中，只有用戶進行了離線計算，所以該取值只與服務要求個數m有關，使m在20到100之間變化，從圖中可以看出，隨著 m值的增大，整個方案的計算量也在不斷增加，但是 3個方案的時間差別并不大，通過計算可以知道，當m=100時，離線計算時間低于5.2 s。

圖2(b)表示的是3種方案在線的計算量與子代理個數k的關系，本文使k值在1 000到6 000之間變動。顯然，k值增加，在線的計算時間也增長，盡管在線計算開銷很大，但是本文方案中主代理相應的承擔了絕大部分的計算，減輕了子代理和用戶的負擔，因此從圖中可以明顯的看出本文方案的計算量小于文獻[17,18]方案的計算開銷。當 k=6 000時,本方案在線計算時間約為2.3 s，文獻[17,18]方案在線時間分別約為3.1 s和3 s。

表1 計算開銷與通信量

表2 便攜式計算機運算執行時間

表3 服務器運算執行時間

圖2 不同參數取值下的不同方案間性能比較

圖2(c)表示的是3種方案的通信開銷與k的關系圖，k在1 000到6 000之間變動，隨著k的增加，傳輸消耗不斷增加，從圖中難以分辨3種方案的差別，利用理論數據計算，當k=6 000時，本方案、文獻[17]和文獻[18]的方案通信量分別為 2.219 3×109bit、2.224 5×109bit和2.231 6×109bit，顯然，本文方案的通信量小于其他兩者。

圖2(d)表示3種方案執行時間隨k的變化，圖像趨勢同樣為遞增，雖然對比方案與本文方案執行時間處于同一量級，但是具體數值還是有所差別，同樣通過理論數值計算，得到當k=6 000時，本文方案、文獻[17]和文獻[18]的方案的執行時間分別約為3.798 2 s、3.819 2 s和3.829 8 s。并且盡管基于大傳輸量的條件，總體的執行時間仍然在可控范圍內。

根據對理論值與圖像的分析，方案消耗與服務要求的個數和子代理的個數均為正相關。本文方案通過增加第三方主代理，轉移了用戶和子代理的消耗，可以使整體的消耗和執行時間均有所減少，并與其他方案比較，本文方案在在線計算量方面有較明顯的優越性。

5 結束語

本文針對代理發現中用戶對代理的性能、成本和安全性等方面的需求，以及需求匹配過程中的隱私保護問題，基于Paillier同態加密算法，提出一種新的綜合考慮代理和用戶屬性及其偏好的私有數據信息匹配算法，該算法引入半可信主代理，從全局層面管理所有子代理的業務類型和連接狀況，并承擔主要的計算開銷，同時將歐氏距離與 Paillier同態加密算法有機結合，支持具有偏好信息的多元屬性數據匹配，能夠有效保障用戶和子代理的安全性。通過安全性分析，表明了方案的正確性和安全性，并通過性能仿真進一步驗證方案的有效性和高效性。

[1]ZHENG Y,LI M,LOU W,et al. Location based handshake and private proximity test with location tags[J]. IEEE Transactions on Dependable and Secure Computing,2015:1.

[2]SUN J,ZHANG R,ZHANG Y. Privacy-preserving spatiotemporal matching[C]//32th IEEE International Conference on Computer Communications. c2013: 800-808.

[3]LU R,LIN X,SHEN X. SPOC: a secure and privacy-preserving opportunistic computing framework for mobile-healthcare emergency[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(3):614-623.

[4]AGRAWAL R,EVFIMIEVSKI A,SRIKANT R. Information sharing across private databases[C]//30th ACM SIGMOD International Conference on Management of Data. c2003: 86-97.

[5]VAIDYA J,CLIFTON C. Secure set intersection cardinality with application to association rule mining[J]. Journal of Computer Security,2005,1(13): 593-622.

[6]NIU B,ZHU X,ZHANG T,et al. P-match: priority-aware friend discovery for proximity-based mobile social networks[C]//10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems.c2013: 351-355.

[7]LI R,WU C. An unconditionally secure protocol for multi-party set intersection[M]. 5th Springer Applied Cryptography and Network Security,c2007: 226-236.

[8]KERSCHBAUM F. Outsourced private set intersection using homomorphicencryption[C]//7th ACM Symposium on Information,Computer and Communications Security. c2012: 85-86.

[9]LI M,YU S,CAO N,et al. Privacy-preserving distributed profile matching in proximity-based mobile social networks[J]. IEEE Transactions on Wireless Communications,2013,12(5): 2024-2033.

[10]ZHANG R,ZHANG J,ZHANG Y,et al. Privacy-preserving profile matching for proximity-based mobile social networking[J]. IEEE Journal on Selected Areas in Communications,2013,31(9): 656-668.

[11]THAPA A,LI M,SALINAS S,et al. Asymmetric social proximity based private matching protocols for online social networks[J]. IEEE Transactions on Parallel and Distributed Systems,2015,26(6):1547-1559.

[12]CHU W T,CHANG F C. A privacy-preserving bipartite graph matching framework for multimedia analysis and retrieval[C]//5th ACM International Conference on Multimedia Retrieval,c2015: 243-250.

[13]JECKMANS A,TANG Q,HARTEL P. Poster: privacy-preserving profile similarity computation in online social networks[C]//18th ACM Conference on Computer and Communications Security. c2011:793-796.

[14]WANG B,LI B,LI H. Gmatch: secure and privacy-preserving group matching in social networks[C]//55th IEEE Global Communications Conference. c2012: 726-731.

[15]NIU B,HE Y,LI F,et al. Achieving secure friend discovery in social strength-aware PMSNs[C]//34th IEEE Military Communications Conference,c2015: 947-953.

[16]PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[J]. Springer Cryptology-EUROCRYPT,1999,547(1):223-238.

[17]RANE S,SUN W,VETRO A. Privacy-preserving approximation of L1 distance for multimedia applications[C]//Multimedia and Expo(ICME). c2010: 492-497.

[18]ZHANG R,ZHANG R,SUN J,et al. Fine-grained private matching for proximity-based mobile social networking[C]//INFOCOM. c2012:1969-1977.

Privacy matching-based service proxy discovery scheme

GENG Kui1,WAN Sheng1,LI Feng-hua1,2,HE Yuan-yuan2,WANG Han-yi2

(1.State Key Laboratory of Integrated Service Networks,Xidian University,Xi’an 710071,China;2.State Key Laboratory of Information Security,Institute of Information Engineering,CAS,Beijing 100093,China)

According to user’s requirements on the proxy performance,cost and safety in proxy discovery,and the privacy-preserving issue during the process of the demand private matching,a new private matching algorithm was presented based on Paillier homomorphic encryption,comprehensively considered the attributes of user and agents and their priority. It included four steps: building the similarity function based on Euclidean distance,carrying on the private matching by encryption algorithm,calculating the similarity and screening the proxy chain. Proposed scheme introduced semi trusted primary proxy from the global level,which is to manage all the sub proxy’s business type and the connection status,and do the main computational overhead.At the same time,Euclidean distance and Paillier homomorphic encryption algorithm were combined to support the multivariate attributes with priority to match,which can effectively protect the privacy of user and sub proxy. Finally,security analysis and evaluation results show the effectiveness and safety of proposed scheme.

proxy,service proxy discovery,privacy matching,homomorphic encryption

s:The Key Program of the National Natural Science Foundation of China-Guangdong Union Foundation(No.U1401251),The National High Technology Research and Development Program of China (863 Program)(No.2015AA016007),The National Natural Science Foundation of China (No.61502489)

TP393

A

2016-03-04；

2016-07-28

李鳳華，lfh@iie.ac.cn

國家自然科學基金委—廣東聯合基金資助項目（No.U1401251）；國家高技術研究發展計劃（“863”計劃）基金資助項目（No.2015AA016007）；國家自然科學基金資助項目（No.61502489）

10.11959/j.issn.1000-436x.2016164

耿魁（1989-），男，湖北紅安人，西安電子科技大學博士生，主要研究方向為網絡安全。

萬盛（1987-），男，江蘇南通人，西安電子科技大學博士生，主要研究方向為網絡安全與隱私保護。

李鳳華（1966-），男，湖北浠水人，博士，中國科學院信息工程研究所副總工、研究員、博士生導師，主要研究方向為網絡與系統安全、信息保護、隱私計算。

何媛媛（1985-），女，湖北松滋人，中國科學院信息工程研究所博士生，主要研究方向為信息安全、隱私保護。

王瀚儀（1994-），女，吉林省吉林市人，中國科學院信息工程研究所博士生，主要研究方向為網絡安全。