一種高效的百萬富翁問題協(xié)議及其應(yīng)用

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

（河南理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，河南焦作 454000）

0 概述

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

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

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

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

1 基礎(chǔ)知識

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

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

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

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

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

1.2 ELGamal同態(tài)加密變體算法

ELGamal同態(tài)加密［22］變體算法如下：

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

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

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

由于存在以下關(guān)系式：

因此，ELGamal同態(tài)加密變體算法滿足如下性質(zhì)：

2 MP解決方案

2.1 改進的0～1編碼規(guī)則

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

0-1編碼規(guī)則如下：

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

根據(jù)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協(xié)議

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

2.2.1 設(shè)計方案

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

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

基于0-1編碼規(guī)則的MP協(xié)議實現(xiàn)流程如下：

協(xié)議1基于0-1編碼的MP協(xié)議

該協(xié)議具體內(nèi)容如下：

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

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

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

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

4）Bob將E(M)發(fā)送給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 協(xié)議的正確性與安全性分析

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

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

正確性證明：

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

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

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

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

安全性證明：

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

1）構(gòu)造模擬器S1。

具體步驟如下：

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

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

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

2）構(gòu)造模擬器S2。

具體步驟如下：

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

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

3 協(xié)議性能分析

3.1 計算效率分析

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

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

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

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

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

3.2 計算耗時分析

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

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

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

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

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

4 集合交集的勢

4.1 問題描述

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

4.2 協(xié)議設(shè)計

本文結(jié)合協(xié)議1，設(shè)計出求解保密集合交集勢的協(xié)議，其具體內(nèi)容如下：

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

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

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

求解保密隱私數(shù)據(jù)集合交集勢的協(xié)議實現(xiàn)流程如下：

協(xié)議2求解保密隱私數(shù)據(jù)集合交集勢的協(xié)議

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

正確性證明：

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

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

安全性證明：

采用模擬器S1和模擬器S2證明定理2，首先構(gòu)造模擬器S1。

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

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

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

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

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

5 結(jié)束語

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