隱私保護(hù)整數(shù)點(diǎn)和區(qū)間關(guān)系判定問題

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

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

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

0 引言

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

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

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

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

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

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

1 知識(shí)準(zhǔn)備

1.1 Goldwasser-Micali加密體制

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

對(duì)素?cái)?shù)p和任意，x模p的勒讓德符號(hào)定義為：

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

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

1）密鑰生成算法。隨機(jī)生成兩個(gè)大素?cái)?shù)p和q，計(jì)算N=pq，選取模N的一個(gè)二次非剩余使其雅可比符號(hào)1。公鑰是pk=(δ，N)，私鑰是sk=(p，q)。

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

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

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

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 半誠實(shí)攻擊模型下的安全兩方計(jì)算模型

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

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

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

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

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

2 已有工作回顧與分析

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

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

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

2）Bob 將區(qū)間[y1，y2]的左端點(diǎn)y1編碼成長(zhǎng)度為n的0-1碼b=b1b2…bn：若xi≥y1則bi=1；否則bi=0。將右端點(diǎn)y2編碼為長(zhǎng)度為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”的個(gè)數(shù)相同，則x∈[y1，y2]；否則x?[y1，y2]。

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

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

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

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

下面通過實(shí)例1和實(shí)例2分別對(duì)1）和2）進(jìn)行輔助說明。

實(shí)例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”的個(gè)數(shù)為5，b||c中“1”的個(gè)數(shù)為7，即N((b||c)⊕(a||a)，1)≠N(b||c，1)，根據(jù)上述判定規(guī)則將輸出x?[y1，y2]的錯(cuò)誤結(jié)果。

實(shí)例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”的個(gè)數(shù)為5，b||c中“1”的個(gè)數(shù)為7，即(b||c)⊕(a||a)中“1”的個(gè)數(shù)比b||c中“1”的個(gè)數(shù)少2，從而Bob得知x＞y2，特別，本例中Bob 完全得知x=7，Alice 的輸入完全泄露。

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

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

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

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

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

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

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

實(shí)例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ī)則，下面證明一個(gè)結(jié)論，本文將該結(jié)論用作判定整數(shù)點(diǎn)是否屬于整數(shù)區(qū)間的判定規(guī)則。

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

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

證明 令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”的個(gè)數(shù)至少比b中“1”的個(gè)數(shù)少1。由于a中只有一個(gè)“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 的兩個(gè)結(jié)論都是充分必要條件，因此判定規(guī)則2 不存在判斷錯(cuò)誤的情況。又由于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 存在的缺陷。此外，在下文中會(huì)發(fā)現(xiàn)，本文基于判定規(guī)則2設(shè)計(jì)的協(xié)議也有較高的執(zhí)行效率。

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

實(shí)例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]。

實(shí)例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)性。在公私密鑰對(duì)不變的情況下，有E(m1)?E(m2) modN=E(m1⊕m2)，其中N是加密運(yùn)算的模數(shù)。協(xié)議開始之前，Bob 生成自己的公私鑰對(duì)，并將公鑰告知Alice。下文中的加密E(?) 都是指用Bob 的公鑰進(jìn)行加密，解密都是指用Bob的私鑰進(jìn)行解密。

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

輸入：全集U={x1，x2，…，xn}是由n個(gè)連續(xù)整數(shù)構(gòu)成的公開集合，用戶Alice 擁有一個(gè)整數(shù)x∈U，用戶Bob 擁有一個(gè)整數(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長(zhǎng)的0-1編碼b=b1b2…bn，并逐比特加密b，得到n個(gè)密文E(b)=(E(b1)，E(b2)，…，E(bn))，將這n個(gè)密文發(fā)送給Alice。

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

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

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

3）Bob對(duì)收到的n個(gè)密文T(E(a⊕b))逐項(xiàng)解密后得到：

計(jì) 算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”的個(gè)數(shù)與a⊕b所含“1”的個(gè)數(shù)相同，即N(T(a⊕b)，1)=N(a⊕b，1)，由定理1可得：

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

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

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

證明 在半誠實(shí)模型下，Alice 和Bob 都嚴(yán)格遵循協(xié)議步驟，他們可能記錄自己在執(zhí)行協(xié)議過程中的中間信息，并嘗試去推測(cè)對(duì)方的秘密輸入。下面根據(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]”時(shí)的證明，類似地可給出f1(X，Y)=f2(X，Y)=“x?[y1，y2]”時(shí)的證明。

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

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

1）S1隨機(jī)選擇滿足。

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

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

此外，由協(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)部隨機(jī)帶的輸出。

情形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隨機(jī)選擇x*∈U滿足x*∈[y1，y2]。

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

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

隨后S2輸出

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

此外，由協(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)部隨機(jī)帶的輸出。

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

4 效率分析與比較

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

表1 整體性能對(duì)比Tab.1 Overall performance comparison

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

5 結(jié)語

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