劉旭紅，孫晨

（上海體育學(xué)院經(jīng)濟(jì)管理學(xué)院，上海 200438）

0 引言

安全多方計(jì)算（SMC，secure multiparty computation）是關(guān)于一組互不信任的參與者在保護(hù)各自隱私數(shù)據(jù)的前提下進(jìn)行協(xié)同計(jì)算的問(wèn)題，SMC要確保各參與者輸入數(shù)據(jù)的私密性以及計(jì)算結(jié)果的正確性。隨著信息時(shí)代數(shù)據(jù)安全性越來(lái)越受到重視，安全多方計(jì)算成為國(guó)際密碼學(xué)界的研究熱點(diǎn)。

圖靈獎(jiǎng)獲得者姚期智教授在文獻(xiàn)[1]中首次提出安全多方計(jì)算問(wèn)題，并引起國(guó)際密碼學(xué)界的重視[2-3]，Goldreich等[4,5]對(duì)其進(jìn)行了深入的研究，從理論上證明了任意的安全多方計(jì)算問(wèn)題都是可解的，并給出了通用的解決方案。由于通用解決方案的效率很低，利用通用方案解決具體的計(jì)算問(wèn)題一般是不可行的，考慮到實(shí)際應(yīng)用場(chǎng)景和計(jì)算效率與通信效率的問(wèn)題，需要針對(duì)具體問(wèn)題研究具體的解決方案?；谏鲜鰧W(xué)者的研究理論，許多密碼學(xué)研究人員不斷提出新的具有實(shí)際應(yīng)用前景的安全多方計(jì)算問(wèn)題及其解決方案，推進(jìn)了安全多方計(jì)算研究的發(fā)展。目前所研究的問(wèn)題有保密信息比較[6-7]、保密數(shù)據(jù)挖掘[8-9]、保密幾何計(jì)算[10-11]、保密數(shù)據(jù)查詢[12-13]等。

保密比較相等問(wèn)題和保密集合計(jì)算問(wèn)題是基本的安全多方計(jì)算問(wèn)題，保密比較相等問(wèn)題是保密信息比較中重要的基礎(chǔ)問(wèn)題并得到了廣泛的研究[14-18]，其對(duì)集合問(wèn)題的保密計(jì)算具有重要的基礎(chǔ)作用。集合問(wèn)題在保密數(shù)據(jù)挖掘、保密統(tǒng)計(jì)分析、保密幾何計(jì)算等方面有重要的應(yīng)用，其中保密判定元素與集合的關(guān)系[19-21]是集合保密計(jì)算中的基本問(wèn)題。文獻(xiàn)[14,15]基于第三方參與者設(shè)計(jì)了整數(shù)集上的保密比較相等協(xié)議，計(jì)算復(fù)雜性較高。文獻(xiàn)[16]提出了一個(gè)有理數(shù)閾值密碼系統(tǒng)，基于所提出的門(mén)限方案，構(gòu)造了分布式有理數(shù)相等測(cè)試協(xié)議，協(xié)議中需要多個(gè)參與者共同參與保密判定兩個(gè)有理數(shù)的相等問(wèn)題，且計(jì)算復(fù)雜性較高。文獻(xiàn)[17]利用單項(xiàng)哈希函數(shù)解決了兩個(gè)整數(shù)相等問(wèn)題和整數(shù)向量相等問(wèn)題，計(jì)算效率較高，但無(wú)法抵抗窮舉攻擊。文獻(xiàn)[18]利用Paillier公鑰加密算法解決了有理數(shù)相等問(wèn)題，相比文獻(xiàn)[16]計(jì)算效率有所提高。文獻(xiàn)[19]應(yīng)用不經(jīng)意多項(xiàng)式計(jì)算設(shè)計(jì)了整數(shù)集上元素與集合關(guān)系的保密判定協(xié)議，該方案借助于Paillier公鑰加密體制，計(jì)算復(fù)雜性較高。文獻(xiàn)[20]利用對(duì)稱加密體制和異或運(yùn)算設(shè)計(jì)了高效的整數(shù)集上元素與集合關(guān)系的保密判定協(xié)議，但泄露了集合元素的取值范圍，具有一定的局限性。文獻(xiàn)[21]應(yīng)用Paillier加密算法首次解決了有理數(shù)域上元素與集合關(guān)系問(wèn)題。

上述相關(guān)工作為研究更高效更廣泛的安全多方計(jì)算奠定了基礎(chǔ)，根據(jù)現(xiàn)有相關(guān)問(wèn)題的多個(gè)解決方案，分析每個(gè)解決方案的優(yōu)缺點(diǎn)，可以進(jìn)一步設(shè)計(jì)更加安全高效且適用范圍更廣的解決方案。已有的關(guān)于保密比較相等問(wèn)題和保密計(jì)算集合問(wèn)題的研究大多局限于整數(shù)范圍，現(xiàn)有的有理數(shù)域上的解決方案計(jì)算效率低，且無(wú)法應(yīng)用于實(shí)際中有理數(shù)域上相關(guān)問(wèn)題的保密計(jì)算，限制了相等問(wèn)題和集合問(wèn)題的實(shí)際應(yīng)用場(chǎng)景。

有理數(shù)不僅在現(xiàn)實(shí)生活中有廣泛的應(yīng)用，在生物學(xué)、氣候?qū)W、化學(xué)等領(lǐng)域中的應(yīng)用更為廣泛，尤其這些領(lǐng)域的研究工作講究準(zhǔn)確性，無(wú)誤差性。例如，在醫(yī)療保健方面，不僅需要準(zhǔn)確診斷病人的健康情況，而且需要確保病人的健康狀況和其他個(gè)人信息的安全性。由于大多數(shù)醫(yī)療數(shù)據(jù)（如血糖、胰島素和c肽水平）是有理數(shù)[22]，而傳統(tǒng)的密碼系統(tǒng)只能加密整數(shù)，這將影響數(shù)據(jù)的準(zhǔn)確性以及計(jì)算效率，從而影響決策和導(dǎo)致錯(cuò)誤診斷?；谏鲜鱿嚓P(guān)問(wèn)題，文獻(xiàn)[23]提出了允許用戶將有理數(shù)外包給云服務(wù)器進(jìn)行存儲(chǔ)和處理的一種新的高效隱私保護(hù)外包計(jì)算框架，為繼續(xù)研究有理數(shù)域上安全多方計(jì)算問(wèn)題提供了研究背景和意義。

在計(jì)算幾何方面，有理數(shù)的應(yīng)用也較廣泛[24-25]，舉例如下。① Alice擁有一條直線l1:y=k1x+b1，Bob擁有一條直線l2:y=k2x+b2，Alice和Bob希望保密判定兩條直線是否相交，則只需保密判定兩條直線的斜率k1和k2是否相等，即保密判定兩個(gè)有理數(shù)是否相等。② 在多邊形相似的保密判定問(wèn)題中，需要保密判定對(duì)應(yīng)邊是否成比例，通過(guò)歸一化可以將問(wèn)題轉(zhuǎn)化為保密判定有理向量相等問(wèn)題。③ 隨著計(jì)算機(jī)網(wǎng)絡(luò)的迅速發(fā)展，坐標(biāo)定位在多個(gè)行業(yè)中的應(yīng)用越來(lái)越普遍（偵查活動(dòng)、手機(jī)App等）。假設(shè)在某項(xiàng)偵查活動(dòng)中，Alice鎖定了多個(gè)位置點(diǎn)，記為點(diǎn)集合U；Bob所在的位置坐標(biāo)記為點(diǎn)u，Alice和Bob想要保密判定點(diǎn)u是否屬于集合U，即保密判定二維空間的元素與集合關(guān)系。

上述相關(guān)問(wèn)題中，多個(gè)研究對(duì)象需要用有理數(shù)或有理數(shù)集合進(jìn)行描述，從而將問(wèn)題抽象為有理數(shù)域上的安全多方計(jì)算問(wèn)題。根據(jù)現(xiàn)有的安全多方計(jì)算協(xié)議，由于加密體制的限制，往往需要將計(jì)算幾何問(wèn)題轉(zhuǎn)化到正整數(shù)集合上進(jìn)行研究，導(dǎo)致計(jì)算復(fù)雜性高、適用性差。研究有理數(shù)域上的安全多方計(jì)算問(wèn)題，通過(guò)有理數(shù)或有理數(shù)集合直接解決遇到的問(wèn)題，或?yàn)榻鉀Q問(wèn)題提供新的途徑，對(duì)安全多方計(jì)算的研究具有重要意義。

本文主要研究構(gòu)造有理數(shù)域上相等問(wèn)題和集合問(wèn)題的保密計(jì)算協(xié)議，是有理數(shù)域上安全多方計(jì)算研究的基礎(chǔ)。

本文的貢獻(xiàn)如下。

1）利用有理數(shù)的分?jǐn)?shù)表示形式，設(shè)計(jì)了關(guān)于有理數(shù)的一種全新的編碼方法。該編碼方案將任意有理數(shù)（數(shù)組）編碼為整數(shù)，為有理數(shù)與整數(shù)之間的轉(zhuǎn)換提供了一種新的思路。

2）將新的編碼方案與單向哈希函數(shù)相結(jié)合，解決了有理數(shù)域上的相等問(wèn)題和集合問(wèn)題。

3）協(xié)議計(jì)算效率高，且適用范圍廣（整數(shù)集合和有理數(shù)集合均適用），可用于解決更多安全多方計(jì)算問(wèn)題。

4）通過(guò)實(shí)例說(shuō)明對(duì)于所設(shè)計(jì)的協(xié)議進(jìn)行適當(dāng)修改或推廣應(yīng)用，對(duì)更多的安全多方計(jì)算問(wèn)題或?qū)嶋H應(yīng)用問(wèn)題可設(shè)計(jì)構(gòu)造安全高效的解決方案。

1 預(yù)備知識(shí)

本節(jié)主要介紹下文研究中所需要的一些基本概念和基礎(chǔ)知識(shí)[5]。

1.1 基本定義

（1）雙方計(jì)算

雙方計(jì)算是一個(gè)將任意給定的輸入對(duì)映射為輸出對(duì)的隨機(jī)過(guò)程, 這個(gè)過(guò)程用函數(shù)表示為f:(x,y)→(f1(x,y),f2(x,y))。即對(duì)于每一個(gè)輸入對(duì)(x,y)，輸出對(duì)是隨機(jī)變量(f1(x,y),f2(x,y))。記這樣的函數(shù)為f=(f1,f2)。

（2）半誠(chéng)實(shí)模型

安全多方保密計(jì)算問(wèn)題的初期研究基本上是以半誠(chéng)實(shí)模型為基礎(chǔ)的。半誠(chéng)實(shí)參與者是指在協(xié)議執(zhí)行過(guò)程中按照協(xié)議要求忠實(shí)地履行協(xié)議的參與者，不會(huì)欺騙和泄露信息，但是會(huì)收集和保留在協(xié)議執(zhí)行過(guò)程中獲得的所有信息，在協(xié)議執(zhí)行后試圖根據(jù)這些信息推算出額外的信息。如果所有參與者均為半誠(chéng)實(shí)參與者，這樣的計(jì)算模型稱為半誠(chéng)實(shí)模型。由于半誠(chéng)實(shí)參與者不對(duì)協(xié)議實(shí)施主動(dòng)攻擊，所以半誠(chéng)實(shí)模型又稱為誠(chéng)實(shí)但好奇（honest-but-curious）模型或被動(dòng)模型。文獻(xiàn)[5]給出了一個(gè)由半誠(chéng)實(shí)模型下安全協(xié)議直接編譯獲得惡意模型下安全協(xié)議的一般方法，因此半誠(chéng)實(shí)模型下安全計(jì)算協(xié)議的設(shè)計(jì)是基本而重要的。本文主要研究半誠(chéng)實(shí)模型下的兩方計(jì)算問(wèn)題。

（3）模擬范例方法

模擬范例方法是由Goldreich提出的，在安全多方計(jì)算協(xié)議安全性證明中廣泛使用的證明方法，其證明原理為：如果每個(gè)參與者在實(shí)際執(zhí)行協(xié)議過(guò)程中所獲得的信息都可以通過(guò)自己的輸入和輸出進(jìn)行模擬，而且模擬所得到的消息序列與實(shí)際執(zhí)行過(guò)程得到的消息序列計(jì)算不可區(qū)分，就說(shuō)明協(xié)議是安全的。如果一個(gè)多方計(jì)算協(xié)議能夠進(jìn)行這樣的模擬，即說(shuō)明所有參與者都不可能從協(xié)議的執(zhí)行過(guò)程中得到其他參與者任何有價(jià)值的信息。這種證明安全性的方法是研究安全多方計(jì)算問(wèn)題時(shí)普遍接受的模擬范例方法。模擬范例方法的具體描述如下。

假設(shè)參與雙方計(jì)算的參與者為P1和P2，則

① 設(shè)f=(f1,f2)是一個(gè)概率多項(xiàng)式時(shí)間函數(shù)，π表示計(jì)算函數(shù)f的一個(gè)雙方協(xié)議；

② 當(dāng)輸入為(x,y)時(shí)，在執(zhí)行協(xié)議π的過(guò)程中Pi(i=1,2)的view信息序列記為

其中，ri表示參與者Pi產(chǎn)生的隨機(jī)數(shù)，表示Pi收到的第j個(gè)消息；

③ 執(zhí)行協(xié)議后，參與者Pi(i=1,2)獲得的輸出結(jié)果記為。

定義1半誠(chéng)實(shí)模型下協(xié)議的安全性。對(duì)于上述函數(shù)f和協(xié)議π，如果存在概率多項(xiàng)式時(shí)間算法S1和S2，使

成立，則協(xié)議π保密地計(jì)算f，其中表示計(jì)算上不可區(qū)分。

要證明一個(gè)多方計(jì)算方案是安全的，就必須構(gòu)造滿足式(1)和式(2)的模擬器S1和S2。

1.2 字母表與連接運(yùn)算

字母表是對(duì)象的有窮非空集合M，M中符號(hào)的n元組稱作M上的字或字符串，M中所有字符串的全體記作M?。例如，所有的自然數(shù)都是字母表{0,1,2,…,9}上的字符串，所有的二進(jìn)制數(shù)都是字母表{0,1}上的字符串，字符串的連接定義如下。

其中，z=。對(duì)于給定的字符串u1,…,um∈M?,就是把字符串u1,…,um一個(gè)接著一個(gè)放在一起所得到的新的字符串。

1.3 單向哈希函數(shù)的性質(zhì)

單向哈希函數(shù)（簡(jiǎn)稱為Hash函數(shù)）是密碼體制中一類常用的公開(kāi)函數(shù)，該函數(shù)將任意長(zhǎng)度的消息映射成某一固定長(zhǎng)度消息。它具有如下性質(zhì)。

1) 給定消息m，很容易計(jì)算h=Hash(m)。

2) 給定h=Hash(m)，根據(jù)h計(jì)算其逆m=Hash?1(h)是困難的。

3) 給定m，要找一個(gè)消息m′，使Hash(m)=Hash(m′)是困難的。

4) 找出兩個(gè)隨機(jī)的消息m,m′，使Hash(m)=Hash(m′)是困難的。

5) 如果對(duì)m做微小的改變，即使只改變一個(gè)比特，變?yōu)閙′，Hash(m)的值與Hash(m′)的值相比也會(huì)發(fā)生驚人的變化，至少改變一半位數(shù)的值。

進(jìn)一步，根據(jù)單向哈希函數(shù)的性質(zhì)可知，Hash(a)=Hash(b)但a≠b的概率為1/2|Hash()|。例如，在SHA-1算法中|Hash()|=160，如果利用SHA-1算法做單向哈希函數(shù)，Hash(a)=Hash(b)但a≠b的概率為1/2160。在一般應(yīng)用中，如此小的出錯(cuò)概率是可以忽略不計(jì)的。

Hash函數(shù)具有上述特性，所以常被用于消息的完整性檢測(cè)和消息認(rèn)證。

2 編碼方案

本節(jié)設(shè)計(jì)一種有理數(shù)的編碼方法，以此方法，任一有理數(shù)（或有理向量）與一個(gè)十進(jìn)制整數(shù)相對(duì)應(yīng)。

2.1 有理數(shù)的編碼

（1）有理數(shù)的編碼方式

① 有理數(shù)的分?jǐn)?shù)表示

對(duì)任一有理數(shù)w，首先按如下方式將其表示為唯一的分?jǐn)?shù)形式（其中w1≥0,w2≥1 均為整數(shù)，s為符號(hào)位）。當(dāng)0w≠時(shí)，要求12,ww互素，當(dāng)w=0時(shí)，約定w1=0,w2=1；當(dāng)w≥0時(shí)，約定=1s，當(dāng)<0w時(shí)約定=2s。

② 有理數(shù)的向量表示

③ 有理數(shù)的編碼表示

根據(jù)②中的方式，可以將w表示成向量V(w)。若將V(w)的分量s,看作字母表{0,1,2,,9}…上的字符串，進(jìn)一步應(yīng)用連接運(yùn)算得到一個(gè)長(zhǎng)度為21k+的新的字符串，并記為W，顯然W亦可看作一個(gè)正整數(shù)，稱其為w的編碼整數(shù)。例如，w1=2/3對(duì)應(yīng)編碼整數(shù)W1=123,w2=23對(duì)應(yīng)編碼整數(shù)W2=12301,w3=?0.048對(duì)應(yīng)于編碼整數(shù)W3=2006125。

（2）有理數(shù)編碼方案的對(duì)應(yīng)關(guān)系

設(shè)一個(gè)映射BM:Q→，其中Q為有理數(shù)集合，為編碼整數(shù)集合（由集合Q中的有理數(shù)通過(guò)有理數(shù)編碼方案得到的編碼整數(shù)集合）。BM是一個(gè)雙射，即有理數(shù)集合Q與編碼整數(shù)集合是一一對(duì)應(yīng)的。

綜上所述，映射BM是雙射，利用上述有理數(shù)編碼方式得到的編碼整數(shù)集合與有理數(shù)集合Q是一一對(duì)應(yīng)的，即任一有理數(shù)存在唯一與之對(duì)應(yīng)的編碼整數(shù)。因此，兩個(gè)有理數(shù),xy相等當(dāng)且僅當(dāng)它們的編碼整數(shù)相等。為敘述方便，下文中將這種編碼方案簡(jiǎn)記為BMF。

2.2 有理向量的編碼

（1）有理向量的編碼方式

（2）有理向量編碼方案的對(duì)應(yīng)關(guān)系

根據(jù)上述有理向量的編碼過(guò)程可知，有理向量的編碼方案是以有理數(shù)編碼方案BMF為基礎(chǔ)的，類似于有理數(shù)編碼方案的對(duì)應(yīng)關(guān)系，當(dāng)向量位數(shù)n確定時(shí)，按照上述有理向量編碼方案得到的編碼整數(shù)存在唯一與之對(duì)應(yīng)的n維有理向量。n維有理向量和正整數(shù)形成一一對(duì)應(yīng)關(guān)系，稱為有理向量的編碼整數(shù)，記該編碼方案為VBMF。

下文中有理數(shù)組的編碼方法與有理向量的編碼方法類似，在此不再重復(fù)敘述。

3 相等問(wèn)題的保密判定方案

本節(jié)主要應(yīng)用單向哈希函數(shù)和上節(jié)所介紹的編碼方案設(shè)計(jì)有理數(shù)相等問(wèn)題（REq，rational number equality problem）以及有理向量相等問(wèn)題（RVEq，rational number vector equality problem）的保密判定協(xié)議。本文涉及的隨機(jī)數(shù)均為非零隨機(jī)數(shù)。

3.1 有理數(shù)相等問(wèn)題

問(wèn)題描述Alice有一個(gè)有理數(shù)x，Bob有一個(gè)有理數(shù)y，他們想保密判定兩個(gè)有理數(shù)是否相等，不泄露雙方的任何信息。

基本思想按照前面所述的BMF編碼方案，任意有理數(shù)w與一個(gè)編碼整數(shù)W形成一一對(duì)應(yīng)關(guān)系。如果有理數(shù)x,y對(duì)應(yīng)的編碼整數(shù)分別為X,Y，則，兩個(gè)有理數(shù)相等的保密判定問(wèn)題轉(zhuǎn)化為兩個(gè)整數(shù)相等的保密判定問(wèn)題。

下面將結(jié)合編碼方案BMF與單向哈希函數(shù)設(shè)計(jì)有理數(shù)相等問(wèn)題的保密判定方案，為敘述方便，定義二元謂詞。

具體協(xié)議如下。

協(xié)議1有理數(shù)相等保密判定協(xié)議

輸入Alice輸入有理數(shù)x，Bob輸入有理數(shù)y

輸出P(x,y)

準(zhǔn)備Alice和Bob共同商定一個(gè)單向哈希函數(shù)Hash()

1) Alice和Bob分別隨機(jī)選取足夠大的有理數(shù)r和t，計(jì)算x1=x+r和y1=y+t，并將結(jié)果發(fā)送給對(duì)方。

2) Alice和Bob執(zhí)行以下操作：

a) Alice計(jì)算y2=y1+r，Bob計(jì)算x2=x1+t；

b) 利用BMF編碼方案，Alice和Bob分別把有理數(shù)y2和x2編碼為十進(jìn)制正整數(shù)Y2=BM(y2)和X2=BM(x2)；

c) Alice和Bob分別計(jì)算h1=Hash(Y2)和h2=Hash(X2)，并將結(jié)果發(fā)給對(duì)方。

3) Alice和Bob各自比較h1與h2。如果h1=h2，則輸出P(x,y)=1；否則，輸出P(x,y)=0。

協(xié)議1的正確性

證明。首先，由協(xié)議可知x2=x1+t=x+r+t,y2=y1+r=y+t+r。

根據(jù)BMF編碼方案可知，X2與x2一一對(duì)應(yīng)，Y2與y2一一對(duì)應(yīng)，則。

協(xié)議1的安全性關(guān)于協(xié)議1的安全性，將從以下兩部分分別進(jìn)行詳細(xì)的分析證明：① 安全性分析，包括理論分析和抵抗窮舉攻擊分析；② 安全性證明，對(duì)第①部分的理論證明。

安全性分析：根據(jù)協(xié)議1可知，Alice和Bob私有數(shù)據(jù)的安全性分析類似，故在此僅對(duì)Alice的私有數(shù)據(jù)進(jìn)行安全性分析。

首先，在協(xié)議中Bob得到Alice發(fā)送的兩個(gè)關(guān)系式

由于上面兩個(gè)關(guān)系式含有兩個(gè)未知數(shù)x和r，Bob只能設(shè)法從h1=Hash(BM(y+t+r))中解出r，再代入x1=x+r獲得x；或Bob試圖根據(jù)h1=Hash(BM(y+t+x1?x))直接求出x值。根據(jù)Hash函數(shù)性質(zhì)，Bob想由h1=Hash(BM(y+t+r))求得r，或由h1=Hash(BM(y+t+x1?x))求得x，只能試圖通過(guò)窮舉攻擊方法實(shí)現(xiàn)。而由于x,r均為Alice的私密有理數(shù)，即使x的范圍限制在某有限區(qū)間內(nèi)，由于有理數(shù)的稠密性，Bob不可能通過(guò)窮舉攻擊得到數(shù)據(jù)x的任何信息。因此，Alice的私有數(shù)據(jù)x是安全的。

安全性證明：通過(guò)前面的理論分析和抵抗窮舉攻擊的分析可知，協(xié)議1理論上是安全的。為了進(jìn)一步證明協(xié)議1的安全性，通過(guò)嚴(yán)格的模擬范例方法進(jìn)行證明，證明如下。

定理1有理數(shù)相等保密判定協(xié)議1是安全的。

證明在半誠(chéng)實(shí)模型下，利用模擬范例方法嚴(yán)格證明協(xié)議1的安全性。構(gòu)造模擬器S1(或S2)，使式(1)（或式(2)）成立。僅構(gòu)造S2（S1的構(gòu)造方法完全類似），對(duì)于輸入(y,f2(x,y)=P(x,y))，模擬器S2按以下方式運(yùn)行。

1)S2先任意選擇x′，使P(x′,y)=P(x,y)。

2)S2選擇隨機(jī)數(shù)r′，并計(jì)算x1′=x′+r′。

3 )S2計(jì)算y2′=y1+r′和，并應(yīng)用BMF編碼方案將x2′,y2′分別編碼為十進(jìn)制正整數(shù)。

4)S2計(jì)算和。

由于r是Alice選的隨機(jī)數(shù)，通過(guò)前面的安全性分析可知，Bob由x1=x+r,h1=Hash(BM? (y+t+r))無(wú)法獲得Alice數(shù)據(jù)x和r的任何信息，因此有

又由于P(x′,y)=P(x,y)，因此

類似地，可以構(gòu)造模擬器S1使

證畢。

3.2 有理數(shù)相等問(wèn)題?優(yōu)化的REq協(xié)議

協(xié)議2有理數(shù)相等保密判定協(xié)議

輸入Alice輸入有理數(shù)x，Bob輸入有理數(shù)y

輸出P(x,y)

準(zhǔn)備Alice和Bob共同商定一個(gè)單向哈希函數(shù)Hash()

1) Bob執(zhí)行以下操作：

a) 隨機(jī)選取足夠大的有理數(shù)t，計(jì)算y1=y+t和y2=2y+t；

b) 利用BMF編碼方案，把有理數(shù)y2編碼為整數(shù)Y2=BM(y2)并計(jì)算h2=Hash(Y2)，將y1和h2發(fā)送給Alice。

2) Alice執(zhí)行以下操作:

a) 計(jì)算x1=x+y1，并將有理數(shù)x1編碼為整數(shù)X1=BM(x1)；

b) 計(jì)算h1=Hash(X1)，并比較h1與h2，如果h1=h2，則輸出P(x,y)=1; 否則，輸出P(x,y)=0。

分析協(xié)議2的正確性和安全性完全類似于協(xié)議1，故詳細(xì)的分析在此省略。協(xié)議2只需要半輪通信，通信效率高于協(xié)議1，但降低了協(xié)議的公平性。因此，根據(jù)不同的場(chǎng)景，可以選擇不同的協(xié)議進(jìn)行計(jì)算。關(guān)于協(xié)議2的安全性有下面定理2。

定理2有理數(shù)相等保密判定協(xié)議2是安全的。 協(xié)議2的證明過(guò)程完全類似于協(xié)議1，故在此省略。

3.3 有理向量相等問(wèn)題

問(wèn)題描述Alice擁有有理向量(x1,…,xn)，Bob擁有有理向量（這里有理向量指向量的所有分量都是有理數(shù)），雙方想要保密判定兩個(gè)向量與是否相等。如果不相等，不應(yīng)向?qū)Ψ叫孤蹲约核矫芟蛄康娜魏涡畔ⅰ?/p>

計(jì)算原理根據(jù)有理向量的編碼方法VBMF，分別將有理向量編碼為正整數(shù)，則可將有理向量相等的保密判定問(wèn)題轉(zhuǎn)化為整數(shù)集上數(shù)值相等問(wèn)題。

協(xié)議3有理向量相等保密判定協(xié)議

輸入Alice輸入有理向量，Bob輸入有理向量

輸出

1) Alice和Bob分別選取隨機(jī)有理向量R=(r1,…,rn)和T=(t1,…,tn)（其中ri,ti(i∈[1,n])均為隨機(jī)有理數(shù)），計(jì)算，并將結(jié)果發(fā)送給對(duì)方。

2) Alice和Bob執(zhí)行如下步驟：

b) Alice和Bob根據(jù)向量編碼方法VBMF分別將向量和編碼為整數(shù)和；

協(xié)議3的正確性和安全性協(xié)議3的設(shè)計(jì)思想與協(xié)議1類似，協(xié)議3的正確性和安全性證明過(guò)程與協(xié)議1也相似，這里僅敘述下面定理。

定理3有理向量相等的保密判定協(xié)議3是安全的。

協(xié)議3的安全性證明完全類似于協(xié)議1，故在此省略。

4 集合問(wèn)題的保密判定方案

本節(jié)主要以協(xié)議1和協(xié)議3的構(gòu)造思想為基礎(chǔ)，研究設(shè)計(jì)有理數(shù)域上元素與集合關(guān)系問(wèn)題（ReES，the relationship problem between element and set）、坐標(biāo)系中的點(diǎn)集合問(wèn)題（RePS，point set problem of coordinate system）的保密計(jì)算協(xié)議。

4.1 元素與集合關(guān)系問(wèn)題

問(wèn)題描述Alice擁有私密的有理數(shù)集合X={x1,…,xn}，Bob擁有有理數(shù)y，他們希望合作保密判定y是否屬于集合X，不泄露雙方的任何信息（包括保密集合X的勢(shì)）。

計(jì)算原理

1) 根據(jù)協(xié)議1的構(gòu)造思想，Alice（或Bob）利用BMF編碼對(duì)自己的有理數(shù)集合元素x1,…,xn（或y）進(jìn)行編碼，Alice得到編碼整數(shù)集合U={u1,…,un}（其中ui=BM(xi),i∈[1,n]），Bob得到v=BM(y)。那么，判定y是否屬于集合

X的問(wèn)題可轉(zhuǎn)化為判定v是否屬于集合U的問(wèn)題。

2) 為了隱藏Alice集合的勢(shì)，Alice隨機(jī)選擇整數(shù)l>n，構(gòu)造l?n個(gè)形如1b1…bk0…0或 2b1…bk0…0的“偽編碼數(shù)”（這里k為任意選取的正整數(shù)，bj(j∈[1,k])在{0,…,9}中隨機(jī)選取，最后k位設(shè)為零），記這些整數(shù)為un+1,…,ul。將這些整數(shù)添加到集合U中，得到一個(gè)勢(shì)為l的新集合，將其記為。

3) 根據(jù)“偽編碼數(shù)”un+1,…,ul的構(gòu)造方式，由于任何有理數(shù)的編碼整數(shù)都不可能是un+1,…,ul的形式，可知y∈X當(dāng)且僅當(dāng)v∈U?。

下面根據(jù)上述計(jì)算原理設(shè)計(jì)協(xié)議，定義二元謂詞P(y,X)：當(dāng)y∈X時(shí)，P(y,X)=1；否則，P(y,X)=0。

協(xié)議4元素與集合關(guān)系的保密判定協(xié)議

輸入Alice輸入有理數(shù)集合X={x1,…,xn}，Bob輸入有理數(shù)y

輸出P(y,X)

1) Bob執(zhí)行以下操作:

a) Bob隨機(jī)選取足夠大的有理數(shù)t，計(jì)算y1=y+t和y2=2y+t，并將y1發(fā)送給Alice；

b) Bob按照BMF編碼方案，將y2編碼為整數(shù)v=BM(y2)，并計(jì)算z=Hash(v)。

2) Alice執(zhí)行以下操作：

a) Alice計(jì)算W={x1+y1,…,xn+y1}:={w1,…,wn}；

b) Alice按照BMF編碼方案，將wi編碼為整數(shù)ui=BM(wi)(i∈[1,n])，并隨機(jī)添加“偽編碼數(shù)”un+1,…,ul得到集合；

c) Alice計(jì)算Z={Hash(u1),…,Hash(ul)}:= {z1,…,zl}，并將Z發(fā)送給Bob。

3) Bob比較z與Z，若存在i∈[1,l]，使z=zi，則輸出P(y,X)=1；否則，輸出P(y,X)=0。

協(xié)議4的正確性根據(jù)協(xié)議4的過(guò)程和BMF編碼方案可知

因此，協(xié)議4是正確的。

協(xié)議4的安全性關(guān)于協(xié)議4的安全性，從以下兩部分進(jìn)行詳細(xì)的分析證明：① 安全性分析，包括理論分析和抵抗窮舉攻擊分析；② 安全性證明，對(duì)第①部分的理論證明。

安全性分析：首先分析Alice集合X的安全性。在協(xié)議執(zhí)行中，Bob得到Alice發(fā)送的集合Z={z1,…,zl}。由于l是Alice選取的隨機(jī)數(shù)，保證了Alice的集合勢(shì)n的安全性，并且Bob無(wú)法區(qū)分出集合Z中的真假元素。根據(jù)單向哈希函數(shù)的性質(zhì)，Bob無(wú)法從zi=Hash(ui)(i∈[1,l])中得到ui的任何信息，因此集合元素xi是安全的，集合X是安全的。

接著分析Bob數(shù)據(jù)y的安全性。Alice僅得到Bob發(fā)送的y1=y+t，由于Alice不知道隨機(jī)數(shù)t，所以Bob的數(shù)據(jù)y是安全的。

下面說(shuō)明協(xié)議4可以抵抗窮舉攻擊。協(xié)議4抵抗窮舉攻擊的過(guò)程和協(xié)議1類似，根據(jù)協(xié)議1的分析可知，由于有理數(shù)的稠密性，任意有理數(shù)的編碼整數(shù)均勻分布在整個(gè)數(shù)軸上，所以編碼整數(shù)的范圍是無(wú)限的，故協(xié)議4可以抵抗窮舉攻擊。

安全性證明：通過(guò)前面的理論分析和抵抗窮舉攻擊的分析可知，協(xié)議4理論上是安全的。為了進(jìn)一步證明協(xié)議4的安全性，通過(guò)嚴(yán)格的模擬范例方法進(jìn)行證明，證明如下。

定理4元素與集合關(guān)系的保密判定協(xié)議4是安全的。

證明下面應(yīng)用模擬范例嚴(yán)格證明定理4，為此需要構(gòu)造模擬器S1（或S2），分別使式(1)（或式(2)）成立。

先構(gòu)造S1。對(duì)輸入(X,f1(y,X)=P(y,X))，S1按以下方式運(yùn)行。 1)S1任意選擇y′，使P(y′,X)=P(y,X)。

2)S1隨機(jī)選取足夠大的有理數(shù)t′計(jì)算y1′=y′+t′和y2′=2y′+t′。將y2′編碼為整數(shù)v′=BM(y2′)，并計(jì)算h′=Hash(v′)。

3)S1計(jì)算。并將wi′編碼為整數(shù)ui′ =BM(wi′)(i∈[1,n])。根據(jù)計(jì)算原理，S1隨機(jī)添加“偽編碼數(shù)”得到集合。

由于t和t′為隨機(jī)數(shù)，有，因此；進(jìn)一步，由于P(y′,X)=P(y,X)，因此。

對(duì)于輸入(y,f2(y,X)=P(y,X))，模擬器S2按以下方式運(yùn)行。

1)S2構(gòu)造含n′個(gè)元素的集合， 使P(y,X′)=P(y,X)。

2)S2計(jì)算，并且按照BMF編碼方案，將wi′編碼為整數(shù)ui′ =BM(wi′)(i∈[1,n′])。由計(jì)算原理，S2隨機(jī)添加“偽編碼數(shù)”得到集合。

3)S2計(jì)算Z′={Hash(u1′),…,Hash(ul′ )}:= {z1′,…,zl′ }。

證畢。

4.2 坐標(biāo)系中的點(diǎn)集合問(wèn)題

目前，在SMC中對(duì)集合問(wèn)題的研究?jī)H限于元素為單一數(shù)據(jù)的集合。當(dāng)集合元素是一個(gè)數(shù)組時(shí)（如集合元素是坐標(biāo)點(diǎn)(x,y)），現(xiàn)有的解決方案并不適用。因此，本節(jié)研究坐標(biāo)點(diǎn)集問(wèn)題（進(jìn)一步可以擴(kuò)展到更高維的集合問(wèn)題）。

問(wèn)題描述Alice有一個(gè)點(diǎn)集合A={a1,…,an}，Bob有一點(diǎn)a0，其中ai=(xi,yi)且xi,yi(i∈[0,n])均為有理數(shù)。他們想保密判定是否a0∈A，不泄露雙方的任何信息A,a0。

計(jì)算原理根據(jù)VBMF編碼方案，Alice將點(diǎn)ai=(xi,yi)編碼為整數(shù)，得到一個(gè)新的集合；Bob將點(diǎn)a0=(x0,y0)編碼為整數(shù)。那么

為方便敘述，定義P(a0,A)：若a0∈A，P(a0,A)=1；否則，P(a0,A)=0。協(xié)議5點(diǎn)與點(diǎn)集合關(guān)系的保密判定協(xié)議

輸入Alice輸入一個(gè)點(diǎn)集合A={a1,…,an}，Bob輸入點(diǎn)a0=(x0,y0)

輸出P(a0,A)

1) Bob隨機(jī)選取點(diǎn)T=(t1,t2)計(jì)算，其中t1,t2均為有理數(shù)，并將發(fā)送給Alice。

2) Alice執(zhí)行以下操作：

a) Alice隨機(jī)選取點(diǎn)集合R={R1,…,Rn}計(jì)算W={a1+R1,…,an+Rn}:={w1,…,wn}以及，其中Ri=(ri1,ri2)，均為有理數(shù)。

b) Alice對(duì)點(diǎn)集合W和U執(zhí)行相同的隨機(jī)置換得到和。根據(jù)VBMF編碼方案，Alice將點(diǎn)u?i(i∈[1,n])編碼為整數(shù)，并得到向量。

3) Bob執(zhí)行以下操作：

c) Bob比較Z和Z′。若存在i∈[1,n]，使zi=zi′ ，則輸出P(a0,A)=1；否則，輸出P(a0,A)=0。

協(xié)議5的正確性根據(jù)協(xié)議5的過(guò)程以及VBMF編碼方案可知

因此，協(xié)議5是安全的。

協(xié)議5的安全性關(guān)于協(xié)議5的安全性，本文從以下兩部分分別進(jìn)行詳細(xì)的分析證明：① 安全性分析，包括理論分析和抵抗窮舉攻擊分析；② 安全性證明，對(duì)第①部分的理論證明。

安全性分析：下面分析協(xié)議5的安全性，并表明協(xié)議5可以抵抗窮舉攻擊。首先，分析Alice集合A的安全性。在協(xié)議執(zhí)行中，Bob得到Alice發(fā)送的Z=(z1,…,zl)和。根據(jù)單向哈希函數(shù)的性質(zhì)可知，Bob根據(jù)zi=Hash(ui)(i∈[1,n])得不到關(guān)于ui或者Ri的任何信息。進(jìn)一步，對(duì)于中的有理數(shù)組ai和Ri均為Alice的私有數(shù)據(jù)，因此Bob根據(jù)得不到關(guān)于ai的任何信息，即點(diǎn)ai是安全的。因此集合A是安全的。

其次，分析Bob的點(diǎn)a0的安全性。Alice僅得到Bob發(fā)送的，因?yàn)殡S機(jī)數(shù)組T是Bob的私密數(shù)據(jù)，Alice根據(jù)得不到a0的任何信息。因此，Bob的點(diǎn)a0是安全的。

最后，說(shuō)明協(xié)議5可以抵抗窮舉攻擊。協(xié)議5抵抗窮舉攻擊的過(guò)程類似于協(xié)議1和協(xié)議4，故在此省略。

安全性證明：通過(guò)前面的理論分析和抵抗窮舉攻擊的分析可知，協(xié)議5理論上是安全的。為了進(jìn)一步證明協(xié)議5的安全性，下面通過(guò)嚴(yán)格的模擬范例方法進(jìn)行證明。

定理5點(diǎn)與點(diǎn)集合關(guān)系的保密判定協(xié)議5是安全的。

協(xié)議5的安全性證明過(guò)程完全類似于協(xié)議4，故在此省略。

5 性能分析

下面對(duì)本文所設(shè)計(jì)協(xié)議的性能和適用范圍進(jìn)行分析，并與現(xiàn)有相關(guān)協(xié)議分析進(jìn)行比較。文獻(xiàn)[17,18]分別研究了整數(shù)范圍和有理數(shù)域上的數(shù)據(jù)相等問(wèn)題，主要以Hash函數(shù)以及Paillier同態(tài)加密算法為基礎(chǔ)設(shè)計(jì)協(xié)議，文獻(xiàn)[17]的協(xié)議計(jì)算效率較高但僅適用于整數(shù)范圍；文獻(xiàn)[18]解決了有理數(shù)相等問(wèn)題但計(jì)算效率相對(duì)較低。文獻(xiàn)[21]以Paillier同態(tài)加密算法為基礎(chǔ)設(shè)計(jì)了有理數(shù)域上元素與集合關(guān)系的保密判定協(xié)議，但計(jì)算效率低且應(yīng)用范圍小。

下面主要通過(guò)比較各協(xié)議所需要進(jìn)行的Hash運(yùn)算次數(shù)以及模指數(shù)運(yùn)算的次數(shù)來(lái)衡量計(jì)算復(fù)雜性，而應(yīng)用執(zhí)行協(xié)議所需要的通信輪數(shù)來(lái)衡量協(xié)議的通信復(fù)雜性。為了便于分析比較，假設(shè)Alice集合的勢(shì)為n，Bob集合的勢(shì)為m。

5.1 理論分析與比較

5.1.1 計(jì)算復(fù)雜性分析

本文協(xié)議1～協(xié)議5主要運(yùn)用了基本算術(shù)運(yùn)算（普通實(shí)數(shù)的加減乘除運(yùn)算）和Hash運(yùn)算，由于基本算術(shù)運(yùn)算與Hash運(yùn)算相比計(jì)算復(fù)雜性可以忽略，在此只考慮Hash運(yùn)算次數(shù)。

協(xié)議1（協(xié)議2）中Alice和Bob分別執(zhí)行了1次Hash運(yùn)算，因此協(xié)議1（協(xié)議2）共執(zhí)行了2次Hash運(yùn)算。協(xié)議3應(yīng)用協(xié)議1的基本思想，將向量相等問(wèn)題轉(zhuǎn)化為數(shù)值相等問(wèn)題，協(xié)議3也需要執(zhí)行2次Hash運(yùn)算。協(xié)議4中Alice執(zhí)行了l次Hash運(yùn)算，Bob執(zhí)行了1次Hash運(yùn)算，即協(xié)議4共執(zhí)行了l+1次Hash運(yùn)算（其中l(wèi)是為隱藏集合X的勢(shì)選取的大于|X|=n的一個(gè)數(shù)值，不需要取值太大，能夠保證協(xié)議4具有線性復(fù)雜性）?；趨f(xié)議4的設(shè)計(jì)思想，協(xié)議5首次解決了坐標(biāo)系中點(diǎn)與點(diǎn)集合關(guān)系的保密計(jì)算問(wèn)題。在協(xié)議5中，Alice和Bob均需要執(zhí)行n次Hash運(yùn)算，即協(xié)議5共執(zhí)行了2n次Hash運(yùn)算。

文獻(xiàn)[17]基于Hash函數(shù)設(shè)計(jì)了正整數(shù)范圍內(nèi)相等問(wèn)題的保密判定協(xié)議1和向量相等協(xié)議2，協(xié)議1和協(xié)議2均需執(zhí)行2次Hash運(yùn)算。文獻(xiàn)[18]基于Paillier同態(tài)加密算法設(shè)計(jì)了有理數(shù)相等保密判定協(xié)議，協(xié)議共需要6次模指數(shù)運(yùn)算。文獻(xiàn)[21]基于Paillier同態(tài)加密算法設(shè)計(jì)了有理數(shù)域上元素與集合關(guān)系的保密判定協(xié)議，其中Alice需要執(zhí)行l(wèi)+2次模指數(shù)運(yùn)算，Bob需要執(zhí)行2l+6次模指數(shù)運(yùn)算，協(xié)議共需執(zhí)行3l+8次模指數(shù)運(yùn)算。

5.1.2 通信復(fù)雜性分析

本文協(xié)議1和協(xié)議3各需要2輪通信；協(xié)議2需要半輪通信；協(xié)議4～協(xié)議5各需要1輪通信。

文獻(xiàn)[17]中的協(xié)議1和協(xié)議2均需2輪通信；文獻(xiàn)[18]需要2輪通信；文獻(xiàn)[21]需要2輪通信。

根據(jù)上述理論分析，現(xiàn)將本文協(xié)議的效率及適用范圍分析的結(jié)果在表1中給出。在表1中，其中計(jì)算功能一欄為所列文獻(xiàn)研究的具體內(nèi)容；計(jì)算復(fù)雜性一欄，H（或M）表示Hash（或模指數(shù)）運(yùn)算，通信復(fù)雜性為通信輪數(shù)。

表1 協(xié)議的效率分析與適用范圍比較Table 1 Efficiency analysis and scope analysis of the protocols

通過(guò)表1分析可知，本文協(xié)議僅需較少的Hash運(yùn)算即可實(shí)現(xiàn)有理數(shù)（或有理向量）相等問(wèn)題以及有理集合問(wèn)題的保密判定，擴(kuò)展了相關(guān)安全多方計(jì)算問(wèn)題的適用范圍且計(jì)算效率優(yōu)勢(shì)明顯。

5.2 實(shí)驗(yàn)測(cè)試

表1從理論上對(duì)本文協(xié)議和以往相關(guān)協(xié)議的效率進(jìn)行了全面分析，并進(jìn)行了比較。下面進(jìn)一步利用Java編程語(yǔ)言在MyEclipse上對(duì)本文協(xié)議4和文獻(xiàn)[21]的協(xié)議進(jìn)行編程實(shí)現(xiàn)。

（1）實(shí)驗(yàn)平臺(tái)

計(jì)算機(jī)的配置如下：操作系統(tǒng)為Windows10企業(yè)版，Intel Core i5-6600 CPU @3.30 GHz，安裝內(nèi)存8.00 GB，64位操作系統(tǒng)。在此，約定本文協(xié)議所做模擬實(shí)驗(yàn)均在此環(huán)境下進(jìn)行。

（2）實(shí)驗(yàn)結(jié)果

本文協(xié)議4應(yīng)用單向哈希函數(shù)，文獻(xiàn)[21]應(yīng)用Paillier同態(tài)加密體制，下面分別對(duì)本文協(xié)議4和文獻(xiàn)[21]進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)設(shè)定Paillier加密方案中大素?cái)?shù)p和q的位數(shù)為512 bit，因此模數(shù)的位數(shù)為1 024 bit。保密數(shù)據(jù)的范圍為[?100, 100]。通過(guò)對(duì)本文協(xié)議4和文獻(xiàn)[21]的協(xié)議進(jìn)行實(shí)際計(jì)算，對(duì)每種協(xié)議進(jìn)行多次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果隨機(jī)抽取50次數(shù)據(jù)求取平均值，結(jié)果如表2所示。

表2 實(shí)驗(yàn)結(jié)果分析Table 2 Analysis of simulation result

由表2可知，與文獻(xiàn)[21]相比，本文協(xié)議4的計(jì)算效率較高，且優(yōu)勢(shì)明顯。理論分析（表1）和實(shí)驗(yàn)測(cè)試（表2）兩方面均表明本文協(xié)議優(yōu)勢(shì)明顯。

為了進(jìn)一步測(cè)試效率和集合基數(shù)（添加“偽編碼”數(shù)后的元素個(gè)數(shù)）之間的關(guān)系，對(duì)本文協(xié)議4和文獻(xiàn)[21]分別進(jìn)行了多維實(shí)驗(yàn)測(cè)試，實(shí)驗(yàn)結(jié)果如圖1所示。

在不同基數(shù)下的仿真結(jié)果（圖1）表明本文協(xié)議4的計(jì)算效率隨集合基數(shù)的變化幅度較小，文獻(xiàn)[21]的計(jì)算效率隨集合基數(shù)的變化幅度較大，本文協(xié)議4具有明顯優(yōu)勢(shì)，且本文協(xié)議4更適用于集合基數(shù)大的應(yīng)用場(chǎng)景，適用范圍更廣。

圖1 計(jì)算效率與集合基數(shù)的關(guān)系Figure 1 The relationship between computational efficiency and set cardinality

6 協(xié)議的推廣及實(shí)際應(yīng)用

目前關(guān)于有理數(shù)域上的安全多方計(jì)算的研究較少，但在計(jì)算幾何等方面有理數(shù)的應(yīng)用十分廣泛，下面根據(jù)前面協(xié)議的設(shè)計(jì)思想，對(duì)更廣泛的有理數(shù)域上安全多方計(jì)算實(shí)際應(yīng)用問(wèn)題設(shè)計(jì)新的高效的保密協(xié)議。

直線位置關(guān)系問(wèn)題描述

Alice有一條直線l1:y=k1x+b1，Bob有一條直線l2:y=k2x+b2，雙方要保密判定兩條直線的位置關(guān)系（重合、平行、相交、垂直），不泄露各自的私密信息。

直線位置關(guān)系計(jì)算原理

首先，根據(jù)兩條直線位置關(guān)系的判定定理可知，① 當(dāng)兩條直線的斜率k1=k2且截距b1=b2時(shí)，兩直線重合，記為l1=l2；② 當(dāng)兩條直線的斜率k1=k2但截距b1≠b2時(shí)，兩直線平行，記為l1‖l2；③ 當(dāng)兩條直線的斜率k1≠k2時(shí)，兩直線相交，記為l1×l2；④ 當(dāng)兩條直線的斜率滿足k1×k2=?1時(shí)，兩直線垂直，記為l1⊥l2。特別地，當(dāng)直線與X軸平行時(shí)，記直線斜率為?0/1； 當(dāng)直線與Y軸平行時(shí)，記直線斜率為1/0。那么，兩直線位置關(guān)系描述如下。

其次，Alice和Bob利用有理向量的編碼方法VBMF，將向量(k1,b1),(k2,b2)分別編碼為整數(shù)u1,v1；Alice利用有理數(shù)編碼方法BMF，將斜率k1,?1/k1分別編碼為整數(shù)u2,u3；Bob利用有理數(shù)編碼方法BMF，將斜率k2編碼為整數(shù)v2，則

根據(jù)上述計(jì)算原理設(shè)計(jì)協(xié)議，為敘述方便，定義二元謂詞P(l1,l2)如下。

具體協(xié)議如下。

協(xié)議6直線位置關(guān)系的保密判定協(xié)議

輸入Alice輸入直線l1:y=k1x+b1，Bob輸入直線l2:y=k2x+b2

輸出P(l1,l2)

準(zhǔn)備Alice、Bob商定單向哈希函數(shù)Hash()

1) 按照計(jì)算原理所述，Alice利用VBMF編碼方案和BMF編碼方案，將向量(k1,b1)以及分別編碼為整數(shù)u1,u2,u3；類似地，Bob利用VBMF編碼方案和BMF編碼方案，將向量(k2,b2)以及k2分別編碼為整數(shù)v1,v2。

2) Bob選取充分大的隨機(jī)數(shù)t1,t2（均為有理數(shù)），分別計(jì)算和，并將結(jié)果發(fā)送給Alice。

3) Alice選取充分大的隨機(jī)數(shù)r1,r2,r3（均為有理數(shù)），計(jì)算W=(u1+r1,u2+r2,u3+r3):=(w1,w2,w3)，以及(z1,z2,z3)，并將W,Z發(fā)送給Bob。

Bob比較Z與Z′的各個(gè)分量，如果z1=z1′，則輸出P(l1,l2)=0；如果z1≠z1′,z2=z′2，則輸出P(l1,l2)=1；如果z2≠z2′，則輸出P(l1,l2)=2；如果z3=z3′，則輸出P(l1,l2)=3。

協(xié)議6的正確性和安全性協(xié)議6的設(shè)計(jì)思想本質(zhì)上是協(xié)議1和協(xié)議3設(shè)計(jì)思想的推廣。根據(jù)協(xié)議1和協(xié)議3的正確性和安全性可知，協(xié)議6是正確且安全的。

7 結(jié)束語(yǔ)

本文提出了有理數(shù)域上一些基本的安全多方計(jì)算問(wèn)題，設(shè)計(jì)了有理數(shù)（數(shù)組）的編碼方法，并以此為基礎(chǔ)解決了有理數(shù)域上相等問(wèn)題和集合問(wèn)題的保密計(jì)算。通過(guò)對(duì)本文協(xié)議進(jìn)行適當(dāng)?shù)膽?yīng)用，可以進(jìn)一步解決有理數(shù)域上其他的安全多方計(jì)算問(wèn)題，對(duì)后續(xù)有理數(shù)域上安全多方計(jì)算問(wèn)題的研究和應(yīng)用具有重要意義。目前，本文的協(xié)議是在半誠(chéng)實(shí)模型下設(shè)計(jì)的，未來(lái)將進(jìn)一步研究惡意模型下有理數(shù)域上的安全多方計(jì)算問(wèn)題。