一種高效的百萬富翁問題協議及其應用

張 靜，何 錚，葛炳輝，湯永利，葉 青

（河南理工大學計算機科學與技術學院，河南焦作 454000）

0 概述

安全多方計算（Secure Multi-Party Computation，SMC）是指兩個及兩個以上的參與者在不泄露各自隱私數據的情況下，利用隱私數據進行保密計算并共同完成某項計算任務。SMC可滿足人們利用隱私數據進行保密計算的需求，同時兼顧數據的保密性與共享性，因此被廣泛應用于機器學習［1］、數據分析［2］、社交網絡［3］以及醫療信息等領域。

百萬富翁問題（Millionaires’Problem，MP）是安全多方計算中的基本問題，其在1982年由YAO提出［4］后引起多方關注。近年來，研究人員相繼提出多種解決該問題的方法。文獻［5］將安全多方計算規約到智力游戲中，利用混淆電路解決百萬富翁問題。文獻［6］采用不經意傳輸工具對兩方輸入進行雙重加密，設計一種解決百萬富翁問題的安全雙方計算協議。文獻［7］使用不經意傳輸工具并通過簡單異或運算解決百萬富翁問題。文獻［8-9］借助茫然第三方提出一種安全的百萬富翁比較協議，解決第三方合謀問題。文獻［10］利用零知識證明構造一種百萬富翁問題協議。文獻［11-13］通過私有置換操作提出基于卡片的密碼協議，解決了百萬富翁問題。文獻［14-15］利用對稱密碼解決惡意模型下的百萬富翁問題。

利用編碼是解決百萬富翁問題的有效措施之一。文獻［16］采用0-1編碼將雙方待比較的數據轉化為0/1集合，結合具有乘法同態性的加密算法解決百萬富翁問題，但其計算復雜度較高且無法精確區分兩數相等的情況。文獻［17］利用基于二次剩余困難問題的GM加密算法，通過構造0-1編碼將數據編碼轉換為向量，提出一種基于幾何方法的有理數比較協議，但GM算法在解密過程中的時間開銷隨二次非剩余集合增大呈線性增長。文獻［18］使用文獻［16］中編碼方式提出一種基于DDH假設的方案，但該方案僅適用于輸入較小數據，當兩個待比較數據較大時計算開銷較高。文獻［19］結合1-r編碼方式和ELGamal同態加密算法解決數據比較問題，提出一種數據比較協議并將其應用于保密數據排序。文獻［20-21］提出0-1-2編碼方法，同時利用Paillier同態加密算法將百萬富翁問題轉化為向量問題求解。雖然文獻［19-21］提出的方法能有效解決百萬富翁問題中的兩數相等問題，但計算效率均較低。

本文提出一種采用0-1編碼的百萬富翁問題協議。通過改進保密數據編碼規則，利用ElGamal同態加密變體算法解決安全兩數比較問題，在半誠實模型下證明協議的正確性和安全性，并從理論和實驗兩個角度對協議的計算復雜度與效率進行分析。

1 基礎知識

1.1 安全多方計算的安全模型

在安全多方計算協議的執行過程中，半誠實參與者在忠實履行協議的同時會保留協議執行過程中的有效信息，并嘗試推導出其他參與方的隱私信息。若安全多方計算協議中參與者均為半誠實參與者，則稱該協議使用的計算模型為半誠實模型。由于本文協議的計算模型均為半誠實模型，因此以下文給出半誠實模型下兩方計算模型的安全性定義。

設Alice和Bob分別擁有隱私數據x、y，π為計算函數f的協議。Alice和Bob希望通過合作計算函數F：(x，y)→(f1(x，y)，f2(x，y))且不泄露各自隱私數據，其中存在概率多項式函數f：{0，1}*×{0，1}*→{0，1}*×{0，1}*，f1(x，y)和f2(x，y)分別為Alice和Bob計算所得函數F的兩個分量。將Alice和Bob在執行P協議過程中得到的消息序列分別記為其所得輸出結果分別記為

定義1（半誠實參與者的保密性）對于函數f，如果存在概率多項式算法S1和S（2也稱為模擬器）滿足式（1）與式（2），則稱其為π保密計算函數。

其中，≡c表示計算上不可區分。若要證明一個安全多方計算協議具備安全性，則需構造模擬器S1和模擬器S2使式（1）與式（2）成立。

1.2 ELGamal同態加密變體算法

ELGamal同態加密［22］變體算法如下：

1）密鑰生成（KeyGen）。給定安全參數k，定義k特別大，采用密鑰生成算法生成1個大小為k比特的素數p以及有限域的1個生成元g，隨機選取x作為私鑰，其對應公鑰h=gxmodp。

2）加密階段（Enc）。給定消息M∈，選擇隨機數r，密文E(M)=(c1，c2)=(grmodp，gMhrmodp)。

3）解密階段（Dec）。將密文E(M) 解密為gM=對明文m1和m2加密后得到：

由于存在以下關系式：

因此，ELGamal同態加密變體算法滿足如下性質：

2 MP解決方案

2.1 改進的0～1編碼規則

百萬富翁問題的實質是在保密情況下比較兩數大小，即Alice有1個隱私數據x，Bob有1個隱私數據y，兩人在不泄露x和y大小的前提下合作計算并比較兩數大小。為解決該問題，本文將文獻［20］中保密數據編碼規則改進為0-1編碼規則，并利用該規則構造基于0-1編碼的百萬富翁問題協議。

0-1編碼規則如下：

設x，y∈{ν1，ν2，…，νn}=U，其中ν1＜ν2＜···＜νn。令x=νk且y=νl(1≤k，l≤n)，根據x與U構建只含0和1的向量α=(α1，α2，…，αn)，具體規則如下：

根據y=νl在U中的位置計算M=αl+αl+1。若M=0，則k＞l，即x＞y；若M=1，則k=l，即x=y；若M=2，則k＜l，即x＜y。

2.2 基于0-1編碼的MP協議

本文利用0-1編碼規則提出一種解決百萬富翁問題的協議，以下介紹MP協議的具體設計方案，并對其正確性與安全性進行分析。

2.2.1 設計方案

MP協議利用0-1編碼規則將判斷隱私數據x與y大小的問題歸約到求解αl+αl+1值的問題，主要通過兩元素之和來判斷兩數大小，該協議框架如圖1所示。

圖1 基于0-1編碼規則的MP協議框架Fig.1 MP protocol framework based on 0-1 coding rule

基于0-1編碼規則的MP協議實現流程如下：

協議1基于0-1編碼的MP協議

該協議具體內容如下：

1）Alice按照式（9）中的規則利用自身隱私數據x和隱私數據集合U={ν1，ν2，…，νn}構造1個只含0和1的向量A=(α1，α2，…，αn)。

2）Alice根據ELGamal同態加密算法生成公私鑰對(pk，sk)，選取不同的隨機數ri，利用公鑰pk將向量A中各個元素分別加密得到E(A)=(E(α1)，E(α2)，…，E(αn))，其中，αi∈A，i=1，2，…，n，并將E(A)發送給Bob。

3）Bob根據y在隱私數據集合U中的排列位置（即al所在位置）進行以下操作：

（2）計算E(M)=E(αl)E(αl+1)。

4）Bob將E(M)發送給Alice。

5）Alice利用私鑰sk對E(M)進行解密操作D(E(M)) 得到M。若M=1，則x＞y；若M=g，則x=y；若M=g2，則x＜y。

2.2.2 協議的正確性與安全性分析

本文對基于0-1編碼規則的MP協議正確性與安全性進行分析。

定理1在半誠實模型下，協議1是正確的，同時也是安全的。

正確性證明：

2）基于ELGamal的同態加密變體算法具有加法同態性，計算公式如下：

3）Bob利用公鑰對M=αl+αl+1計算過程進行加密：

4）Bob對E(M)進行解密：

5）由于選取的安全參數k很大，因此生成大小為kbit的p很大，生成元g非常小且滿足gMmodp=gM。針對計算得到的gM：當gM=1時，M=0，y位置在x左側，x＞y；當gM=g時，M=1，y位置與x位置相同，x=y；當gM=g2，M=2，y位置在x右側，x＜y。

安全性證明：

Alice根據自身隱私數據x和雙方的共有集合U={ν1，ν2，…，νn}構建向量A=(α1，α2，…，αn)，其中αi∈{0，1}，i=1，2，…，n。Alice擁有公鑰pkA與私鑰skA，在計算每個E(αi)(i=1，2，…，n) 時，其對利用ELGamal同態加密算法選取的不同r進行加密操作，即其中，αi∈A，i=1，2，…，n，由于選取的r不同造成密文不同，因此對于加密后的向量E(A)=(E(α1)，E(α2)，…，E(αn))，Bob無法通過解密從中獲取有用信息；Bob自身隱私數據y在集合U中位置為已知，其在向量A中對應的位置al不變，Bob為混淆密文選取隨機rz∈，若其利用al直接計算E(M)=E(αl)E(αl+1)，則Alice可通過列舉方式計算每兩個元素相乘的密文值，當E(M′)=E(M)時，可確定Bob的隱私數據y在集合U中的位置，從而造成其隱私數據泄露。因此，雙方在整個過程中均無法獲得對方的隱私信息。以下通過構造模擬器S1和模擬器S2進一步證明協議的安全性。

1）構造模擬器S1。

具體步驟如下：

（1）模擬器S1接受輸入(x，p(x，y))，由p(x，y) 的值構造y′且滿足p(x，y′)=p(x，y)，并用x′和y進行模擬。根據x與U構建只含0和1的向量A=(α1，α2，…，αn)。

（2）利用ELGamal同態加密算法選取不同r對向量A=(α1，α2，…，αn)進行加密，得到：

（4）對數據E(M′)進行解密得到M'。

2）構造模擬器S2。

具體步驟如下：

（1）模擬器S2接受輸入(p(x，y)，y)，根據p(x，y)的值構造x′且滿足p(x′，y)=p(x，y)，并用x′和y進行模擬。根據x′與U′構建只含0和1的向量A′=

（2）利用ELGamal同態加密算法選取不同r′對向量A′=進行加密，得到：

3 協議性能分析

3.1 計算效率分析

對協議1和文獻［16，19，21］協議的計算復雜度、通信輪數以及適用范圍進行對比。由于文獻［16，19］協議基于ElGamal同態加密算法，文獻［21］協議基于Paillier同態加密算法，本文協議基于ELGamal同態加密變體算法，因此為便于對比分析，令Paillier同態加密算法模為N，數據長度為n，ElGamal同態算法及其變體算法的模為P，比較結果如表1所示。

表1 3種協議的不同性能對比Table 1 Performance comparison of three protocols

從上述3種協議的計算復雜性來看，協議1、文獻［16，19］協議都是基于ElGamal同態加密，而采用ElGamal同態加密算法進行1次加密需2lbP次模乘計算，進行1次解密需lbP次模乘計算。協議1中Alice進行n次加密和1次解密，Bob進行3次模乘計算，總計算開銷為(2n+3) lbP+2次模乘計算；文獻［16］協議需n次加密、n次解密和2nlbP+4n-6次模乘計算，總計算開銷為5nlbN+4n-6次模乘計算。文獻［19］協議中Alice需n次加密和1次解密，Bob需1次加密和2次模乘計算，總計算開銷為(2n+3) lbP+2次模乘計算。文獻［21］協議需n次加密、1次解密與l次模乘計算，由于該協議是基于Paillier同態加密，因此由Paillier同態加密算法中每次加密和解密需2lbN次模乘計算可知，文獻［21］協議的總計算開銷為2(n+1) lbN+l次模乘計算。

從通信輪數來看，協議1中Alice將密文E(A)發送給Bob，Bob將處理后的密文E(M) 反饋給Alice，Alice對其解密后得到結果M并告知Bob，在整個協議執行過程中雙方共通信3次，因此，協議1通信輪數為3，其他3種協議的通信輪數與協議1相同。

由上述分析可知，雖然協議1的通信輪數與其他協議相同，但是其計算復雜度較其他協議更低。此外，與文獻［16］協議相比，協議1可更好地比較兩數據相等的問題。因此，協議1整體計算效率優于其他協議。

3.2 計算耗時分析

將協議1和文獻［16，19，21］協議加密和解密的計算耗時進行對比。實驗采用Windows10 64位操作系統，Inter?CoreTMi7-4720HQ 2.60 GHz CPU，8 GB內存以及MyEclipse 2017CI編譯環境。假設上述協議中雙方商定向量元素個數n=100，令Paillier同態加密算法與ELGamal同態加密算法中模數相同，則在模數為128 bit、256 bit、512 bit和1 024 bit時分別計算這2種同態加密算法加密和解密的耗時，結果如表2所示。

表2 2種算法在不同模數下加密和解密的耗時Table 2 Encryption and decryption time consumption of two algorithms under different modulusms

由表2可計算得到這2種算法加密和解密的平均耗時，結合3.1節中對4種協議的效率分析可得到各協議在不同模數下的時間開銷，結果如圖2所示（文獻［21］協議中l值取決于Bob的隱私數據在商定向量中的位置，l取值范圍為［1，100］，由于實驗假定所商定向量的長度n=100，為便于對比，設定l=50）。由圖2可以看出：文獻［16］協議的時間開銷最高，協議1與文獻［19］協議的時間開銷最低且兩者很接近。對協議1與文獻［19］協議在不同模數下的時間開銷進行對比，結果如表3所示。可以看出，協議1在不同模數下的耗時均低于文獻［19］協議。由上述分析可知，協議1時間開銷低于其他協議，此結果與協議計算效率分析結果一致。

圖2 4種協議在不同模數下的時間開銷Fig.2 Time cost of four protocols under different modulus

表3 協議1與文獻［19］協議在不同模數下的時間開銷Table 3 Time cost of the protocol 1 and the protocol in reference［19］under different modulus

4 集合交集的勢

4.1 問題描述

當前社交網絡已深入人們的日常生活，為擴大用戶交友范圍，云服務器會向每個用戶推薦可能認識的好友，其推薦時判斷依據為用戶之間相同好友數量。然而在服務器與用戶交互過程中，服務器在精準計算不同用戶之間相同好友數量的同時，還要保證用戶隱私不被泄露。如果將計算相同好友數量的過程視為安全兩方的計算問題，則該問題可轉化為求解安全兩方集合交集個數的問題，即：Alice擁有隱私數據集合W1={x1，x2，…，xn}，Bob擁有隱私數據集合W2={y1，y2，…，ym}，Alice與Bob在不泄露自身隱私數據集合情況下求解兩集合交集的勢。

4.2 協議設計

本文結合協議1，設計出求解保密集合交集勢的協議，其具體內容如下：

1）Alice和Bob利用自身隱私數據集合與共有隱私數據集合U={ν1，ν2，…，νz}(z≥m+n) 構造0-1編碼向量A=(a1，a2，…，az)和B=(b1，b2，…，bz)，編碼規則如下：

2）(G，D，E) 為ElGamal同態加密算法，k為設定的安全參數，Alice運行G（k）生成算法的公私鑰對(pk，sk)。Alice用公鑰pk加密向量A得到E(A)=(E(a1)，E(a2)，…，E(az))，并將E(A)發送給Bob。

4）Alice通過私鑰sk對E(M) 進行解密得到數據ω=gM，兩集合交集的勢M=loggω。

求解保密隱私數據集合交集勢的協議實現流程如下：

協議2求解保密隱私數據集合交集勢的協議

定理2在半誠實模型下，協議2是正確的，同時也是安全的。

正確性證明：

4）Bob對E(M)進行解密：

5）由于選取的安全參數k很大，因此生成大小為k比特的p很大，生成元g非常小且滿足gMmodp=gM。對解密后D(E(M)) 的數據ω進行計算得到M=loggω，M即集合的勢。

安全性證明：

采用模擬器S1和模擬器S2證明定理2，首先構造模擬器S1。

1）模擬器S1接受輸入(x，p(x，y))，由p(x，y)的值構造y′且滿足p(x，y′)=p(x，y)，并用x′和y進行模擬。根據x與U構建只含0和1的向量A=(a1，a2，…，az)。通過模擬器S1構造向量B′=()。

2）利用ELGamal同態加密算法選取不同的r對向量A=(a1，a2，…，az)進行加密，得到：

4）對數據E(M')進行解密得到M′。

在協議2中，Alice需執行n次加密、1次解密和1次對數計算。Bob需要執行z次模冪計算和z次模乘運算，定義Mul、Exp、lb分別代表1次模乘計算、1次模冪計算和1次對數計算。因此，協議2的計算復雜度為((2n+1) lbN+z) Mul+zExp+1×lb。

在協議2中，Alice將編碼后的隱私數據集合元素A進行加密，將加密結果E(A)發送給Bob，Bob對E(A) 進行處理得到E(M) 并將其反饋給Alice，Alice對E(M)解密并向Bob公布結果。在整個協議執行過程中雙方共通信3次，因此通信輪數為3。

5 結束語

百萬富翁問題作為安全多方計算的基本模塊，常見于數據挖掘、數據查詢和計算幾何等方面，而現有解決方案計算效率與安全性較低。本文提出一種基于0-1編碼的百萬富翁問題協議，利用ELGamal同態加密的性質解決百萬富翁問題，在半誠實模型下證明其安全性，并用協議求解安全兩方集合交集個數。實驗結果表明，與采用ElGamal和Paillier同態加密算法的協議相比，該協議計算效率更高。后續將在兩數比較的基礎上進行多數比較，以解決帶隱私保護的多集合交集問題。