馬敏耀，吳 戀，劉 卓，徐 藝

（1.貴州師范學院數(shù)學與大數(shù)據(jù)學院，貴陽 550018；2.貴州師范學院網(wǎng)絡(luò)空間安全重點實驗室，貴陽 550018）

（*通信作者電子郵箱minyaoma2006@163.com）

0 引言

安全多方計算研究如何使互不信任的多個參與方在不借助任何第三方的情況下實現(xiàn)保護隱私的協(xié)同計算。安全多方計算技術(shù)常用來解決各種隱私保護科學計算問題。只含兩個參與方的安全多方計算稱為安全兩方計算，即參與方A1和A2分別擁有自己的秘密輸入x1和x2，在不借助任何第三方的情況下聯(lián)合計算某個二元函數(shù)（y1，y2）=f（x1，x2），協(xié)議結(jié)束后，參與方Ai得到本方的正確輸出yi（正確性）且任何一方的輸入都未泄露給其他人（安全性）。1982 年，姚期智在文獻［1］中最先提出安全多方計算的思想。隨后，文獻［2-4］研究安全多方計算的可行性問題，即具體安全模型下安全多方計算協(xié)議的存在性問題，以及構(gòu)造能夠計算任意可計算函數(shù)的通用安全多方計算協(xié)議。由于通用協(xié)議的執(zhí)行效率相對較低，因此大量的文獻研究具體安全多方計算問題的解決方案，例如：隱私保護線性代數(shù)計算［5］、隱私保護DNA 序列漢明距離計算［6］、安全數(shù)據(jù)比較［7-9］、安全多方量子計算［8-10］、安全多方集合計算［10-15］、隱私保護機器學習［16］、保密區(qū)間計算［17-19］等。

點和區(qū)間關(guān)系的保密判定問題，是指在保護雙方隱私的情況下，判斷一方持有的點是否包含在另一方持有的區(qū)間中。此問題在保護隱私的范圍查詢或定位搜索中有著非常廣泛的應(yīng)用。文獻［17-18］利用安全多方計算的思想研究了點和區(qū)間關(guān)系的隱私保護判定協(xié)議，并將數(shù)和區(qū)間放在有理數(shù)范圍內(nèi)考慮，文獻［19］將點和區(qū)間關(guān)系的隱私保護判定問題推廣到實數(shù)范圍內(nèi)。

文獻［19］同時研究了整數(shù)點和整數(shù)區(qū)間關(guān)系的保護判定問題：即在隱私保護的前提下，協(xié)議雙方如何判斷一個整數(shù)點是否屬于一個整數(shù)區(qū)間，其中整數(shù)區(qū)間［y1，y2］指的是從y1到y(tǒng)2的全部y2–y1+1個整數(shù)構(gòu)成的集合。該文定義了一種0-1編碼規(guī)則，基于此規(guī)則給出了整數(shù)點屬于整數(shù)區(qū)間的一個判定規(guī)則，以此判定規(guī)則為基礎(chǔ)，設(shè)計了一個解決方案。分析發(fā)現(xiàn)該文給出的判定規(guī)則存在缺陷，導致基于此判定規(guī)則設(shè)計的解決方案存在幾個主要缺陷：一是協(xié)議可能輸出錯誤的判定結(jié)果；二是協(xié)議可能導致整數(shù)點持有方的隱私泄露；三是協(xié)議的復(fù)雜度偏高。鑒于此，本文進一步研究隱私保護整數(shù)點和區(qū)間關(guān)系判定問題，主要工作如下：

1）定義新的0-1 編碼規(guī)則，基于此編碼規(guī)則，證明了整數(shù)點屬于整數(shù)區(qū)間的一個充分必要條件，進而給出整數(shù)點是否屬于整數(shù)區(qū)間的一個新的判定規(guī)則。

2）基于新的判定規(guī)則，以Goldwasser-Micali 加密體制［20］為主要密碼學工具，設(shè)計了整數(shù)點是否屬于整數(shù)區(qū)間的一個判定協(xié)議。

3）證明了提出的協(xié)議是正確的，即不會輸出錯誤的結(jié)果；證明了協(xié)議在半誠實攻擊者模型［21］下是安全的，即不會導致任何一方的隱私泄露；協(xié)議的復(fù)雜度在文獻［19］的基礎(chǔ)上整體降低了約一半。

1 知識準備

1.1 Goldwasser-Micali加密體制

N是正整數(shù)，定 義。稱是模N的二次剩余，若x2≡amodN對某個x∈ZN成立；否則稱a為模N的二次非剩余。判斷a是否是模N的二次剩余的問題稱為模N的二次剩余問題，當未知N的素因數(shù)分解時該問題是困難的，已知N的素因數(shù)分解時該問題是容易的。

對素數(shù)p和任意，x模p的勒讓德符號定義為：

設(shè)合數(shù)N的素因子（可重復(fù)）分解為N=p1p2…pk，則稱為x模N的雅可比符號，其中是x模pi的勒讓德符號。

Goldwasser-Micali 加密體制［20］是基于模N的二次剩余問題困難性的公鑰加密體制，其密鑰生成算法、加密算法和解密算法描述如下。

1）密鑰生成算法。隨機生成兩個大素數(shù)p和q，計算N=pq，選取模N的一個二次非剩余使其雅可比符號1。公鑰是pk=(δ，N)，私鑰是sk=(p，q)。

2）加密算法。對任意明文比特x∈{0，1}，選取秘密隨機數(shù)，計算密文Epk(x)=r2δxmodN。

在未知私鑰（即未知大整數(shù)N的因數(shù)分解）的情況下，模N的二次剩余問題是困難的，故解密是困難的；反之，已知私鑰（即知道N的因數(shù)分解）時，模N的二次剩余問題是容易的，故解密是容易的。該密碼系統(tǒng)具有如下特性。

1）概率加密特性：每次加密都有隨機數(shù)r參與運算。

2）異或同態(tài)性：Epk(x1)和Epk(x2)分別是x1和x2的密文，則(Epk(x1)?Epk(x2)) modN是x1⊕x2的密文，即(Epk(x1)?Epk(x2)) modN=Epk(x1⊕x2)。

1.2 半誠實攻擊模型下的安全兩方計算模型

記f：{0，1}*×{0，1}*→{0，1}*×{0，1}*是任意一個概率多項式時間二元函數(shù)，其中f(X，Y)=(f1(X，X)，f2(X，X))，記Π 是計算函數(shù)f的一個兩方協(xié)議。兩個參與方P1和P2分別以X和Y作為輸入，他們執(zhí)行結(jié)束協(xié)議Π 之后，參與方P1的view記為，參與方P2的view記為，其中ri表示Pi的內(nèi)部隨機帶的輸出，mij表示Pi收到的第j條信息，Pi的output記為。稱Π 是半誠實攻擊模型下計算二元函數(shù)f=(f1，f2)的安全兩方計算協(xié)議，如果存在概率多項式時間算法S1和S2，使得下面兩個關(guān)系式成立，其中≡c表示隨機變量簇是計算不可區(qū)分的：

1.3 整數(shù)點與整數(shù)區(qū)間屬于關(guān)系判定問題

符號約定 本文所指的全集U={x1，x2，…，xn}都是由n個連續(xù)整數(shù)構(gòu)成的集合，即xi=xi-1+1，2 ≤i≤n。整數(shù)區(qū)間[y1，y2]指由兩整數(shù)y1和y2之間的y2-y1+1個連續(xù)整數(shù)構(gòu)成的集合，即[y1，y2]={y1，y1+1，y1+2，…，y2}。例如全集U=｛1，2，3，4，5，6，7｝，整數(shù)區(qū)間［3，6］=｛3，4，5，6｝。用符號“||”表示兩個0-1 串的級聯(lián)，如x=100，y=1100，則x||y=1001100。用符號“?”表示等價關(guān)系“當且僅當”。

定義1設(shè)全集U={x1，x2，…，xn}是由n個連續(xù)整數(shù)構(gòu)成的公開集合，整數(shù)點與整數(shù)區(qū)間屬于關(guān)系判定問題被定義為：Alice 和Bob 分別擁有整數(shù)點x∈U和整數(shù)區(qū)間[y1，y2]?U，在保證各自的輸入信息不被泄露的情況下，Alice和Bob如何正確地判斷x∈[y1，y2]或x?[y1，y2]。

定義2比特串s=s1s2…sn∈{0，1}m中所含“1”的個數(shù)稱 為s的重量，記 為N(s，1)，即。例如若s=001110010，則N(s，1)=4。

2 已有工作回顧與分析

為了解決整數(shù)點與整數(shù)區(qū)間屬于關(guān)系判定問題，文獻［19］設(shè)計了一個協(xié)議（文獻［19］協(xié)議1）。下面先簡單回顧該文的判定規(guī)則，然后指出其判定規(guī)則存在缺陷。

編碼規(guī)則1［19］Alice 和Bob 根據(jù)自己的輸入按如下規(guī)則進行0-1編碼：

1）Alice 將點x編碼成長度為n的0-1 碼a=a1a2…an：若xi=x則ai=1；否則ai=0。

2）Bob 將區(qū)間[y1，y2]的左端點y1編碼成長度為n的0-1碼b=b1b2…bn：若xi≥y1則bi=1；否則bi=0。將右端點y2編碼為長度為n的0-1碼c=c1c2…cn：若xi≥y2則ci=1；否則ci=0。

該文基于此0-1編碼規(guī)則，得出如下判定規(guī)則。

判定規(guī)則1［19］若N((b||c)⊕(a||a)，1)=N(b||c，1)，則x∈[y1，y2]；否則x?[y1，y2]。即若(b||c)⊕(a||a)和b||c中“1”的個數(shù)相同，則x∈[y1，y2]；否則x?[y1，y2]。

基于此判定規(guī)則，該文設(shè)計了解決整數(shù)點與整數(shù)區(qū)間屬于關(guān)系判定問題的一個協(xié)議。然而，分析發(fā)現(xiàn)，基于判定規(guī)則1來設(shè)計協(xié)議，存在下面幾個主要缺陷：

1）會輸出錯誤結(jié)果。當x=y2時，應(yīng)該輸出x∈[y1，y2]，但按上述判定規(guī)則和該文的協(xié)議描述，最終將輸出x?[y1，y2]，即雙方將輸出錯誤的結(jié)果。

2）會導致Alice 的隱私泄露。當x?[y1，y2]時，Bob 能夠得到有關(guān)x的更多信息，即知道x＜y1或x＞y2。因為當x＜y1時，(b||c)⊕(a||a)中“1”的個數(shù)比b||c中“1”的個數(shù)大2；當x＞y2時，(b||c)⊕(a||a)中“1”的個數(shù)比b||c中“1”的個數(shù)少2。在該文的協(xié)議中，Bob 能夠準確地知道屬于哪一種情形，因此他能準確地判斷x＜y1或x＞y2。

3）復(fù)雜度偏高。因為需要對2n長的0-1 串（如b||c和a||a）進行操作，其中n是全集U所含元素個數(shù)，因此協(xié)議的復(fù)雜度將偏高。與此相比，本文提出的協(xié)議只對n長的0-1串進行操作，計算復(fù)雜度和通信復(fù)雜度降低約一半。

下面通過實例1和實例2分別對1）和2）進行輔助說明。

實例1 全集U=｛1，2，3，4，5，6，7｝，Alice擁有整數(shù)x=6，Bob 擁有整數(shù)區(qū)間[y1，y2]=[3，6]，正確結(jié)果應(yīng)該為x∈[y1，y2]。Alice 得到0-1 編碼a=0000010，Bob 得到0-1 編碼b=0011111和c=0000011。因此b||c=0011111||0000011且

可見(b||c)⊕(a||a)中“1”的個數(shù)為5，b||c中“1”的個數(shù)為7，即N((b||c)⊕(a||a)，1)≠N(b||c，1)，根據(jù)上述判定規(guī)則將輸出x?[y1，y2]的錯誤結(jié)果。

實例2 全集U=｛1，2，3，4，5，6，7｝，Alice擁有整數(shù)x=7，Bob 擁有整數(shù)區(qū)間[y1，y2]=[3，6]。Alice 得 到0-1 編 碼a=0000001，Bob 得到0-1 編碼b=0011111 和c=0000011。因此b||c=0011111||0000011且

可見(b||c)⊕(a||a)中“1”的個數(shù)為5，b||c中“1”的個數(shù)為7，即(b||c)⊕(a||a)中“1”的個數(shù)比b||c中“1”的個數(shù)少2，從而Bob得知x＞y2，特別，本例中Bob 完全得知x=7，Alice 的輸入完全泄露。

3 整數(shù)點與整數(shù)區(qū)間屬于關(guān)系判定協(xié)議

基于第2 章的分析，本章將重新研究整數(shù)點與整數(shù)區(qū)間屬于關(guān)系判定問題的解決方案。定義新的0-1 編碼規(guī)則，并給出新的判定規(guī)則，基于此規(guī)則在半誠實攻擊者模型下給出一個協(xié)議，并對協(xié)議的安全性給出基于模擬器的證明。

3.1 0-1編碼規(guī)則和判定規(guī)則

編碼規(guī)則2 Alice和Bob按如下規(guī)則進行0-1編碼：

1）整數(shù)x的編碼規(guī)則。Alice 將自己的整數(shù)x編碼成長度為n的0-1碼a=a1a2…an，滿足：若xi=x則ai=1，否則ai=0。

2）整數(shù)區(qū)間[y1，y2]的編碼規(guī)則。Bob 將自己的區(qū)間[y1，y2]編碼成長度為n的0-1 碼b=b1b2…bn，滿足：若y1≤xi≤y2則bi=1，否則bi=0。

下面給出實例3對新的0-1編碼規(guī)則進行輔助說明。

實例3 全集U=｛1，2，3，4，5，6，7｝，Alice擁有整數(shù)x=6，Bob 擁有整數(shù)區(qū)間[y1，y2]=[3，6]。則Alice 擁有0-1 編碼a=0000010，Bob擁有0-1編碼b=0011110。

根據(jù)如上定義的0-1 編碼規(guī)則，下面證明一個結(jié)論，本文將該結(jié)論用作判定整數(shù)點是否屬于整數(shù)區(qū)間的判定規(guī)則。

定理1全集U={x1，x2，…，xn}是由n個連續(xù)整數(shù)構(gòu)成的集合，對整數(shù)點x∈U和整數(shù)區(qū)間[y1，y2]?U，將x和[y1，y2]按編碼規(guī)則2進行編碼后得到0-1編碼a和b，則

即x∈[y1，y2]當且僅當b⊕a中所含“1”的個數(shù)比b中所含“1”的個數(shù)少1。進一步有

證明 令x=xi，由整數(shù)x的編碼規(guī)則知，即ai=1。令[y1，y2]=[xk，xj]，即y1=xk且y2=xj，由區(qū)間[y1，y2]的編碼規(guī)則可知。

假設(shè)x∈[y1，y2]，即y1≤x≤y2，有xk≤xi≤xj，故有k≤i≤j，因此bi=1。由ai=1可知ai⊕bi=0，故b⊕a中“1”的個數(shù)至少比b中“1”的個數(shù)少1。由于a中只有一個“1”，故b⊕a能且只能引起b中的1 比特變化，因此可得N(b⊕a，1)-N(b，1)=-1。反 之，若N(b⊕a，1)-N(b，1)=-1，則 由b=可斷定k≤i≤j，從而有xk≤xi≤xj，即y1≤x≤y2，因此x∈[y1，y2]。

綜上有x∈[y1，y2]?N(b⊕a，1)-N(b，1)=-1。類 似地，可證x?[y1，y2]?N(b⊕a，1)-N(b，1)=1。 證畢。

根據(jù)定理1的結(jié)論，得到如下判定規(guī)則。

判定規(guī)則 2 若N(b⊕a，1)-N(b，1)=-1，則x∈[y1，y2]；否則x?[y1，y2]。

由于定理1 的兩個結(jié)論都是充分必要條件，因此判定規(guī)則2 不存在判斷錯誤的情況。又由于N(b⊕a，1)-N(b，1)的值只有1 和-1 兩種情況，因此根據(jù)N(b⊕a，1)-N(b，1)的值只能得到x∈[y1，y2]或x?[y1，y2]，除此之外推不出x＜y1或x＞y2及其他額外信息。可見，判定規(guī)則2很好地避免了判定規(guī)則1 存在的缺陷。此外，在下文中會發(fā)現(xiàn)，本文基于判定規(guī)則2設(shè)計的協(xié)議也有較高的執(zhí)行效率。

下面給出實例4和實例5對判定規(guī)則進行輔助說明。

實例4 全集U=｛1，2，3，4，5，6，7｝，Alice擁有整數(shù)x=6，Bob 擁有整數(shù)區(qū)間[y1，y2]=[3，6]。則Alice 擁有0-1 編碼a=0000010，Bob 擁有0-1 編碼b=0011110。則b⊕a=0011100，故有N(b⊕a，1)-N(b，1)=-1，Alice 和Bob 得到正確的判斷結(jié)果x∈[y1，y2]。

實例5 全集U=｛1，2，3，4，5，6，7｝，Alice擁有整數(shù)x=2，Bob 擁有整數(shù)區(qū)間[y1，y2]=[3，6]。則Alice 擁有0-1 編碼a=0100000，Bob 擁有0-1 編碼b=0011110。則b⊕a=0111110，故有N(b⊕a，1)-N(b，1)=1，Alice 和Bob 得到正確的判斷結(jié)果x?[y1，y2]。

3.2 協(xié)議描述

本節(jié)構(gòu)造的協(xié)議基于Goldwasser-Micali 加密體制，主要利用其概率加密特性和異或同態(tài)性。在公私密鑰對不變的情況下，有E(m1)?E(m2) modN=E(m1⊕m2)，其中N是加密運算的模數(shù)。協(xié)議開始之前，Bob 生成自己的公私鑰對，并將公鑰告知Alice。下文中的加密E(?) 都是指用Bob 的公鑰進行加密，解密都是指用Bob的私鑰進行解密。

協(xié)議1 整數(shù)點和整數(shù)區(qū)間屬于關(guān)系判定協(xié)議。

輸入：全集U={x1，x2，…，xn}是由n個連續(xù)整數(shù)構(gòu)成的公開集合，用戶Alice 擁有一個整數(shù)x∈U，用戶Bob 擁有一個整數(shù)區(qū)間[y1，y2]?U。

輸出：Alice和Bob都輸出x∈[y1，y2]或x?[y1，y2]。

Alice和Bob執(zhí)行如下協(xié)議步驟：

1）Bob 按如上編碼規(guī)則2 將整數(shù)區(qū)間[y1，y2]編碼為n長的0-1編碼b=b1b2…bn，并逐比特加密b，得到n個密文E(b)=(E(b1)，E(b2)，…，E(bn))，將這n個密文發(fā)送給Alice。

2）Alice 按如上編碼規(guī)則2 將整數(shù)x編碼為n長的0-1 編碼a=a1a2…an，并逐比特加密a，得到n個密文E(a)=(E(a1)，E(a2)，…，E(an))。Alice 將這n個密文與Bob 傳來的n個密文E(b)的對應(yīng)項進行模N相乘，根據(jù)加密體制的異或同態(tài)性得到如下n個密文：

E(a⊕b)=(E(a1⊕b1)，E(a2⊕b2)，…，E(an⊕bn))

Alice 秘密選取{1，2，…，n}上的一個隨機置換T，對這n個密文進行隨機置換，將得到的如下n個密文發(fā)送給Bob：

3）Bob對收到的n個密文T(E(a⊕b))逐項解密后得到：

計 算D=N(T(a⊕b)，1)-N(b，1)，若D=-1，則x∈[y1，y2]，否則x?[y1，y2]。

4）Bob將結(jié)果告訴Alice。

3.3 正確性和安全性分析

協(xié)議1 的正確性由定理1 即可保證。由于T是{1，2，…，n}上的置換，因此T(a⊕b)中所含“1”的個數(shù)與a⊕b所含“1”的個數(shù)相同，即N(T(a⊕b)，1)=N(a⊕b，1)，由定理1可得：

故協(xié)議1是正確的。

下面證明協(xié)議1的安全性。

定理2在半誠實攻擊者模型下，協(xié)議1能夠安全地判斷整數(shù)點和整數(shù)區(qū)間的屬于關(guān)系。

證明 在半誠實模型下，Alice 和Bob 都嚴格遵循協(xié)議步驟，他們可能記錄自己在執(zhí)行協(xié)議過程中的中間信息，并嘗試去推測對方的秘密輸入。下面根據(jù)第1.2 節(jié)中定義的安全模型，證明協(xié)議的安全性。

根據(jù)協(xié)議1 的描述，有f1(X，Y)=f2(X，Y)=“x∈[y1，y2]”或“x?[y1，y2]”，即協(xié)議執(zhí)行結(jié)束后，Alice和Bob的輸出相同。下面只給出f1(X，Y)=f2(X，Y)=“x∈[y1，y2]”時的證明，類似地可給出f1(X，Y)=f2(X，Y)=“x?[y1，y2]”時的證明。

情形1 構(gòu)造模擬器S1，使得下式成立：

模擬器S1以(X，f1(X，Y))=(x，“x∈[y1，y2]”)為輸入，其中X=x，f1(X，Y)=“x∈[y1，y2]”，執(zhí)行如下步驟：

1）S1隨機選擇滿足。

2）S1將區(qū)間編碼成n長的0-1 碼：若則，否則。逐比特加密b*后得到n個密文。隨后S1輸出

其中R1是S1的內(nèi)部隨機帶的輸出。

此外，由協(xié)議描述可知協(xié)議執(zhí)行結(jié)束后Alice 的view為。其中(E(b1)，E(b2)，…，E(bn))和“x∈[y1，y2]”分別是Bob 在第1）步和第4）步發(fā)送給Alice 的信息，x是Alice 的輸入，r1是Alice的內(nèi)部隨機帶的輸出。

情形2 構(gòu)造模擬器S2，使得下式成立：

模擬器S2以(Y，f2(X，Y))=([y1，y2]，“x∈[y1，y2]”)為輸入，其中Y=[y1，y2]和f2(X，Y)=“x∈[y1，y2]”分別是Bob 的輸入和輸出，執(zhí)行如下步驟：

1）S2隨機選擇x*∈U滿足x*∈[y1，y2]。

2）S2將區(qū)間[y1，y2]編碼成n長的0-1 碼b=b1b2…bn：若y1≤xi≤y2則bi=1，否則bi=0。S2逐比特加密b后得到n個密文E(b)=(E(b1)，E(b2)，…，E(bn))。

3）S2將整數(shù)x*編碼為n長的0-1 碼：若xi=x*則，否則。逐比特加密a*后得到n個密文。S2將E(b)與E(a*)的對應(yīng)項進行模N相乘，根據(jù)加密體制的異或同態(tài)性，得到n個密文。S2隨機選取集合{1，2，…，n}上的一個置換T*，對E(a*⊕b)進行置換后得到：

隨后S2輸出

其中R2是S2的內(nèi)部隨機帶的輸出。

此外，由協(xié)議描述可知協(xié)議執(zhí)行結(jié)束后Bob的view為

其中(E(aT(1)⊕bT(1))，E(aT(2)⊕bT(2))，…，E(aT(n)⊕bT(n))) 是Alice在第2）步發(fā)送給Bob的信息，[y1，y2]是Bob的隱私輸入，r2是Bob的內(nèi)部隨機帶的輸出。

下面證明{S2(Y，f2(X，Y))}≡c{viewΠ2 (X，Y)}。首先，r2和R2分別是Bob 和S2的內(nèi)部隨機帶的輸出，有R2≡c r2。由于(E(a*1)，E(a*2)，…，E(a*n))與(E(a1)，E(a2)，…，E(an))的每個元素都是Goldwasser-Micali概率加密算法加密的結(jié)果，且T*和T是集合{1，2，…，n}上的隨機置換，從而有：

4 效率分析與比較

本章將本文協(xié)議與文獻［19］的協(xié)議1（簡記為Chen 協(xié)議［19］）進行比較。首先，從整體上看，Chen 協(xié)議可能會導致判斷錯誤，且可能會導致Alice 的隱私泄露，而本文協(xié)議克服了這些缺陷（如表1 所示）。其次，在協(xié)議復(fù)雜度方面，二者的輪復(fù)雜度相同，由于Chen 協(xié)議［19］對長度為2n的0-1 串進行操作，而本文協(xié)議只對長度為n的0-1 串進行處理，故本文協(xié)議的計算復(fù)雜度和通信復(fù)雜度分別降低約一半（如表2 所示，其中n是全集U的勢，N是加密運算的模數(shù)）。

表1 整體性能對比Tab.1 Overall performance comparison

表2 復(fù)雜度對比Tab.2 Complexity comparison

5 結(jié)語

安全多方計算是當前密碼學界研究的熱點問題，隱私保護整數(shù)點和整數(shù)區(qū)間屬于關(guān)系判斷問題是一類具體的安全多方計算問題，隱私保護查詢和搜索判斷等一些實際問題可抽象為該問題。前人已經(jīng)對此問題展開過研究，但已有的協(xié)議具有或多或少的不足，例如隱私保護的強度不夠、協(xié)議效率偏低，甚至可能輸出不正確結(jié)果等。得益于前人的研究基礎(chǔ)和研究思路，本文進一步研究隱私保護整數(shù)點和整數(shù)區(qū)間屬于關(guān)系判斷問題，提出了解決該問題的一個協(xié)議，并對協(xié)議的正確性和半誠實模型下的安全性進行了證明，確保協(xié)議不會出現(xiàn)判斷錯誤的情況，且在半誠實攻擊者模型下很好地保護了兩個參與者的數(shù)據(jù)隱私。與已有協(xié)議相比，本文協(xié)議在輪復(fù)雜度不變的情況下，計算復(fù)雜度和通信復(fù)雜度分別降低約一半。作為下一步的研究工作，可以繼續(xù)探索該問題的更高效的安全方案。