基于Rabin 的概率型1 選1 不經(jīng)意傳輸協(xié)議?

2021-04-06 06:51張艷碩趙瀚森李澤昊

北京電子科技學(xué)院學(xué)報 2021年1期

張艷碩趙瀚森李澤昊

北京電子科技學(xué)院，北京市 100070

1 引言

隨著電子信息技術(shù)的不斷迅猛發(fā)展，各種信息系統(tǒng)得到廣泛使用，如電子商務(wù)，醫(yī)療保健、內(nèi)容保護等。為獲取服務(wù)或完成交易通常需要交換大量個人信息，如商務(wù)活動中消費者的信用卡信息、銀行賬戶信息、支付情況醫(yī)療衛(wèi)生保健系統(tǒng)中患者的年齡等等。私人信息的泄漏和濫用可能導(dǎo)致災(zāi)難性的后果。保護私人數(shù)據(jù)的隱私越來越成為信息社會的一個令人關(guān)注的問題。

不經(jīng)意傳輸協(xié)議(Oblivious Transfer，簡稱為OT 協(xié)議)[1]，是密碼學(xué)的一個基本協(xié)議，是一種可保護隱私的雙方通信協(xié)議，通信雙方可以以一種模糊化的方式傳送消息。他使得服務(wù)的接收方以不經(jīng)意的方式得到服務(wù)發(fā)送方輸入的某些消息，這樣就可以在保證接收者在不知道發(fā)送者隱私的前提下，保護接受者的隱私不被發(fā)送者所知道，比如，不經(jīng)意的網(wǎng)上訂購，消費者可能不愿意暴露其購買的某些商品(如某些藥品)；，在線付費瀏覽，用戶可用不經(jīng)意的方式選擇某些敏感信息，股票交易的買家和賣家都不會希望交易暴露給第三方。

不經(jīng)意傳輸協(xié)議能使通信雙方以一種不經(jīng)意的方式傳送消息。與匿名技術(shù)相比較不經(jīng)意傳輸協(xié)議是一種低強度的隱私保護方法，但是在匿名技術(shù)不易實現(xiàn)或不合需要的場合中不經(jīng)意傳輸協(xié)議為能夠保護用戶的隱私提供了一種現(xiàn)實的選擇。

不經(jīng)意傳輸協(xié)議最初是由Rabin 在1981 年提出的，隨后又出現(xiàn)多種形式。不經(jīng)意傳輸既可作為基本組件構(gòu)造其它安全協(xié)議又可直接應(yīng)用于電子商務(wù)等領(lǐng)域保護用戶的隱私。在Rabin的方案中實現(xiàn)了1 選1 不經(jīng)意傳輸協(xié)議，接收方有50%的概率可以成功獲取秘密信息，從此不經(jīng)意傳輸協(xié)議逐漸成為密碼學(xué)的一個重要組成部分，隨著學(xué)者們的不斷深入研究，不經(jīng)意傳輸協(xié)議也在不斷的發(fā)展和完善，逐漸的應(yīng)用到我們生活的各個領(lǐng)域，如安全多方計算、證券、股票、電子交易、公平拍賣協(xié)議等多個方面。

目前，不經(jīng)意傳輸主要分為以下四類:經(jīng)典1 選1 不經(jīng)意傳輸協(xié)議[2]、2 選1 不經(jīng)意傳輸協(xié)議[3]、n 選1 不經(jīng)意傳輸協(xié)議[4]和n 選k 不經(jīng)意傳輸協(xié)議[5]。并且經(jīng)過學(xué)者的努力，每一類的不經(jīng)意傳輸協(xié)議都有著很多的改進方案及應(yīng)用，對2 選1 不經(jīng)意傳輸來說，2008 年，Abhishek Parakh[6]等人基于Diffie Hellman 密鑰交換協(xié)議，為實現(xiàn)不經(jīng)意傳輸?shù)膫鹘y(tǒng)方法提供了一種有用的替代方案；2017 年Martin Plesch 等人[7]提出了一種更為簡化的2 選1 不經(jīng)意傳輸協(xié)議。對n 選1 不經(jīng)意傳輸協(xié)議來說，2000 年Gertner等人[8]提出了一種分布式n 選1 不經(jīng)意傳輸協(xié)議； 2004 年，Tzeng 等人[9]基于判定性Diffie Hellman 困難性假設(shè)，設(shè)計出了一個新的不經(jīng)意傳輸協(xié)議。對n 選k 不經(jīng)意傳輸協(xié)議來說，2014年，Der Chyuan Lou 等人[10]在橢圓曲線密碼體制的基礎(chǔ)上，提出了一種新的用于私人信息檢索的n 選k 不經(jīng)意傳輸協(xié)議，該協(xié)議更適合于智能卡或移動設(shè)備，更適合當(dāng)前的時代發(fā)展；2019年，NicoDottling 等人[11]提出了一種構(gòu)造惡意安全的兩輪不經(jīng)意轉(zhuǎn)移的新方法，在可計算Diffie Hellman(CDH)假設(shè)或?qū)W習(xí)等價噪聲(LPN)假設(shè)下給出了基本OT 的簡單構(gòu)造，得到了惡意(UCsecure) 兩輪 OT 的第一個構(gòu) 造； 2020 年，VipulGoyal 等人[12]給出了三輪不經(jīng)意傳輸協(xié)議的第一個構(gòu)造-在普通模型中-基于多項式時間假設(shè)，實現(xiàn)接收者的統(tǒng)計隱私和發(fā)送者對抗惡意對手的計算隱私。

2 不經(jīng)意傳輸協(xié)議性質(zhì)及其分類

2.1 不經(jīng)意傳輸協(xié)議的性質(zhì)

不經(jīng)意傳輸協(xié)議是一種可以保護隱私的密碼協(xié)議。對于一般的密碼協(xié)議來說，首先，密碼協(xié)議中的每人都必須了解協(xié)議，并且預(yù)先知道所要完成的所有步驟。其次，密碼協(xié)議中的每人都必須同意遵循它。再次，密碼協(xié)議必須是不模糊的，每一步必須明確定義，并且不會引起誤解。最后，密碼協(xié)議必須是完整的，對每種可能的情況必須規(guī)定具體的動作。

對于一般的不經(jīng)意傳輸協(xié)議來說，應(yīng)該具有以下6 個性質(zhì):

(1)協(xié)議正確性:這是最基本的屬性，在協(xié)議完成后，接收方可以通過協(xié)議以一定的概率正確的得到自己所選擇的消息。

(2)發(fā)送方的隱私性:在協(xié)議完成后，如果接收方?jīng)]有成功恢復(fù)秘密信息，那么他是不可能知道秘密消息是什么的。

(3)接收方的隱私性:在協(xié)議完成后，發(fā)送方不能以任何方式來了解接收方是否成功接收到了秘密消息。

(4)抗冒名攻擊:在協(xié)議執(zhí)行過程中，只有真正的接收方才能從發(fā)送方那里獲取所選擇的信息。

(5)抗重放攻擊:如果存在惡意第三方，且在雙方傳遞數(shù)據(jù)時被惡意第三方成功竊聽，第三方雖然拿到了傳遞的數(shù)據(jù)，但仍無法知道發(fā)送方擁有的秘密消息和接收方是否成功恢復(fù)了消息。

(6)抗中間人攻擊:中間人攻擊是指第三方在協(xié)議執(zhí)行過程中竊聽到雙方傳遞的數(shù)據(jù)，同時對發(fā)送方和接收方進行欺騙，以防止雙方中的任意一方發(fā)現(xiàn)第三方的攻擊而終止協(xié)議。一個安全的不經(jīng)意傳輸協(xié)議應(yīng)該具有抵抗中間人攻擊的能力。

2.2 不經(jīng)意傳輸協(xié)議的分類

不經(jīng)意傳輸協(xié)議作為一種保證通信雙方信息隱私性的通信協(xié)議，通常有兩個協(xié)議的參與方:信息持有者Alice 和信息接收者Bob。而目前存在的不經(jīng)意傳輸協(xié)議大致可分為以下四類:

(1)1 選1 不經(jīng)意傳輸協(xié)議

1981 年Rabin[2]第一次提出不經(jīng)意傳輸?shù)母拍?，該協(xié)議中是基于二次剩余假設(shè)[11]之上的，信息持有者Alice 以二次剩余的方式加密所持有的秘密信息，信息接受者Bob 有1/2 的概率解密得到該秘密信息，同時Alice 不知道Bob 是否真的得到秘密信息。

(2)2 選1 不經(jīng)意傳輸協(xié)議

1985 年Even 等人[3]基于公鑰體制提出了2選1 的不經(jīng)意傳輸協(xié)議。在這個協(xié)議中，信息持有者Alice 擁有兩個秘密消息，并將這兩個秘密消息加密后發(fā)送給Bob，Bob 通過一定的方式進行解密恢復(fù)后，得到兩個秘密消息中的一個。在協(xié)議結(jié)束后，Alice 不知道Bob 所得到的是哪一個秘密消息，同時，Bob 也不知道除了自己所得到的另一條秘密消息是什么。

(3)n 選1 不經(jīng)意傳輸協(xié)議

1986 年Brassard 等人[4]通過調(diào)用2 選1 的不經(jīng)意傳輸協(xié)議，提出了n 選1 的不經(jīng)意傳輸。在這個協(xié)議中，Alice 擁有n 個秘密消息，Bob 可以選擇自己想要的秘密消息的序號，加密后告訴Alice，Alice 在對n 個秘密信息加密并發(fā)送給Bob 后，Bob 可以根據(jù)自己所選擇的消息序號對密文進行解密恢復(fù)，得到自己想要的秘密信息。最后Alice 并不知道Bob 所選擇的序號是多少，也不會知道Bob 恢復(fù)了哪個信息，同時，Bob 也不會知道其他n-1 個秘密消息是什么。

(4) n 選k 不經(jīng)意傳輸協(xié)議

1999 年Naor 等人[5]提出了真正意義上的n 選k 的不經(jīng)意傳輸協(xié)議。在這個協(xié)議中，Bob可以選擇k 個自己想要的秘密信息序號，加密后發(fā)送給Alice，Alice 根據(jù)接收到的密文和自己所持有的n 個秘密信息加密得到密文并發(fā)送給Bob，Bob 可以通過自己選擇的序號得到且僅得到自己想要的k 個秘密信息。最終，Alice 不能知道Bob 所選擇的任意一個秘密信息是什么，Bob 也不能得知其他的n-k 個秘密信息。

在不經(jīng)意傳輸協(xié)議的研究中，2017 年Martin Plesch 等人[7]提出的一種更為簡化的2 選1 不經(jīng)意傳輸協(xié)議屬于2 選1 型不經(jīng)意傳輸協(xié)議。2000 年Gertner 等人[8]提出了一種分布式n 選1 不經(jīng)意傳輸協(xié)議和2004 年Tzeng 等人[9]設(shè)計的不經(jīng)意傳輸協(xié)議都屬于n 選1 型不經(jīng)意傳輸協(xié)議。 2014 年，Der Chyuan Lou 等人[10]提出的一種新的用于私人信息檢索的n 選k 不經(jīng)意傳輸協(xié)議屬于對n 選k 型不經(jīng)意傳輸協(xié)議。

3 經(jīng)典1 選1 不經(jīng)意傳輸協(xié)議

在Rabin[2]第一次提出的不經(jīng)意傳輸方案中，發(fā)送方將一條消息傳送給接收方，接收方有1/2 的概率接收成功，而發(fā)送方不知道接收方是否接收成功。協(xié)議的執(zhí)行流程如圖1 所示:

圖1 經(jīng)典不經(jīng)意傳輸協(xié)議

具體方案如下:

(1)設(shè)Alice 想不經(jīng)意傳輸給Bob 的秘密是整數(shù)n 的分解。 Alice 隨機選擇兩個大素數(shù)p 和q，計算n=pq 并發(fā)送給Bob。

(2)Bob 隨機選擇一整數(shù)x，并將x2mod n傳送給Alice。 Alice 接收到x2mod n 后，計算x2mod n 的四個平方根±a 和±b，并選擇4 個平方根中的一個發(fā)回給Bob，將發(fā)回的解記為m。在這步中，由于Alice 只知道x2mod n 的結(jié)果，因此Alice 并不知道哪一個是Bob 所選擇的x。

(3)Bob 接收到m 后，查驗m 和±x mod n 是否同余，如果同余，則說明Alice 發(fā)回的m 就是Bob 所選擇的x，Bob 不會得到任何消息；如果不同余，則Bob 可以利用求解gcd(x+m，n) 對大整數(shù)n 進行分解。

由于x2mod n 有且僅有兩個平方根和x 同余，因此接收方Bob 有1/2 的概率恢復(fù)秘密，即分解大整數(shù)n。而Alice 不知道Bob 是否成功分解了n。

經(jīng)典不經(jīng)意傳輸協(xié)議的安全性是依賴于大數(shù)分解難題的，2017 年楊波等人[14]給出的一種基于離散對數(shù)問題的非交互式1 選1 不經(jīng)意傳輸協(xié)議。

就現(xiàn)在的1 選1 不經(jīng)意傳輸協(xié)議來看，如果接收方只能以一種固定的概率獲取到自己想得到的信息，那么在應(yīng)用中可能會略顯刻板，應(yīng)用的場景也會受到一定的限制，因此在Rabin 方案的基礎(chǔ)上，提出一種可根據(jù)現(xiàn)實需求設(shè)置接收方接收到自己所需的信息的概率型1 選1 不經(jīng)意傳輸協(xié)議，在一些實際的應(yīng)用中也可以更加靈活.

4 概率型1 選1 不經(jīng)意傳輸協(xié)議方案設(shè)計

4.1 概率型1 選1 不經(jīng)意傳輸協(xié)議

概率型1 選1 不經(jīng)意傳輸協(xié)議是一種在經(jīng)典1 選1 不經(jīng)意傳輸協(xié)議的基礎(chǔ)上進行的推廣，經(jīng)典1 選1 不經(jīng)意傳輸協(xié)議是概率不經(jīng)意傳輸?shù)囊环N特殊情況。實際上，Rabin 在提出不經(jīng)意傳輸協(xié)議[2]后，對概率型1 選1 不經(jīng)意傳輸協(xié)議已經(jīng)進行了一個粗略的評述，但并沒有給出具體的方案，因此我們在這一章給出了概率型1 選1不經(jīng)意傳輸協(xié)議嚴(yán)格的定義，并給出方案。和不經(jīng)意傳輸協(xié)議一樣，概率不經(jīng)意傳輸一般也是由兩個參與者Alice (信息持有者) 和Bob (信息接收者) 共同完成。

概率型1 選1 不經(jīng)意傳輸協(xié)議可以很好的應(yīng)用到一些信息交易中:當(dāng)信息購買者的購買意愿不強時，信息的持有者為了達成交易，可以通過設(shè)置概率來降低信息購買者獲取秘密信息的可能，并對所持有的秘密信息降價處理，達到獲取信息的概率和價值相對應(yīng)的目的，進而明碼標(biāo)價讓購買者挑選成功獲取信息的概率來進行降價，接著信息持有者就可以通過設(shè)置概率來降低購買者成功獲取信息的可能，從而實現(xiàn)價值的對應(yīng)。

4.2 概率型1 選1 不經(jīng)意傳輸協(xié)議方案

設(shè)Alice 有一個秘密為n = p × q，Bob 想以概率P 獲取該秘密，但不想讓Alice 知道自己是否獲得了這個秘密，因此選用概率型1 選1 不經(jīng)意傳輸協(xié)議來實現(xiàn)目的，具體框架如圖2 所示:

圖2 概率型1 選1 不經(jīng)意傳輸協(xié)議

協(xié)議的具體流程如下:

(1) Alice 將大整數(shù)n 發(fā)送給Bob。

(4) Bob 接收到k 個解后，分別和x0，x1，…，xk-1進行模n 的同余驗證。在這里只有當(dāng)發(fā)回的k 個解和Bob 所選擇的k 個整數(shù)x0，x1，…，xk-1全部一一對應(yīng)同余時，才無法成功分解大數(shù)n。因此，Bob 有的概率成功分解n。

(5) Alice 再選擇(k-1)個大整數(shù)(其中k≥2)，記為n1，n2，…，nk-1，其中ni=pi×qi，并且pi和qi均為大素數(shù)(i=1，2，…，k-1)，將(n，n1，n2，…，nk-1)發(fā)送給Bob。

(6) Bob 隨機選擇k 個整數(shù)(k≥2)，記為x0，x1，…，xk-1，計算y0= xmodn，y1= xmodn1，y2= xmodn2，…， yk-1=，并將(y0，y1，…，yk-1)發(fā)送給Alice。

4.3 方案分析

由于當(dāng)k=2 時，就是經(jīng)典的1 選1 不經(jīng)意傳輸協(xié)議，因此在此就不贅述該方案的具體分析，只對k＞2 的情況進行討論。

(1)正確性分析

定理1:在方程x2modn 中，只要知道該方程的兩個互不同余的解，就可以成功分解大整數(shù)n。

證明:和經(jīng)典的1 選1 不經(jīng)意傳輸協(xié)議一樣，概率型1 選1 不經(jīng)意傳輸協(xié)議的正確性也是建立在歐幾里德算法上的。在概率型1 選1 不經(jīng)意傳輸協(xié)議中，對于每一個發(fā)送給Alice 的y，都可以計算得出4 個平方根±x 和±x‘，當(dāng)Alice發(fā)回給Bob 的一個平方根和Bob 自己選擇的整數(shù)x 不同余時，便可以通過gcd x - x‘，n( ) 來計算得到大整數(shù)n 的一個因子p 或者q，進而成功分解大整數(shù)n；但是當(dāng)發(fā)回的一個平方根和Bob自己選擇的整數(shù)x 同余時，就說明Bob 沒有得到任何新的信息，無法獲取n 的分解。

(2) 概率分析

表1 概率型方案與其他方案的概率對比

(3) 安全性分析

協(xié)議是針對半誠實的敵手，對協(xié)議的安全性分析也只是針對半誠實的敵手。經(jīng)典不經(jīng)意傳輸協(xié)議的安全性依賴于大數(shù)分解難題[2]，因此經(jīng)典不經(jīng)意傳輸協(xié)議的困難性和大數(shù)分解的困難性是等價的。

基于Rabin 的概率型1 選1 不經(jīng)意傳輸協(xié)議其實是經(jīng)典的Rabin 的不經(jīng)意傳輸協(xié)議的推廣，本質(zhì)上是經(jīng)典不經(jīng)意傳輸?shù)姆磸?fù)調(diào)用。其安全性模型和經(jīng)典算法的安全性模型是一致的，基于Rain 的概率型1 選1 不經(jīng)意傳輸協(xié)議的困難性和經(jīng)典不經(jīng)意傳輸協(xié)議的困難性是等價的，基于Rabin 的概率型1 選1 不經(jīng)意傳輸協(xié)議的困難性和大數(shù)分解的困難性也是等價的，所以在安全性方面，基于Rabin 的概率型1 選1 不經(jīng)意傳輸協(xié)議和經(jīng)典的Rabin 不經(jīng)意傳輸協(xié)議是等價的。

因此，基于Rain 的概率型1 選1 不經(jīng)意傳輸協(xié)議是經(jīng)典的Rabin 的不經(jīng)意傳輸協(xié)議的一個安全推廣，基于概率性質(zhì)，方案可以能夠靈活應(yīng)用到復(fù)雜網(wǎng)絡(luò)當(dāng)中。

(4) 效率分析