可驗證的隱私數據比較與排名查詢方法

2023-05-12 10:41:01 2

專利名稱：可驗證的隱私數據比較與排名查詢方法
技術領域：
本發明涉及數據安全與分析處理領域，特別涉及一種可驗證的隱私數據比較與排名查詢方法。
背景技術：
數據大小比較和基於數據比較的數據排名作為一種非常基礎的數據查詢，被廣泛應用在各種數據應用場景，如傳感網絡中節點進行數據查詢，社交網絡中好友間數據的比較查詢，雲計算等。很多應用場景中，僅僅需要數據的比較和排名結果，但參與比較和排名的數據本身是一種隱私，具有敏感性需要得到保護，比如用戶希望在不暴露個人分數的情況下比較兩個用戶的得分，進行個人分數在多用戶中排名的查詢。安全多方計算最簡單的解決方法便是採用可信的中心伺服器，計算參與方將各自隱私的數據交給可信中心，由可信中心進行計算，再將計算結果返回給參與方。在這種有中心的解決方案中，固然可以進行數據大小比較和排名的運算。但是在很多情況下，如無線自組織傳感網，移動社交網絡等，並不是所有用戶都能訪問到中心伺服器，例如在沒有網際網路接入或者在伺服器失效的情況下運算便無法展開。頻繁與計算中心交互還會帶來高額的費用，同時也增大了數據隱私暴露的隱患。此外，由於伺服器並非絕對可信，伺服器被攻擊可能導致大量用戶隱私暴露，因此很多用戶並不願意將其隱私的數據暴露給伺服器。由於採用可信中心的方式存在的種種局限，因此急需無中心的隱私數據比較和排名查詢方法。目前已經有部分工作支持保護隱私的無中心數據比較，來保證每個用戶只能得到比較和排名的結果而無法得到他人的隱私數據。但是現有的方法計算開銷都非常大，尤其是在計算資源受限的行動裝置上幾乎無法進行，使得它們在很多場景下都難以得到實際應用。目前所有相關的解決方案都將重點放在了隱私保護，保證數據不被洩露，而忽略了運算輸入和結果的可驗證性。採用這些方法的進行比較和排序，其結果的正確性都建立在用戶誠實地執行該方法的假設上。實際上，惡意用戶可以通過簡單的偽造其輸入數據就能更改數據比較結果，導致錯誤的排名結果；或者先得到比較結果的用戶可以向其他用戶謊報排名結果。例如，惡意用戶可以簡單的輸入一個非常大的數值而獲得最高排名。這樣無法驗證的運算結果顯然無法滿足大量安全性較高的應用的需要。

發明內容
(一)要解決的技術問題本發明要解決的技術問題是如何提供一種可驗證的隱私數據比較與排名查詢方法，使得該方法在整個查詢過程中無需伺服器參與，不受平臺限制，能夠在比較數據降低計算開銷的同時保護數據的安全性，並能夠提供一種嚴密的驗證機制。(二)技術方案為解決上述技術問題，本發明提供了一種可驗證的隱私數據比較與排名查詢方法，該方法運行的系統中存在可信第三方，所述可信第三方擁有公鑰PkT和私鑰SkT，該方法包括步驟SI每個用戶連接可信第三方，獲取一對公鑰Pki和私鑰Ski,由可信第三方對用戶的隱私數據Vi和相關的隨機數進行驗證，使用用戶獲取的公鑰Pki對隱私數據Vi和相關的隨機數進行加密，對加密的數據進行籤名形成數字證書頒發給用戶；S2用戶P1發送證書給用戶P2，用戶P2對用戶P1發送的數字證書中加密的數據進行驗證和同態計算，並將同態計算的結果發送給用戶P1 ；S3用戶P1解密用戶P2發送的同態計算結果，得到隱私數據的比較結果；S4用戶P1驗證隱私數據的比較結果的正確性；

S5針對各用戶進行步驟S2-S5，獲得各用戶的排名。優選的，步驟SI中，所述隱私數據Vi和相關的隨機數的加密和驗證方法為可信第三方為每個用戶分配一個標示IDi,定義Ei (VijTi)表示使用快速Paillier加密算法利用用戶Pi的公鑰Pki對Vi進行加密，其中^是作為快速Paillier加密算法輸入的隨機數。用戶Pi選擇一系列隨機數{ 6 J發送給可信第三方來驗證Vi的合法性。優選的，步驟SI中，所述對加密的數據進行籤名和形成數字證書的方法為用一系列相關隨機數{ 6 J分別乘以Vi得到集合{ 8 kVi}，可信第三方使用用戶Pi的公鑰Pki加密得到Ei (Vi, !Ti)、集合(Ei ( S k，rj}和Ei ( S kVi，r/ )}，並將rjPr/告知然後可信第三方分別對所述Ei (Vi，ri)、集合{EjSkA)}和)}進行哈希，再對哈希的結果用可信第三方的私鑰SkT進行籤名Sig形成該數據的證書C(Pi, Vi) =和一系列證書的集合{C(Pi,6 J5Vi)} = { }其中r/為隨機數。優選的，步驟S2中所述用戶P1發送的證書為(P1, V1) =所述數據的數據驗證和同態計算方法為用戶P2隨機地從V2的證書集合{C(p2，8 kv2)}中選出一個證書 C(p2, S1V2) = p2基於P1的證書中的值，利用快速Paillier加密系統的同態計算,得到同態計算結果e: = E1 ( 6 ^1+ 6 2, 6 ^1+ 8 2), e2 = E1 ( 6 ^2+ 5 2，r2), e3 = E2 ( 3 2，r2"),e4 = E1 Cr2V1+!"" 2, Y2Y^r" 2), e5 = El (r" 2+r" 2, r2)其中62和1>" 2為生成的隨機數。優選的，步驟S3中，所述得到隱私數據比較結果方法為定義DiG)表示使用快速Paillier解密算法用Pi的私鑰Ski對同態計算結果進行解密,計算(I1 = Dje1)和d2 =D1G2)，比較Cl1和d2的大小即可得到隱私數據V1和V2的大小比較結果。優選的，步驟S4中，所述驗證正確性的方法為A計算d4 = D1 (e4), d5 = D1 (e5),然後用證書C(P2，S1V2)中的值，以及e3，採用快速Paillier加密的同態性計算以下等式E2 ( 6 JV1+ 8 2，d4) = E2 ((I1), E2 ( 6 ^2+ 8 2, d5) = E2 (d2)
如果兩個等式均成立，則說明P1得到正確的比較結果，否則說明P2對計算結果作假，則該計算結果無效。優選的，步驟S5中，獲得各用戶的排名的具體方法為 1在11個用戶中，P1反覆採用步驟S2到S4的方法，分別與其他n-1個用戶進行的保護隱私的數據比較和驗證，並記錄數值小於P1的用戶的個數R。比較完成後，P1就能得到自己在n個用戶中的排名為R+1，採用相同的方法獲得各用戶的排名。優選的，所述快速Paillier加密算法為c = E (m, r) = gm+nrmodn2其中m為加密數據，n為用戶公鑰的模，g為用戶公式的基，r為隨機數。優選的，所述快速Paillier加密系統的同態計算算法為EOn1, r:) E (m2, r2)mod n2 = EOi^m2, r1+r2)mod n2Eiin-1, F1 )m'2mod n2 = EOn1 m2, ^ rn2)mod n2其中Iiipm2為加密數據，n為用戶公鑰的模，I^r2為隨機數。優選的，所述快速Paillier解密算法為
權利要求
1.一種可驗證的隱私數據比較與排名查詢方法，其特徵在於，該方法運行的系統中存在可信第三方，所述可信第三方擁有公鑰PkT和私鑰SkT，該方法包括步驟 Si每個用戶連接可信第三方，獲取一對公鑰Pki和私鑰Ski,由可信第三方對用戶的隱私數據Vi和相關的隨機數進行驗證，使用用戶獲取的公鑰Pki對隱私數據Vi和相關的隨機數進行加密，對加密的數據進行籤名形成數字證書頒發給用戶； S2用戶P1發送證書給用戶P2，用戶P2對用戶P1發送的數字證書中加密的數據進行驗證和同態計算，並將同態計算的結果發送給用戶P1 ； S3用戶P1解密用戶P2發送的同態計算結果，得到隱私數據的比較結果； S4用戶P1驗證隱私數據的比較結果的正確性； S5針對各用戶進行步驟S2-S5，獲得各用戶的排名。
2.權利要求1所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，步驟SI中，所述隱私數據Vi和相關的隨機數的加密和驗證方法為可信第三方為每個用戶分配一個標示IDi,定義Ei (Vyri)表示使用快速Paillier加密算法利用用戶Pi的公鑰PkJt Vi進行加密，其中A是作為快速Paillier加密算法輸入的隨機數。用戶Pi選擇一系列隨機數{ 6 J發送給可信第三方來驗證Vi的合法性。
3.權利要求2所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，步驟SI中，所述對加密的數據進行籤名和形成數字證書的方法為用一系列相關隨機數{Sk}分別乘以Vi得到集合{ SkvJ，可信第三方使用用戶Pi的公鑰Pki加密得到Ei(Vpri)和集合{EjSk，！^)}和i{E(SkVi，ri' )}，並將巧和巧'告知Pi。然後可信第三方分別對所述Ei (Ui)、集合{EjSkA)}和{EjSkhr/ )}進行哈希，再對哈希的結果用可信第三方的私鑰SkT進行籤名Sig形成該數據的證書C(Pi, Vi) = 和一系列證書的集合{C(Pi, 6 J5Vi)} = { I 其中r/為隨機數。
4.權利要求3所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，步驟S2中所述用戶P1發送的證書為 (P1, V1) = 所述數據的數據驗證和同態計算方法為用戶P2隨機地從V2的證書集合{C(p2，SkV2)}中選出一個證書 C(p2, S1V2) =P2基於P1的證書中的值，利用快速Paillier加密系統的同態計算，得到同態計算結果 e: = E1 ( 6 JV1+ 6 2, 6 ^1+ 8 2), e2 = E1 ( 6 ^2+ 6 2，r2), e3 = E2 ( 6 2, r2"), e4 = E1Cr2V1+!"" 2, Y2Y^r" 2), e5 = E1 (r' 2+r" 2, r2) 其中32和1>" 2為生成的隨機數。
5.權利要求4所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，步驟S3中，所述得到隱私數據比較結果方法為定義DJe)表示使用快速Paillier解密算法用Pi的私鑰Ski對同態計算結果進行解密,計算(I1 = D1 (ej)和d2 = D1 (e2),比較(I1和d2的大小即可得到隱私數據V1和V2的大小比較結果。
6.權利要求5所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，步驟S4中，所述驗證正確性的方法為=P1計算d4 = D1 (e4), d5 = D1 (e5),然後用證書C (P2, 8 ^2)中的值，以及e3,採用快速Paillier加密的同態性計算以下等式
7.權利要求6所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，步驟S5中，獲得各用戶的排名的具體方法為=P1在n個用戶中，P1反覆採用步驟S2到S4的方法，分別與其他n-1個用戶進行的保護隱私的數據比較和驗證，並記錄數值小於P1的用戶的個數R。比較完成後，P1就能得到自己在n個用戶中的排名為R+1，採用相同的方法獲得各用戶的排名。
8.權利要求2所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，所述快速Paillier加密算法為 c = E (m, r) = gm+nrmodn2 其中m為加密數據，n為用戶公鑰的模，g為用戶公式的基，r為隨機數。
9.權利要求4所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，所述快速Paillier加密系統的同態計算算法為
10.權利要求8所述的可驗證的隱私數據比較與排名查詢方法，其特徵在於，所述快速Paillier解密算法為
全文摘要
本發明公開了一種可驗證的隱私數據比較與排名查詢方法，該方法包括步驟S1系統初始化，對用戶的隱私數據vi和相關的隨機數進行驗證和加密，對加密的數據進行籤名形成數字證書頒發給用戶；S2用戶p1發送證書給用戶p2，P2對接收的數據進行驗證和同態計算，並將結果發送給用戶p1；S3用戶P1解密用戶p2發送的同態計算結果，得到隱私數據的比較結果；S4用戶p1驗證隱私數據的比較結果的正確性；S5針對各用戶進行步驟S2-S5，獲得各用戶的排名。採用本發明的方法能夠在保護用戶隱私數據的情況下進行比較，並對結果進行驗證，保證用戶無法輸入或對比虛假數據，並且在整個查詢過程中無需伺服器參與，處理速度快，計算開銷小，不受平臺限制。
文檔編號G06F17/30GK103064931SQ20121056455
公開日2013年4月24日 申請日期2012年12月21日 優先權日2012年12月21日
發明者張蘭, 李向陽, 劉雲浩 申請人:清華大學