隱私保護整數區間位置關系判定問題

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

（1.貴州師范學院數學與大數據學院，貴陽 550018；2.貴州師范學院網絡空間安全重點實驗室，貴陽 550018）

0 引言

安全多方計算技術常用來解決各種隱私保護科學計算問題，研究如何使互不信任的多個參與方在不借助任何第三方的情況下實現保護隱私的協同計算。只有兩個參與方的安全多方計算常稱為安全兩方計算，即參與方A1和A2分別擁有自己的秘密輸入x1和x2，在不借助任何第三方的情況下聯合計算某個二元函數（y1，y2）=f（x1，x2），協議結束后至少滿足兩個特性：1）正確性，即參與方Ai得到本方的正確輸出yi；2）安全性，即任何一方的輸入信息都未泄露給其他人。Yao 于1982年在文獻［1］中最先提出安全多方計算的思想。隨后，安全多方計算受到廣泛的研究，其中文獻［2-4］研究安全多方計算的可行性問題，即研究具體安全模型下安全多方計算協議的存在性問題，以及通用安全多方計算協議的構造問題，即構造能計算任意可計算函數的通用安全多方計算協議。一般而言，通用安全多方計算協議的執行效率不高，因此需要針對具體的安全多方計算問題研究個性化的解決方案。例如文獻［5］研究隱私保護線性代數計算問題，文獻［6］研究隱私保護脫氧核糖核酸（DeoxyriboNucleic Acid，DNA）序列漢明距離計算問題，文獻［7-9］研究百萬富翁問題等安全數值計算問題，文獻［8-10］研究安全多方量子計算問題，文獻［10-15］研究安全多方集合計算問題，文獻［16］在安全多方計算模型下研究基于多方數據集的隱私保護機器學習問題，文獻［17-19］研究保密區間計算問題。

本文提出一種新的安全兩方計算問題，即隱私保護整數區間位置關系判定問題，研究如何讓擁有整數區間的兩個用戶，在保護輸入隱私的前提下，準確地判斷出二者的整數區間的位置關系，其中整數區間是指左右端點都是整數，由區間的左右端點及介于它們之間的所有整數構成的集合。例如整數區間［3，6］表示集合｛3，4，5，6｝。整數區間的位置關系是指兩個整數區間在數軸上的位置的相對關系，本文將定義整數區間的6 種位置關系，在設計整數區間位置關系判定協議時，需要保證兩個參與方能夠正確地判斷出彼此持有的整數區間的位置關系屬于6 種關系中的哪一種，同時保證各自的區間信息未被泄露。

隱私保護整數區間位置關系判定問題有著重要的應用背景，下面是幾個例子：在商務上，利益方之間有時需要根據彼此的價格區間的位置關系來制定進一步的合作計劃，而各自的價格區間都是高度利益相關的，他們需要在隱私保護的前提下判斷出彼此價格區間的位置關系；爆發大規模的疫情可能會導致某類商品出現大幅的價格波動，不同的機構根據自有模型預測出不同的價格區間，在保護隱私的前提下判斷出這些價格區間的位置關系有助于相關問題的決策，且能保護各方的隱私；源于某種動機，Bob 需要判斷自己持有的某個時間區間［t1，t2］與Alice訪問某網絡服務的時間區間［T1，T2］（記錄保存在服務器S端）之間的位置關系，B和S在保護隱私的前提下判斷此位置關系，既解決了面臨的問題，又保護了各方的隱私。

文獻［17-20］在隱私保護區間計算方面作了一些研究，但主要研究元素是否屬于區間的判定問題。特別地，文獻［19］的部分工作和文獻［20］都研究了整數點是否屬于整數區間的隱私保護判定問題。目前尚未發現有關隱私保護區間位置關系判定問題的研究工作，而前人關于隱私保護區間計算方面的研究成果，尚不能直接擴展為解決該問題的方案，因此本文對隱私保護區間位置關系判定問題開展研究。

本文取得的主要工作如下：

1）定義了整數區間的6 種位置關系，并給出整數區間的一種0-1 編碼方案，然后證明了兩個整數區間位置關系的判定定理，從而將整數區間位置判定問題轉化為0-1 串之間的漢明重量比較問題。

2）在半誠實攻擊者模型［21］下，基于給出的判定規則，借助Goldwasser-Micali 加密體制［22］，主要是利用其異或同態性和概率加密特性，設計了一個整數區間位置關系判定協議，給出了基于模擬器的安全性證明，并對協議的性能進行了分析和說明。

1 知識準備

1.1 Goldwasser-Micali加密體制

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

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

未知私鑰（即未知大整數N的因數分解）時，模N的二次剩余問題是困難的，故解密是困難的；擁有私鑰（即知道N的因數分解）時，模N的二次剩余問題是容易的，故解密是容易的。該密碼系統具有如下特性。

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

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

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

在研究安全多方計算問題時，半誠實模型和惡意模型是考慮得最多的兩種攻擊者模型。文獻［21］基于比特承諾和零知識證明理論設計了一個編譯器，能夠將半誠實攻擊者模型下安全計算函數f的一個多方計算協議編譯成在惡意攻擊者模型下安全計算f的另一個多方協議。因此在處理具體的安全多方計算問題時，人們往往先探索半誠實攻擊者模型下的解決方案，再進一步構建惡意攻擊者模型下的解決方案。鑒于此，本文在半誠實攻擊者模型下研究隱私保護整數區間位置判定問題，惡意攻擊者模型下的研究工作作為下一步工作。

下面給出半誠實攻擊模型下的安全兩方計算模型［21］，它是本文協議安全性證明的理論根據。直觀地講，在半誠實攻擊模型下，假定協議的每個參與方都嚴格地遵循協議步驟，但允許它們記錄自己在執行協議過程中的中間信息，以此去推測對方的秘密輸入。令f：{0，1}*×{0，1}*→{0，1}*×{0，1}*，其中f(X，Y)=(f1(X，X)，f2(X，X))是一個二元概率多項式時間函數，記Π是計算f的一個兩方協議。兩個參與方P1和P2分別以X和Y為輸入，協議Π 執行結束后，參與方P1的，參與方P2的view為，其中ri表示Pi的內部隨機帶的輸出,表示Pi收到的第j條信息。記Pi的output為。對函數f=(f1，f2)，稱Π 是半誠實攻擊模型下計算f的安全兩方計算協議［21］，若存在概率多項式時間算法S1和S2，分別使得下面兩個關系式成立，其中表示隨機變量簇是計算不可區分的：

1.3 問題定義

設y1和y2（y1＜y2）是兩整數，整數區間[y1，y2]是指由y1和y2以及它們之間的所有整數構成的集合，即是集合{y1，y1+1，y1+2，…，y1+(y2-y1)}，含y2-y1+1 個 連 續整數。

定義1對點整數x和整數區間[y1，y2]，定義如下兩種位置關系，其中“?”表示充分必要條件（下同）：

1）（小于關系?）：x?[y1，y2]?x＜y1；

2）（大于關系?）：x?[y1，y2]?x＞y2。

從數軸上看，x?[y1，y2]相當于點x在區間[y1，y2]的左側，x?[y1，y2]相當于點x在區間[y1，y2]的右側。可見，點x和區間[y1，y2]共有x∈[y1，y2]，x?[y1，y2]和x?[y1，y2]三種可能的位置關系（如圖1所示）。

圖1 整數點和整數區間的三種位置關系Fig.1 Three relationships between integer and integer-interval

定義2定義整數區間[x1，x2]和[y1，y2]的如下6 種位置關系（如圖2所示），其中“∧”表示邏輯關系“與”：

圖2 整數區間的6種位置關系Fig.2 Six relationships between integer-intervals

需要強調的是關系[y1，y2]?[x1，x2]要求x1＜y1且y2＜x2，這不同于集合之間的真包含關系“?”。例如區間位置關系[3，5]?[3，7]并不成立，因為不滿足條件6），但作為集合關系{3，4，5}?{3，4，5，6，7}是成立的。從數軸上看，關系1）表示區間[x1，x2]在[y1，y2]的左側，二者沒有相交；關系2）表示[x1，x2]的右端點x2向右滑動滿足x2∈[y1，y2]，而左端點x1繼續保持位于[y1，y2]的左側；關系3）表示[x1，x2]的左端點x1向右滑動滿足x1∈[y1，y2]，而右端點x2繼續保持位于[y1，y2]的內部，即x2∈[y1，y2]；關系4）表示[x1，x2]的右端點x2繼續向右滑動至[y1，y2]的右側，而左端點x1繼續保持位于[y1，y2]的內部；關系5）表示[x1，x2]的左端點x1繼續向右滑動至[y1，y2]的右側，此時區間[x1，x2]在[y1，y2]的右側，二者沒有相交；而關系6）則表示[x1，x2]的左端點x1位于[y1，y2]的左側而右端點x2位于[y1，y2]的右側。

下文中，全集U={u1，u2，…，un}都指由某n個連續整數構成的公開集合，即形如{u1，u1+1，…，u1+(n-1)}?Z，這意味著ui＜uj?i＜j，即較小的下標對應較小的數值。例如集合U=｛1，2，3，4，5，6，7，8，9，10，11，12｝可作為全集。

定義3隱私保護整數區間位置判定問題。全集U={u1，u2，…，un}是由n個連續整數構成的公開集合，用戶Alice和Bob 分別擁有整數區間[x1，x2]?U和[y1，y2]?U，隱私保護整數區間位置判定問題即是在保證各自的區間信息不被泄露的情況下，Alice 和Bob 如何正確地判斷出整數區間[x1，x2]和[y1，y2]的位置關系，即屬于定義2中的何種情形。

2 編碼規則和判定定理

2.1 編碼規則

全集U={u1，u2，…，un}是由n個連續整數構成的集合，Alice 擁有整數區間[x1，x2]?U，Bob 擁有整數區間[y1，y2]?U。下面分別定義Alice 和Bob 的0-1 編碼規則，將區間[x1，x2]和[y1，y2]編碼成兩個n長的0-1串。

1）Alice 將區間[x1，x2]編碼成長度為n的兩個0-1編碼a=a1a2…an和d=d1d2…dn，滿足：

①若ui=x1則ai=1，否則ai=0；

②若ui=x2則di=1，否則di=0。

2）Bob 將區間[y1，y2]編碼成長度為n的兩個0-1 編碼b=b1b2…bn和c=c1c2…cn，滿足：

①若ui≥y1則bi=1，否則bi=0；

②若ui＞y2則ci=1，否則ci=0。

需要強調的是：在Bob構造0-1編碼c的過程中是用“＞”而不是“≥”。特別，當y2=un（即取全集U中的最大值）時，c=00…0。下面通過實例1對0-1編碼規則進行輔助說明。

實 例1 設U={1，2，3，4，5，6，7，8，9，10，11，12}，Alice和Bob 分別擁有區間[x1，x2]=[5，7]和[y1，y2]=[4，8]，Alice得到兩個0-1 串a=000010000000 和d=000000100000，Bob 得到兩個0-1串b=000111111111和c=000000001111。

2.2 判定定理

本節將根據上述0-1編碼規則，分別給出整數區間的6種位置關系的充分必要條件，這是本文協議的主要理論基礎。下面先通過引理1 給出整數點與整數區間3 種位置關系的充分必要條件，然后基于此，通過定理1 給出整數區間位置關系的充分必要條件。

定義4比特串s=s1s2…sm∈{0，1}m中所含“1”的個數稱為s的重量，記為N(s，1)，即N(s，1)=

例如：令s=001110010，則N(s，1)=4。

引理1全集U={u1，u2，…，un}是由n個連續整數構成的集合，對整數點x∈U和整數區間[y1，y2]?U，將它們分別按如下規則進行0-1 編碼，得到長度為n的0-1 串a=a1a2…an，b=b1b2…bn和c=c1c2…cn：1）若ui=x則ai=1，否則ai=0；2）若ui≥y1則bi=1，否則bi=0；若ui＞y2則ci=1，否則ci=0。則下列關系成立（其中“||”表 示0-1 串的級聯，如x=100，y=1100，則x||y=1001100）：

證明 由于a，b，c都是等長的，則下列等式成立：

先證明關系1）成立。假設x∈[y1，y2]，即y1≤x≤y2。故uk≤ui≤uj-1。根據全集U的定義規則，下標小意味著對應的數值也小，即k≤i≤j-1。可得N(b⊕a，1)-N(b，1)=-1和N(c⊕a，1)-N(b，1)=1。故有：

下面基于引理1，給出整數區間位置關系的判定定理。

定理1 判定定理。全集U是由n個連續整數構成的集合，整數區間[x1，x2]和[y1，y2]是U的兩個子區間。設a，b，c，d是區間[x1，x2]和[y1，y2]按如上0-1 編碼規則進行編碼后得到的四個0-1串，而a||a，d||d和b||c是按照0-1串的級聯得到的3個2n長的0-1串。記：

根據定理1 的結論，要判斷區間[x1，x2]和[y1，y2]的位置關系，只需求出數對(L1，L2)的值即可。在0-1 串a，b，c，d中，Bob擁有b和c，因此他能本地計算N(b||c，1)。由于

因此，如果能夠在保護隱私的前提下，讓Bob 得到N((b||c)⊕(a||a)，1)和N((b||c)⊕(d||d)，1)，他就能計算出數對(L1，L2)的值，從而獲知[x1，x2]和[y1，y2]的位置關系，然后把結果告知Alice。為此，由于Bob 擁有(b||c)，Alice 擁有a||a和d||d。自然的想法是雙方在保護隱私的情況下，執行一系列協議步驟讓Bob 得到N((b||c)⊕(a||a)，1)，然后再重復執行類似步驟，讓Bob 得到N((b||c)⊕(d||d)，1)。但這樣做帶來的問題是協議的輪復雜度較高，彼此收發消息的數量增加，會對協議的性能產生負面影響。因此，本文在設計協議時充分考慮到這一點，在保護隱私的前提下，讓Bob 一次性得到(L1，L2)的值，將協議的輪復雜度降低了一半。

下面通過實例2對定理1給出的判定規則進行輔助說明。

實例2 設U={1，2，3，4，5，6，7，8，9，10，11，12}，對兩個區間[x1，x2]=[3，7]和[y1，y2]=[6，10]，Alice 得到兩個0-1 串a=001000000000 和d=000000100000，Bob 得到兩個0-1 串b=000001111111和c=000000000011。易見N(b||c，1)=9。

因此(L1，L2)=(2，0)，從而可以斷定 [x1，x2]?=[y1，y2]，即[3，7]?=[6，10]，得到正確的判斷結果。

3 整數區間位置關系判定協議

3.1 協議描述

協議的構造主要基于Goldwasser-Micali 加密體制的異或同態性質：在公私鑰對不變的情況下，兩個明文比特m1和m2的密文E(m1)和E(m2)模N相乘，結果為m1⊕m2的密文，即E(m1)×E(m2)modN=E(m1⊕m2)，其中N是加 密 運算的模數。協議中還需要用到集合{1，2，…，2n}上的置換，其含義是該集合到自身的一一映射。在協議開始之前，Bob 生成自己的公私鑰對，并將公鑰告知Alice。協議中的加密都是指用Bob的公鑰進行加密，解密都是指用Bob的私鑰進行解密。另外，Alice 和Bob 根據實際情況事先約定一個全集U={u1，u2，…，un}，確保他們的秘密區間都是U的子集。

協議1 整數區間位置關系判定協議。

輸入：全集U={u1，u2，…，un}是由n個連續整數構成的公開集合，整數區間[x1，x2]?U是Alice 的秘密輸入，整數區間[y1，y2]?U是Bob的秘密輸入。

輸出：Alice 和Bob 都得知[x1，x2]和[y1，y2]的位置關系（即屬于定義2中的哪一種情況）。

Alice和Bob執行如下協議步驟：

1）Bob 按上述0-1 編碼規則將區間[y1，y2]編碼為n長的兩個0-1 編碼b=(b1，b2，…，bn)和c=(c1，c2，…，cn)，逐比特加密b||c后得到2n個密文E(b||c)，重復拼接一次后得到b||c||b||c的4n個密文：

將這4n個密文發送給Alice。

2）Alice 按上述0-1 編碼規則將[x1，x2]編碼成長度為n的兩個0-1 編碼a=a1a2…an和d=d1d2…dn，逐比特加密a后得到n個密文E(a)，逐比特加密d后得到n個密文E(d)。然后拼接成a||a||d||d的4n個密文：

Alice 將這4n個密文E(a||a||d||d)與Bob 傳來的4n個密文E(b||c||b||c)進行逐項對應模N相乘（異或同態運算），得到4n個密文：

Alice 秘密地獨立選取{1，2，…，2n}上的兩個隨機置換T1和T2，對這4n個密文的前2n個密文用T1進行隨機置換，后2n個密文用T2進行隨機置換，將置換后的4n個密文發送給Bob：

3.2 正確性和安全性分析

本節在半誠實攻擊者模型下給出協議1 的正確性和安全性證明，其中半誠實攻擊者模型假定協議的每個參與方都嚴格地遵循協議步驟，但允許它們記錄自己在執行協議過程中的中間信息，以此去推測對方的秘密輸入。在此模型假設下，定理2證明了執行完協議后參與方將輸出正確的結果，定理3證明執行完協議后參與方的隱私輸入數據未被泄露。

定理2正確性。在半誠實攻擊者模型下，協議1正確地判斷整數區間的位置關系。

證明 在半誠實模型下，Alice 和Bob 都嚴格遵循協議步驟。容易得到下面的關系：

4 效率分析與比較

本文首次提出并研究整數區間位置關系問題，故沒有前人的解決方案進行直接比較。考慮到文獻［19］的協議1（簡記Chen 協議）解決的是保密判斷一個整數點a是否屬于一個整數區間［x，y］的問題，該問題與本文的研究問題相對接近，本章將Chen協議與本文協議的性能進行比較。

整體上看（參見表1），二者的研究思路和技術手段相近，例如都基于Goldwasser-Micali（簡記為GM）加密體制，都用到了隨機置換思想，都只考慮半誠實攻擊者模型。但二者的研究問題并不相同，Chen 協議的輸出結果是a∈[x，y]或a?[x，y]，不能直接擴展來解決整數區間位置關系判定問題。

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

復雜度比較方面（參見表2），兩個協議的輪復雜度、Alice的加密次數和Bob 的加密次數都分別相同，但本文協議的通信復雜度和其他方面的計算復雜度大約是Chen 協議的兩倍。導致復雜度增加的主要原因是二者解決的問題不同，Chen 協議僅需對長度為2n的0-1 串進行操作，而本文協議需要對長度為4n的0-1串進行操作。

表2 復雜度對比Tab.2 Complexity comparison

對本文協議而言，從其復雜度情況可以看出，n越大意味著計算復雜度和通信復雜度都越高，其中n是全集U的勢（U所含元素個數），因此在滿足隱私保護要求的前提下，可以選擇勢n盡可能小的全集U。

5 結語

安全多方計算是當前密碼學界的研究熱點。本文提出并研究隱私保護整數區間位置關系判定問題，這是一類新的安全兩方計算問題，實際生活中的一些隱私保護問題可抽象為該問題。論文首先定義了整數區間的6 種位置關系，并構造了參與方的整數區間的一個0-1編碼方案，進而給出了6種區間位置關系的充分必要條件；其次以此充分必要條件為判定準則，基于Goldwasser-Micali 加密體制在半誠實攻擊者模型下設計了一個整數區間位置關系判定協議；最后證明了協議的正確性和安全性，并對協議的性能進行了說明。本文首次研究隱私保護整數區間位置關系判定問題，構建的解決方案的復雜度偏高，設計效率更優的解決方案有待進一步研究。