劉 新, 張瑞玲, 徐 剛, 陳秀波

1. 內(nèi)蒙古科技大學(xué)信息工程學(xué)院, 包頭 014010

2. 北方工業(yè)大學(xué)信息學(xué)院, 北京 100144

3. 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室信息安全中心, 北京 100876

1 引言

隨著區(qū)塊鏈、大數(shù)據(jù)、人工智能等新興技術(shù)在社會各領(lǐng)域融合創(chuàng)新快速發(fā)展, 數(shù)據(jù)信息不斷豐富, 人們的生活得到了許多便利. 然而在享有這些數(shù)據(jù)資源的同時, 信息保密也成為了人們的關(guān)注焦點. 安全多方計算是用于解決隱私數(shù)據(jù)協(xié)同計算的重要工具之一, 受到廣泛關(guān)注[1,2].

最早的安全多方計算問題是由計算機科學(xué)家姚期智教授提出的百萬富翁問題(millionaires’ problem)[3]. 隨后Goldreich、Lindell 等[4,5]研究學(xué)者對其進行了深入的研究, 安全多方計算研究領(lǐng)域不斷擴展, 其中包括保密數(shù)據(jù)挖掘、保密的計算幾何和集合問題、保密的科學(xué)計算等[6,7]. 這些研究不斷地推動安全多方計算向前發(fā)展, 切實解決了許多實際問題.

安全計算幾何問題是研究安全多方計算的一個重要分支, 而點與凸多邊形關(guān)系判斷問題是一個典型的安全多方計算幾何問題, 應(yīng)用領(lǐng)域廣泛. 但其研究方案并不多見, 僅有的研究方案也是在半誠實模型下設(shè)計的[8,9], 不能抵抗惡意敵手的攻擊.

本文設(shè)計了惡意模型下的點與凸多邊形包含問題的判定協(xié)議, 貢獻如下:

(1) 本文首先研究了半誠實模型下的點與凸多邊形關(guān)系判定協(xié)議[8], 并分析了可能存在的惡意行為;

(2) 在半誠實協(xié)議的基礎(chǔ)上, 利用Paillier 加密算法, 借助零知識證明和分割-選擇等密碼學(xué)工具, 設(shè)計了惡意模型下的保密判定點與凸多邊形包含問題協(xié)議;

(3) 利用理想-實際范例方法證明在惡意模型下協(xié)議的安全性, 并分析對比惡意模型下協(xié)議的優(yōu)越性.

2 相關(guān)工作

點和凸多邊形關(guān)系的保密判定, 是指在保護兩方隱私的情況下, 判斷一方的點是否包含在另一方的凸多邊形中. 這個問題在現(xiàn)實生活中有著非常廣泛的應(yīng)用, 如保密的范圍查詢、保密定位搜索等.

文獻[8] 針對判斷點與凸多邊形的位置關(guān)系, 首先將點與凸多邊形的包含問題轉(zhuǎn)化為計算三角形的面積問題, 然后借助內(nèi)積協(xié)議從而設(shè)計了點與凸多邊形的關(guān)系判定協(xié)議. 然而, 該協(xié)議是在半誠實模型下提出的, 不能抵抗惡意敵手的攻擊.

文獻[9] 首先在OTn1和矢量幾何的基礎(chǔ)上, 設(shè)計了一種茫然安全點與線位置關(guān)系判斷協(xié)議. 然后, 將此協(xié)議作為基礎(chǔ)協(xié)議, 并結(jié)合二分檢索法提出了點與凸多邊形位置判定協(xié)議. 該協(xié)議也是在半誠實模型下進行設(shè)計的, 不能抵抗惡意敵手的攻擊.

文獻[10] 將半誠實模型下的百萬富翁問題解決方案改造成惡意模型下安全計算協(xié)議, 并用理想-實際范例證明了協(xié)議的安全性. 該文獻在惡意模型下解決了百萬富翁問題, 能夠抵抗惡意敵手的攻擊, 但與本文場景不同.

文獻[11] 首先設(shè)計了一種新的編碼方法, 采用ElGamal 同態(tài)加密, 在半誠實模型下設(shè)計了多個數(shù)據(jù)相等的保密判定協(xié)議, 并進一步利用比特承諾、零知識證明等方法設(shè)計出了惡意模型下多數(shù)據(jù)相等問題判定協(xié)議. 但與本文解決問題的場景不一致.

文獻[12] 采用Paillier 加密算法設(shè)計了兩個有理數(shù)相等的保密判定協(xié)議, 并且最后給出了惡意模型下的有理數(shù)相等保密判定協(xié)議. 該文雖然可以抵抗惡意敵手的攻擊, 但與本文解決的問題不一致.

現(xiàn)有抗惡意敵手的安全多方計算協(xié)議與本文研究的應(yīng)用場景不同, 不能解決點與凸多邊形的保密判定. 而目前保密判定點與凸多邊形的協(xié)議大多又是在半誠實模型下提出的, 不能抵抗惡意敵手的攻擊, 而且存在隱私泄露、甚至可能出現(xiàn)判斷錯誤等問題.

針對上述不足, 本文設(shè)計了惡意模型下保密判斷點和凸多邊形關(guān)系協(xié)議, 并與現(xiàn)有協(xié)議進行對比分析,本協(xié)議效率保持高效, 且可抵抗惡意攻擊.

3 預(yù)備知識

3.1 Paillier 加密算法

3.2 零知識證明

3.3 分割選擇

分割-選擇(cut-and-choose) 是一個重要密碼學(xué)工具. 在大多數(shù)有惡意參與者參與的協(xié)議中, 將采用分割-選擇方法. 所謂的分割-選擇方法[15]是一方構(gòu)造并發(fā)送大量的電路, 另一方隨機的選出其中一半的電路, 并要求對方打開電路檢查電路的正確性, 之后對沒有打開的另一半電路進行保密計算. 例如:

3.4 惡意模型的安全性定義

在惡意模型下, 廣為接受的可證明安全方法為理想-實際范例. 所謂理想-實際范例就是協(xié)議具有與理想模型下一樣的安全性.

理想?yún)f(xié)議:Alice 擁有信息x, Bob 擁有信息y, 要計算函數(shù)f(x,y) = (f1(x,y),f2(x,y)). 在協(xié)議結(jié)束后, 雙方分別只得到f1(x,y) 和f2(x,y), 而得不到其他任何信息. 在執(zhí)行協(xié)議計算函數(shù)的過程中, 雙方會借助可信的第三方(trusted third party, TTP) 來計算. 具體情形如下:

(1) Alice 和Bob 分別擁有x、y, 發(fā)給TTP, 誠實的參與者會給TTP 提供真實的輸入, 而惡意的參與者會根據(jù)自己的信息來提供虛假的輸入x′或y′.

(2) 當(dāng)TTP 獲得輸入信息(x,y) 后會計算f(x,y), 并將f1(x,y) 發(fā)送給Alice, 反之發(fā)送特殊符號⊥.

(3) 如果Alice 是惡意參與者, Alice 收到信息f1(x,y) 不再理會TTP, 則TTP 會給Bob 發(fā)送⊥;反之給Bob 發(fā)送f2(x,y).

在理想?yún)f(xié)議中, 雙方除了可以獲得各自的結(jié)果外而得不到其他任何信息. 如果在惡意模型中, 我們執(zhí)行的結(jié)果與理想模型下得到的結(jié)果一樣, 即可以證明惡意模型下協(xié)議是安全的. 值得注意的是, 惡意模型下的協(xié)議在執(zhí)行時應(yīng)至少有一方是誠實的, 否則將不能保證協(xié)議是安全可行的. 在文獻[10] 中給出其安全性定義.

3.5 點與凸多邊形包含問題的描述與轉(zhuǎn)化

(1) 問題描述

Alice 擁有點P0(x0,y0), Bob 擁有多邊形G, 其中G的頂點用Gi(xi,yi) 表示,i= 1,2,··· ,n.P0與G有兩種位置關(guān)系, 即P0?G或者P0??G.

圖1 點在凸多邊形內(nèi)部Figure 1 Points inside convex polygon

圖2 點在凸多邊形外部Figure 2 Points outside convex polygon

(2) 轉(zhuǎn)化規(guī)則

4 半誠實模型下的協(xié)議

半誠實模型下的協(xié)議是設(shè)計惡意模型協(xié)議的基礎(chǔ), 惡意模型協(xié)議是根據(jù)半誠實模型協(xié)議中可能出現(xiàn)的惡意行為來設(shè)計的, 因此分析在半誠實模型下的協(xié)議及其安全性是極其重要的. 在文獻[8] 中, 作者巧妙地將點與凸多邊形的包含問題轉(zhuǎn)化為面積判等問題, 而在計算三角形面積時, 利用內(nèi)積的性質(zhì)并調(diào)用了內(nèi)積協(xié)議, 即〈X,Y1〉+〈X,Y2〉=〈X,Y1+Y2〉. 具體協(xié)議如下:

協(xié)議1 半誠實模型下判斷點與凸多邊形的包含關(guān)系輸入: Alice 擁有點P0(x,y), Bob 擁有凸多邊形G, G 有n 個頂點, 其中i = 1,2,··· ,n.輸出: P0 ?G 或P0 ??G.1 Bob 從G 上選取相鄰的頂點Gi, Gi+1, 獲得Gi(xi,yi), Gi+1(xi+1,yi+1), 計算:Ai =■■■■■yi1 yi+1 1■■■■■, Bi =■■■■■xi1 xi+1 1■■■■■, Ci =■■■■■xiyi xi+1 yi+1■■■■■,即獲得向量Yi = (Ai,Bi,Ci), 并計算得到∑n i=1 Yi.2 Alice 計算得到向量X = (x0,?y0,1), 并發(fā)送給Bob.3 Bob 調(diào)用內(nèi)積協(xié)議得到〈X,∑n i=1 Yi〉, 那么, n 個三角形的面積之和為:n∑S△i = 1 n∑?n∑?〈X,Yi〉 = 1 X,Yi .i=1 2 i=1 2 i=1 4 Bob 計算G 的面積S凸多邊形與∑n i=1 S△i 比較. 當(dāng)S凸多邊形=∑n i=1 S△i, P0 ?G; 否則P0 ??G.5 協(xié)議結(jié)束.

在協(xié)議1 中, 只有在Alice 和Bob 都是半誠實參與者的情況下, 協(xié)議才是安全的. 當(dāng)Alice 或Bob 其中的一方是惡意的, 協(xié)議將不再安全, 需要改進協(xié)議使其對于惡意參與者也是安全的.

5 惡意模型下點與凸多邊形包含問題的保密判斷協(xié)議

解決思路: 分析在半誠實模型協(xié)議中可能出現(xiàn)的惡意敵攻擊行為, 根據(jù)其攻擊的缺口, 設(shè)計相應(yīng)協(xié)議來使得惡意敵手無法進行攻擊或被發(fā)現(xiàn). 協(xié)議1 中可能出現(xiàn)的惡意行為:

(1)在協(xié)議1 的第1、2 步,Alice 和Bob 是根據(jù)自己擁有的數(shù)據(jù)來進行計算的. 在協(xié)議的第2 步Alice可能不會將正確的信息發(fā)送給對方, 這種情況我們將不予考慮. 當(dāng)面對提供不真實輸入的情況時, 在理想模型下也無法解決. 因此, 理想情況下都不可避免的情形, 在惡意模型下我們也不會考慮該種情況.

(2) 協(xié)議1 的第3 步是Bob 調(diào)用內(nèi)積協(xié)議, 這樣Bob 就擁有了主動權(quán), 可以計算n個三角形的面積和來與自己的凸多邊形面積來進行比較, 這樣對Alice 很不公平.

(3) 協(xié)議1 在第4 步存在惡意敵手的攻擊行為, 即Bob 可能不會將正確的計算結(jié)果告訴Alice, 而此時Bob 已經(jīng)知道了點與凸多邊形的位置關(guān)系, 與此同時Alice 不會獲得結(jié)果或者獲得一個錯誤的結(jié)果.

為了防止以上惡意行為, 利用Paillier 加密算法, 借助零知識證明和分割-選擇等密碼學(xué)工具, 改進協(xié)議1 來抵抗惡意敵手的攻擊, 最終雙方一起來驗證結(jié)果. 為了提高效率, 本文巧妙的將點與凸多邊形關(guān)系判斷問題轉(zhuǎn)換為兩數(shù)判等問題, 來設(shè)計惡意模型下的協(xié)議.

5.1 具體協(xié)議

在惡意模型下判斷點與凸多邊形的包含關(guān)系, 我們已經(jīng)巧妙地將點與凸多邊形的問題, 轉(zhuǎn)化為面積判等的問題, 即n個三角形的面積之和是否與凸多邊形的面積相等的問題, 其中Q1代表n個三角形的面積之和,Q2代表凸多邊形的面積. 具體協(xié)議如下所示.

協(xié)議2 惡意模型下判斷點與凸多邊形的包含關(guān)系輸入: Alice 擁有點P0(x0,y0), Bob 擁有凸多邊形G, G 有n 個頂點Gi(xi,yi), 其中i = 1,2,··· ,n.準備階段: Alice 和Bob 分別生成自己的Paillier 密碼系統(tǒng)的公鑰(ga,Na), (gb,Nb), 私鑰λa、λb, 并計算u = gaλa mod N2a, v = gbλb mod N2b, 交換(ga,Na,u) 和(gb,Nb,v).輸出: P0 ?G 或P0 ??G.1 Bob 在凸多邊形G 上任選兩個頂點Gi(xi,yi), Gi+1(xi+1,yi+1), 計算Ai =■■■■■yi1 yi+1 1■■■■■Bi =■■■■■xi1 xi+1 1■■■■■Ci =■■■■■xiyi xi+1 yi+1■■■■■;i=1 Yi, 然后將∑n i=1 Yi 發(fā)送給Alice.2 Alice 構(gòu)造向量X = (x0,?y0,1), 然后調(diào)用內(nèi)積協(xié)議得到〈X,∑n i=1 Yi〉, 從而計算n 個三角形的面積和Q1 = ∑n i=1 Q△i = 1 Bob 構(gòu)造向量Yi = (Ai,Bi,Ci), 并計算∑n 2〈X,∑n i=1 Yi〉.3 Bob 知道自己的凸多邊形G 的面積, 即Q2.4 Alice 和Bob 分別選擇m 個隨機數(shù)ai,bi(i = 1,··· ,m) 并用各自的Paillier 加密算法的公鑰計算2∑ni=1〈X,Yi〉 = 1(Ci 1a,Ci2a) = (gaiQ1amod N2a,gaia mod N2a)(Ci 1b,Ci2b) = (gbiQ2bmod N2b,gbib mod N2b)1a,Ci2a), (Ci1b,Ci2b).5 借助分割-選擇方法, Alice 從m 組(Ci并分別公布(Ci 1b,Ci2b) 中任選m/2 組(Ci1b,Ci2b), 在Bob 公布biQ2 后, Alice 驗證gbiQ2 bmod N2b = Ci1b, 如驗證通過, 則繼續(xù)執(zhí)行協(xié)議, 否則中止協(xié)議.6 Bob 從m 組(Ci 1a,Ci2a) 中任選m/2 組(Ci1a,Ci2a), 在Alice 公布aiQ1 后, Bob 驗證gaiQ1 amod N2a =Ci 1a, 如果驗證通過, 則繼續(xù)執(zhí)行協(xié)議, 否則中止協(xié)議.1a,Ci2a) 和(Ci1b,Ci2b) 中隨機選擇一個(Cj1a,Cj2a) 和(Cj1b,Cj2b),并選取a ∈Z?b, b ∈Z?a.8 Alice 計算Cb = Eb(abj(Q1 ?Q2)) = (Cj 7 Alice 和Bob 分別從其余的m/2 組(Ci 2b)aQ1(Cj1b)?arNb1 mod N2b = gabj(Q1?Q2)b rNb 1 mod N2b, 并發(fā)送給Bob.9 Bob 計算Ca = Ea(aib(Q1 ?Q2)) = (Ci1a)(Ci2a)?bQ2rNa2 mod N2a = gaib(Q1?Q2)a rNa2 mod N2a, 并發(fā)送給Alice.10 Alice 用λa 計算ma = Cλaa mod N2a, Bob 用λb 計算mb = Cλbb mod N2b, 并公布ma, mb.11 雙方借助零知識證明來驗證計算的正確性, Alice 證明logCama = loggaμ, Bob 證明logCbmb = loggbν, 如其中一方不能通過證明, 則為惡意參與者.12 如證明通過, Bob 計算L(ma)/L(μ) 得aib(Q1 ?Q2), 繼而得到ai(Q1 ?Q2). 當(dāng)ai(Q1 ?Q2) = 0 時, 則Q1 ?Q2 = 0, 即Q1 = Q2, P0 ?G; 否則P0 ??G.13 Alice 計算L(mb)/L(ν) 得abj(Q1 ?Q2), 繼而得到bj(Q1 ?Q2). 當(dāng)bj(Q1 ?Q2) = 0 時, 則Q1 ?Q2 = 0, 即Q1 = Q2, P0 ?G; 否則P0 ??G.14 協(xié)議結(jié)束.

5.2 正確性分析

5.3 安全性證明

以下是用理想-實際范例來證明協(xié)議2 是安全的.

在協(xié)議2 中, Alice 和Bob 在第1–3 步中主要是為了保密求出Q1和Q2,Q1和Q2作為進一步執(zhí)行協(xié)議的輸入數(shù)據(jù), 這類似于理想模型下參與者的輸入信息, 若發(fā)給TTP 輸入信息有誤, 將無法繼續(xù)進行協(xié)議. 因此, 在惡意模型下也不會考慮輸入信息錯誤的情況, 即在證明中將判斷點與凸多邊形的包含關(guān)系問題轉(zhuǎn)化為這一問題, 因而我們以下將證明協(xié)議第4 步之后的安全性.

定理1協(xié)議2(記為Π) 在有惡意參與者的情況下是安全的.

證明:由定義1可知, 如果協(xié)議Π 要安全地計算時間函數(shù), 則需要雙方共同在實際協(xié)議中找到都認可的策略對ˉA=(A1,A2) 使得與理想模型下的協(xié)議中的策略對ˉB=(B1,B2) 不可區(qū)分, 即可證明協(xié)議的安全性.

為保證協(xié)議是安全可行的, 我們則必須保證至少一方是誠實的, 即: (1)A1是誠實的, 即A2是不誠實的; (2)A1是不誠實的, 即A2是誠實的.

首先證明第一種情況:A1是誠實的,A2是不誠實的.

當(dāng)A1是誠實的, 執(zhí)行協(xié)議Π, 則有:

其中O是A2借助零知識證明收到的序列消息.

當(dāng)A1是誠實的,A1會誠實的執(zhí)行協(xié)議, 這時B1也就確定下來了. 我們只需要證明實際協(xié)議中的A2與理想模型下的B2是不可區(qū)分的, 為此我們要在理想模型中找到一個策略對 ˉB= (B1,B2) 的輸出與實際模型下的REALΠ,ˉA(Q1,Q2) 是不可區(qū)分的. 值得注意的是, 在執(zhí)行協(xié)議的過程中,A2是實際的執(zhí)行者,因此在證明的過程中, 我們必須根據(jù)A2的行為, 即A2(Q2) 來驗證協(xié)議的正確性.

在模擬器B2執(zhí)行協(xié)議過程中, 我們可以得到:

證明第二種情況:A1是不誠實的,A2是誠實的. 存在以下有兩種情況:

(1) 當(dāng)Alice 收到信息不再理會TTP 時, TTP 給Bob 將會發(fā)送⊥, 那么:

(2) 反之, TTP 給Bob 發(fā)送信息F2(A1(Q1),Q2), 那么:

其中,O是A1借助零知識證明收到的序列消息.

當(dāng)A2是誠實的,A2會誠實執(zhí)行協(xié)議, 這時B2也就確定下來了. 我們只需要證明實際協(xié)議中的A1與理想模型下的B1是不可區(qū)分的, 為此我們要在理想模型中找到一個策略對 ˉB= (B1,B2) 的輸出與實際模型下的REALΠ,ˉA(Q1,Q2)是不可區(qū)分的. 值得注意的是, 在執(zhí)行協(xié)議的過程中,A1是實際的執(zhí)行者,因此在證明的過程中, 我們必須根據(jù)A1的行為, 即A1(Q1) 來驗證協(xié)議的正確性.

在模擬器B1執(zhí)行協(xié)議的過程中, 有以下兩種情況:

(1) 當(dāng)A1收到信息不再理會TTP 時, 得到:

(2) 反之, 得到

綜合以上兩種情況, 在理想模型中找到一個策略對 ˉB= (B1,B2) 的輸出與實際模型下的REALΠ,ˉA(Q1,Q2) 是不可區(qū)分的, 滿足定義1. 因此, 協(xié)議2 在惡意模型下是安全的.

6 性能分析

6.1 整體性能對比

本文設(shè)計了惡意模型下點與凸多邊形包含關(guān)系保密判定協(xié)議. 由于當(dāng)下保密判定點與凸多邊形包含關(guān)系的協(xié)議均是在半誠實模型下設(shè)計的, 而有些在惡意模型下的協(xié)議應(yīng)用場景與本協(xié)議不同將無法比較.以下是本文協(xié)議與相關(guān)協(xié)議的整體性能比較, 如表1 所示.

表1 整體性能比較Table 1 Overall performance comparison

6.2 計算復(fù)雜度與通信復(fù)雜度

6.2.1 計算復(fù)雜度

為比較協(xié)議的計算復(fù)雜度, 此時假設(shè)所有方案調(diào)用的是同一個內(nèi)積協(xié)議、同一個百萬富翁協(xié)議、同一個OTn1協(xié)議, 且假設(shè)所有的基礎(chǔ)協(xié)議各交互了3 輪. 本文在比較計算復(fù)雜度時, 將模乘運算作為衡量指標(biāo).

在文獻[8] 中, 調(diào)用了一次內(nèi)積協(xié)議, 則其總的計算復(fù)雜度為n; 文獻[9] 中的協(xié)議調(diào)用了6 次借助茫然點線關(guān)系協(xié)議, 而茫然點線關(guān)系協(xié)議調(diào)用了一次OTn1協(xié)議、兩次點積協(xié)議以及一次百萬富翁協(xié)議, 則其總的計算復(fù)雜度為6·2n+24n+12; 文獻[11] 采用ElGamal 加密系統(tǒng), 并利用比特承諾函數(shù), 使參與者要在上一個參與者之后要揭示剩余的承諾, 則其計算復(fù)雜度為mn+2(m+n); 文獻[12] 采用Paillier加密算法, 其計算復(fù)雜度為b1+b2+λ.

在本文協(xié)議2 中, 第1–3 步是分別計算各自的面積Q1、Q2, 并沒有采用任何加密算法, 因而其計算復(fù)雜度可以忽略不計; 第7–13 步已經(jīng)將問題轉(zhuǎn)化為SMP (socialist millionaires’ problem), 并調(diào)用了內(nèi)積協(xié)議, 因而其總的計算復(fù)雜度為2(λ+N)+n. 具體比較見表2.

6.2.2 通信復(fù)雜度

在文獻[8] 中, 進行了3 輪通信; 在文獻[9] 中, 雙方進行了12 輪通信; 在文獻[11] 中, 進行了2m輪協(xié)議, 其中m代表參與的人數(shù); 在文獻[12] 中, 進行了4 輪通信; 在協(xié)議2 中進行了6 輪通信. 具體比較見表2.

表2 協(xié)議效率比較Table 2 Efficiency comparison of protocols

如表2 所示, 對于解決相同問題的文獻[8], 計算復(fù)雜度比協(xié)議2 的計算復(fù)雜度稍好, 但不能抵抗惡意敵手的攻擊; 在文獻[9] 中調(diào)用了大量的基礎(chǔ)協(xié)議, 計算量大大增加, 因而協(xié)議2 的計算復(fù)雜度較好. 因此, 相比于半誠實模型下的文獻[8,9], 協(xié)議2 可以在保持高效的同時又可以抵抗惡意敵手攻擊. 文獻[11]和[12] 是在惡意模型下提出的協(xié)議, 其計算復(fù)雜度與參與者的輸入位數(shù)有關(guān), 且解決的問題、應(yīng)用場景與本文協(xié)議是不同的. 就安全兩方協(xié)議來說, 協(xié)議2 相比于其他的惡意模型下協(xié)議的效率要高.

值得注意的是, 惡意模型下的協(xié)議大多會借助分割-選擇、比特承若、零知識證明等工具. 對此, 我們可以采用預(yù)處理或者服務(wù)外包來提高協(xié)議效率.

7 結(jié)論

研究點與凸多邊形包含關(guān)系保密判定問題具有重要的應(yīng)用前景, 如軍事演習(xí)中一方軍隊想在另一方軍隊中演習(xí), 但又不能因演習(xí)泄漏基地位置信息, 因此需要保密的判斷演習(xí)地點是否在對方的范圍內(nèi); 公司兩方在不泄露具體商業(yè)位置時擴展業(yè)務(wù), 也需要秘密判斷其商務(wù)范圍等等. 現(xiàn)有的點與凸多邊形包含關(guān)系保密判定協(xié)議大多是基于半誠實模型提出的, 無法抵抗惡意敵手攻擊. 本文利用Paillier 加密算法、零知識證明和分割-選擇方法, 設(shè)計了惡意模型下點與凸多邊形包含問題判定協(xié)議, 避免了不公平性, 又可抵抗惡意敵手攻擊. 利用理想-實際范例證明了在惡意模型下該協(xié)議是安全的, 與現(xiàn)有協(xié)議相比更接近現(xiàn)實情況, 且保持高效, 具有實用價值.