權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議*

張辰旭 張艷碩 張黎仙

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

1 引言

不經(jīng)意傳輸協(xié)議[1],是一種可保護(hù)雙方隱私的通信協(xié)議,它在一個(gè)消息集合中以一種不經(jīng)意的方式來(lái)“秘密”獲取部分消息。

不經(jīng)意傳輸協(xié)議保證了接收者在不知道發(fā)送者隱私的情況下獲取秘密消息,同時(shí)保證了接收者自身的隱私不被發(fā)送者知道,因此不經(jīng)意傳輸協(xié)議可以作為單獨(dú)的協(xié)議應(yīng)用到數(shù)字產(chǎn)品交易、電子選舉方案等諸多信息交易中,還可以作為密碼模塊應(yīng)用到眾多安全多方計(jì)算當(dāng)中。

不經(jīng)意傳輸?shù)母拍钭畛跤蒖abin[2]在1981年提出,從此以后不經(jīng)意傳輸協(xié)議逐漸成為了密碼學(xué)的一個(gè)重要組成部分,隨著學(xué)者研究的不斷深入,諸多的不經(jīng)意傳輸協(xié)議相繼問(wèn)世。 具體可分為以下4 類:1 選1 不經(jīng)意傳輸協(xié)議[2-3]、2 選1 不經(jīng)意傳輸協(xié)議[4]、n 選1 不經(jīng)意傳輸協(xié)議[5]、n 選k 不經(jīng)意傳輸協(xié)議[6-7]。

在Rabin 之后,Even[8]提出了一個(gè)2 選1 不經(jīng)意傳輸協(xié)議,后來(lái)Brassard[5]將2 選1 不經(jīng)意傳輸協(xié)議推廣到了n 選1 不經(jīng)意傳輸協(xié)議,即發(fā)送者發(fā)送n 條消息,接收者僅能獲取其中的1 條消息,并且發(fā)送者不知道接收者選擇的是哪條消息。 Naor 和Pinkas[9]基于Diffie-Hellman 假設(shè)提出了第一個(gè)n 選1 不經(jīng)意傳輸協(xié)議,同時(shí)它也是一個(gè)可復(fù)用的n 選1 不經(jīng)意傳輸協(xié)議。

在本文中,我們提出了權(quán)重型不經(jīng)意傳輸協(xié)議的概念,并對(duì)經(jīng)典的n 選1 不經(jīng)意傳輸協(xié)議Naor 方案進(jìn)行了研究分析,將接收者以固定概率接收發(fā)送者消息進(jìn)行了改進(jìn),新的方案可以根據(jù)接收者的實(shí)際需求設(shè)置相應(yīng)的權(quán)重進(jìn)行獲取。而這種形式也滿足了我們?cè)趶?fù)雜網(wǎng)絡(luò)環(huán)境中的多樣化需求, 更好地適應(yīng)目前復(fù)雜網(wǎng)絡(luò)環(huán)境中不經(jīng)意傳輸協(xié)議的信息傳輸需求。

2 不經(jīng)意傳輸協(xié)議簡(jiǎn)介

不經(jīng)意傳輸?shù)母拍钣蒖abin[2]在1981 年提出后,不經(jīng)意傳輸協(xié)議逐漸成為了密碼學(xué)的一個(gè)重要組成部分,隨著學(xué)者研究的不斷深入,諸多的不經(jīng)意傳輸協(xié)議相繼問(wèn)世。 按照功能具體分為以下4 類經(jīng)典不經(jīng)意傳輸協(xié)議:1 選1 不經(jīng)意傳輸協(xié)議[2-3]、2 選1 不經(jīng)意傳輸協(xié)議[4]、n 選1不經(jīng)意傳輸協(xié)議[5]、n 選k 不經(jīng)意傳輸協(xié)議[6-7]。 具體介紹如下:

(1)1 選1 不經(jīng)意傳輸協(xié)議:發(fā)送方將一條消息傳送給接收方,接收方有1/2 的概率接收成功,而發(fā)送方不知道接收方是否接收成功;

(2)2 選1 不經(jīng)意傳輸協(xié)議:信息的發(fā)送方持有的消息集合包含兩個(gè)秘密信息,接收方可以且僅可以成功恢復(fù)其中一條秘密信息,同時(shí)發(fā)送方并不知道他成功恢復(fù)的是哪一條秘密消息;

(3)n 選1 不經(jīng)意傳輸協(xié)議:信息的發(fā)送方持有的消息集合包含n 個(gè)秘密信息,而接收方在協(xié)議執(zhí)行完畢后只能成功恢復(fù)其中一個(gè)秘密信息,同時(shí)發(fā)送方并不知道他成功恢復(fù)的是哪一條秘密消息;

(4)n 選k 不經(jīng)意傳輸協(xié)議:信息的發(fā)送方持有的消息集合包含n 個(gè)秘密信息,而接收方在協(xié)議執(zhí)行完畢后只能成功恢復(fù)其中k 個(gè)秘密信息,同時(shí)發(fā)送方并不知道他成功恢復(fù)的是哪k 條秘密消息。

對(duì)于一般性的不經(jīng)意傳輸協(xié)議,要考慮三個(gè)性質(zhì):

(1)正確性:只要發(fā)送方和接收方均遵守協(xié)議,那么執(zhí)行完協(xié)議后接收方可以得到他想要的信息;

(2)發(fā)送發(fā)的安全性:執(zhí)行完協(xié)議后,接收方得不到除了他選擇外的其他任何秘密消息;

(3)接收方的安全性:執(zhí)行完協(xié)議后,發(fā)送方不會(huì)知道他的選擇。

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

本節(jié)將重點(diǎn)介紹n 選1 不經(jīng)意傳輸協(xié)議的發(fā)展歷程和最新進(jìn)展以及兩個(gè)經(jīng)典的n 選1 不經(jīng)意傳輸協(xié)議方案。

我們首先介紹一般的n 選1 不經(jīng)意傳輸協(xié)議。 Brassard[5]在2 選1 不經(jīng)意傳輸協(xié)議的基礎(chǔ)上推廣到了n 選1 不經(jīng)意傳輸協(xié)議,其具體概念為:發(fā)送方有n 個(gè)消息s1,s2,…,sn,接收方通過(guò)選擇i∈{1,2…,n} 的值來(lái)獲得消息si,但卻不知道其他的秘密消息sj(j≠i),或者這些sj(j≠i) 的組合消息,同時(shí)發(fā)送方也不知道接收方具體的選擇i,即獲取的是哪一條消息。

在獨(dú)立的n 選1 不經(jīng)意傳輸協(xié)議被設(shè)計(jì)出來(lái)之前,要實(shí)現(xiàn)n 選1 不經(jīng)意傳輸協(xié)議的功能就要通過(guò)多次執(zhí)行2 選1 不經(jīng)意傳輸協(xié)議來(lái)實(shí)現(xiàn),因此這些不同形式的不經(jīng)意傳輸協(xié)議之間是可以相互轉(zhuǎn)化的,但是這樣的協(xié)議構(gòu)造往往會(huì)造成很高的通信代價(jià),因此人們將研究n 選1 不經(jīng)意傳輸協(xié)議的主要精力放在了直接設(shè)計(jì)獨(dú)立的n選1 不經(jīng)意傳輸協(xié)議。

Naor 和Pinkas[9]提出了第一個(gè)獨(dú)立的n 選1 不經(jīng)意傳輸協(xié)議,該協(xié)議是一個(gè)基于Diffie-Hellman 假設(shè)并且可復(fù)用的n 選1 不經(jīng)意傳輸協(xié)議,大大減少了為實(shí)現(xiàn)n 選1 不經(jīng)意傳輸功能而多次執(zhí)行2 選1 不經(jīng)意傳輸協(xié)議的通信代價(jià);后來(lái)Tzeng[10]基于Diffie-Hellman 假設(shè)也提出了一個(gè)n 選1 的不經(jīng)意傳輸協(xié)議,它沒(méi)有初始化階段, 但它的傳輸階段效率還不如Naor 的協(xié)議;2006 年葉君曜[11]等人基于門限思想提出了一個(gè)可復(fù)用的n 選1 的不經(jīng)意傳輸協(xié)議;2008 年,張京良[12]等人對(duì)Naor 方案進(jìn)行了改進(jìn)并應(yīng)用到群簽名當(dāng)中;2015 年,Shin-Yan Chiou[13]等人提出了一種基于離散對(duì)數(shù)問(wèn)題(DLP)的代理簽名n 選1 的不經(jīng)意傳輸方案,它結(jié)合了代理簽名和不經(jīng)意簽名的優(yōu)點(diǎn),滿足了兩種簽名的安全特性,由于該協(xié)議提供了收件人選擇的模糊性,它非常適用于電子投票應(yīng)用;2019 年,邱錫彥和陳俊名[14]兩人首先提出了一種基于不經(jīng)意傳輸?shù)膎 選1 不經(jīng)意傳輸簽名方案,不僅滿足了完整性、不可偽造性、隱私性的安全要求,而且還滿足了選擇限制和非重復(fù)性的要求,使得這種方案非常適合于多選電子投票的應(yīng)用,并在手機(jī)上實(shí)現(xiàn)了該方案,使用戶能夠安全、方便地進(jìn)行投票;在一些車聯(lián)網(wǎng)(VANET)技術(shù)的特征匹配中,用戶的隱私泄露問(wèn)題已經(jīng)嚴(yán)重威脅到人身安全并造成了相當(dāng)大的經(jīng)濟(jì)損失,2020 年WangXianmin[15]等人構(gòu)建了一個(gè)高效的OT 協(xié)議,被采用來(lái)給出一個(gè)帶有平等測(cè)試的PSI 協(xié)議,VANET 的兩方可以獲得他們的特征集的交集,而這種交集之外的任何信息都是不可用的。 因此,內(nèi)部攻擊者無(wú)法從雙方的特征匹配中獲得任何有用的信息,雙方也無(wú)法獲得對(duì)方的額外數(shù)據(jù);2020 年3 月,Wahaballa Abubaker[16]等人提出了一個(gè)安全的n 選1 不經(jīng)意傳輸協(xié)議,該協(xié)議具有隱藏的訪問(wèn)控制和基于確定性有限自動(dòng)機(jī)(DFA)的功能加密的外包解密(HACOT-DFA),可以應(yīng)用在車輛傳感器中,傳感器的數(shù)據(jù)被處理并以記錄的形式存儲(chǔ)在車載傳感器數(shù)據(jù)庫(kù)中,這些記錄可以被其他車輛或路邊單位訪問(wèn)和共享,目的是提高道路安全。 然而,這些記錄可能包含非常敏感的信息,如車輛的識(shí)別碼和位置,這些信息需要特別的保護(hù),而該協(xié)議就確保了車輛用戶的隱私和保密性;2020 年6 月,WangXiaotian[17]等人在ECDH 的假設(shè)下,設(shè)計(jì)了一種新型的n 選1 不經(jīng)意傳輸協(xié)議。 該協(xié)議可以在惡意模式下安全實(shí)現(xiàn),在n 個(gè)輸入值中選擇其中的1 個(gè)。 在此假設(shè)下定義了RAND 函數(shù),并給出了安全定義,構(gòu)建了發(fā)送方和接收方的安全交互模式。 最后分析了該協(xié)議的正確性,并給出了安全證明。 該協(xié)議具有常數(shù)級(jí)的交互復(fù)雜度,計(jì)算和通信復(fù)雜度只與n 線性有關(guān);2020 年8 月,Nibedita Kundu[18]等人利用多變量公鑰密碼學(xué)(MPKC)的OT 協(xié)議的構(gòu)造,提出了一個(gè)2 選1 的不經(jīng)意傳輸協(xié)議,而我們可以進(jìn)行n 次的復(fù)用以實(shí)現(xiàn)n 選1 不經(jīng)意傳輸?shù)墓δ?該方案的安全性是在多變量二次方(MQ)問(wèn)題的硬度下實(shí)現(xiàn)的,該設(shè)計(jì)是第一個(gè)基于MPKC 的后量子OT 協(xié)議;2020 年9 月,Shanshan Zhang[19-20]利用格上不經(jīng)意傳輸協(xié)議的特點(diǎn),設(shè)計(jì)了一個(gè)使用決策性Diffie-Hellman 假設(shè)和混淆不可區(qū)分的基于LWE的n 選1 不經(jīng)意傳輸協(xié)議,該協(xié)議主要的工具包括基于LWE 的雙模式密碼系統(tǒng)和安全的不可區(qū)分性混淆,保證了該n 選1 不經(jīng)意傳輸協(xié)議的安全性;2021 年5 月,Saeid Esmaeilzade[21]等人采用了非對(duì)稱同態(tài)加密的概念,使用了一些著名的同態(tài)加密方案(如RSA、Paillier 和NTRU)來(lái)實(shí)例化他們的結(jié)構(gòu),以獲得具體的不經(jīng)意傳輸協(xié)議,提出了一個(gè)通用的結(jié)構(gòu)來(lái)建立簡(jiǎn)單而高效的n 選1 不經(jīng)意傳輸協(xié)議,該協(xié)議的通用結(jié)構(gòu)在通用可組合框架中是安全的;2021 年11 月,Wang Ping[22]等人在量子信道的幫助下,設(shè)計(jì)了一種新型的計(jì)算安全的量子n 選1 不經(jīng)意傳輸(QOT)協(xié)議,其最低假設(shè)要求是:單向函數(shù)的存在。

獨(dú)立的n 選1 不經(jīng)意傳輸協(xié)議雖然在降低了通信代價(jià)的同時(shí),實(shí)現(xiàn)了相應(yīng)的通信功能,但這種功能是不完善的,因?yàn)樗鼪](méi)有考慮到接收方的實(shí)際需求,因此我們給出了權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議的定義和性質(zhì),并在下一節(jié)提出了具體的設(shè)計(jì)方案,下面我們介紹幾種經(jīng)典的n 選1不經(jīng)意傳輸協(xié)議。

3.1 Naor 方案

本節(jié)對(duì)Naor[7]的n 選1 不經(jīng)意傳輸協(xié)議進(jìn)行描述,具體過(guò)程如下:

初始化:Alice 選擇隨機(jī)數(shù)C1,C2,…,CN-1和r,并計(jì)算(Ci)r和gr的值。Bob可以獲得C1,C2,…,CN-1和gr的值。 其中1 ≤i≤N- 1,g為Zq的生成元。

傳輸階段: Alice 的輸入為 (M0,M1,…MN-1)。 Bob 的輸入為σ∈{0,…N- 1} (他選擇獲取Mσ)。

(1)Bob 選擇k∈Zq,并設(shè)置PKσ=gk。 如果σ≠0,將計(jì)算PK0=Cσ/PKσ,并向Alice 發(fā)送PK0, 并且已經(jīng)可以計(jì)算解密密鑰(gr)k=(PKσ)r;

(2 ) Alice 計(jì) 算 (PK0)r, (PKi)r=(Ci)r/(PK0)r,1 ≤i≤N- 1。 Alice 再選擇隨機(jī)字符串R,通過(guò)計(jì)算H((PKi)r,R,i) ⊕Mi來(lái)加密每個(gè)Mi, 并將這些加密數(shù)據(jù)、R發(fā)送給Bob;

(3) Bob 使 用H((PKσ)r,R,σ), 來(lái) 解 密Mσ。

正確性:主要依賴于方案中的隨機(jī)預(yù)言機(jī)H(通常是一個(gè)哈希函數(shù)),只有在接受到完整的隨機(jī)預(yù)言機(jī)H加密后的數(shù)據(jù)后,才可以對(duì)其進(jìn)行計(jì)算解密。 對(duì)于本方案中的隨機(jī)原語(yǔ)H加密結(jié)果H((PKi)r,R,i), 當(dāng)且僅當(dāng)Bob 知道正確的(PKσ)r、σ以及R才能計(jì)算正確結(jié)果獲得想要的秘密信息。

安全性:在假設(shè)Diffie-Hellman 問(wèn)題難解的情況下,該方案使用的隨機(jī)預(yù)言機(jī)H在Diffie-Hellman 假設(shè)下可以證明其安全性。 由于Bob只能計(jì)算唯一的解密密鑰(PKσ)r=(gr)k,因此也就無(wú)法獲得除了自己選擇的消息外的任意消息,這保證了Alice 的安全性與隱私性。

PK0信息理論上的分布是獨(dú)立于C0,…,CN-1和σ的,與他們的值無(wú)關(guān),僅與他選擇的隨機(jī)數(shù)k有關(guān),而Alice 并不知道具體的隨機(jī)數(shù)k的值。 因此Alice 無(wú)法依據(jù)PK0計(jì)算出相對(duì)應(yīng)的Cσ值,也就無(wú)法得知Bob 想獲得的秘密消息是哪一個(gè)了,這就保證了Bob 的安全性與隱私性。

不經(jīng)意性:接收方發(fā)送給發(fā)送方的PK0參數(shù)僅與他選擇的隨機(jī)數(shù)k有關(guān),而發(fā)送方并不知道具體的隨機(jī)數(shù)k的值。 故接收方將PK0發(fā)送給發(fā)送方后,發(fā)送方無(wú)法依據(jù)PK0計(jì)算出相對(duì)應(yīng)的Cσ值,也就無(wú)法得知σ,也就是接收方想獲得的秘密消息是哪一個(gè)了。

3.2 Tzeng 方案

本節(jié)對(duì)Tzeng[8]的n 選1 不經(jīng)意傳輸協(xié)議進(jìn)行描述,具體過(guò)程如下:

傳輸階段:Alice 的輸入為(M1,M2,…MN∈Gq)。 Bob 的輸入為α∈{1,…N} (他選擇獲取Mσ)。

(1)Bob 計(jì)算y=grhα,r∈RZq,并將其發(fā)送給Alice;

(2) Alice 計(jì)算ci= (gki,Mi(y/hi)ki),ki∈RZq,1 ≤i≤N,并將其發(fā)送給Bob;

(3)設(shè)cα= (a,b),Bob 計(jì)算Mα=b/ar。

正確性:該方案基于DDH 假設(shè),只要Alice和Bob 均遵守協(xié)議,那么執(zhí)行完協(xié)議后Bob 可以得到他想要的信息。

安全性:因?yàn)镈DH 假設(shè)是強(qiáng)于DL 假設(shè)的,因此Bob 不能計(jì)算兩對(duì)不同的(r,α) 和(r′,α′)同時(shí)滿足y=grhα=gr′hα′。 除非Bob 可以計(jì)算loggh= (r′-r)/(α-α′)mod q。 因此,Bob 不能得到除了他選擇得到的秘密消息外的任何一個(gè),這保證了發(fā)送方的安全性與隱私性。

Alice 無(wú)法通過(guò)y=grhα計(jì)算出σ的值,也就無(wú)法得知Bob 想獲得的秘密消息是哪一個(gè)了,這保證了接收方的安全性與隱私性。

不經(jīng)意性:在該方案中沒(méi)有(g,h,Gq) 的初始化,而是Alice 將(g,h,Gq) 一同發(fā)送給Bob。當(dāng)Bob 接收到這些系統(tǒng)參數(shù)后,他需要去檢查一下是否q為素?cái)?shù)、g≠1 和h≠1。 否則,如果Alice 選擇了一個(gè)非素?cái)?shù)q和非常小的g和h,他將會(huì)知道Bob 的選擇σ。 當(dāng)然,在Bob 檢查沒(méi)有問(wèn)題的情況下,即使Alice 知道,Bob 的選擇也是無(wú)條件安全的,Alice 也就無(wú)法知道Bob的選擇了。

4 權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議

本節(jié)重點(diǎn)介紹權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議的定義、性質(zhì)以及權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議方案。

4.1 權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議定義

n 選1 不經(jīng)意傳輸協(xié)議同其他眾多經(jīng)典的不經(jīng)意傳輸協(xié)議一樣,作為通信協(xié)議可以通過(guò)不經(jīng)意的方式,在保護(hù)雙方隱私的情況下達(dá)成獲取信息的目的,并且可以應(yīng)用到數(shù)字產(chǎn)品交易、電子選舉方案等諸多信息交易中,以及眾多安全多方計(jì)算當(dāng)中。 但目前為止的n 選1 不經(jīng)意傳輸協(xié)議都是令接收者獲取信息的概率為固定值,為了更好的拓展應(yīng)用,我們提出了一個(gè)可以根據(jù)接收方實(shí)際需求設(shè)置相應(yīng)權(quán)重的權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議。

權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議是一種在保護(hù)通信雙方隱私的同時(shí),可以讓接收者以一定的權(quán)重成功從秘密消息中恢復(fù)自己想得到的消息的通信協(xié)議,但得不到任何其他的消息或者其他消息的組合形式,同時(shí)發(fā)送者也不知道接收者選擇的是哪一個(gè)消息。

權(quán)重型不經(jīng)意傳輸協(xié)議和概率型不經(jīng)意傳輸協(xié)議[3][12]的區(qū)別在于:概率型的不經(jīng)意傳輸協(xié)議的接收方成功獲取發(fā)送方的各個(gè)消息概率之和為1,比如對(duì)于概率型2 選1 不經(jīng)意傳輸協(xié)議來(lái)說(shuō),若接收方想以概率P獲取秘密信息Mj,那么對(duì)于另一個(gè)秘密信息的獲取概率為1-P;而權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議只能以1/m的權(quán)重獲取所選擇的消息, 而對(duì)于其他消息,由于缺少解密密鑰()r, 故而無(wú)法成功解密,所有消息的獲取概率之和仍為1/m。

4.2 權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議性質(zhì)

結(jié)合一般的n 選1 不經(jīng)意傳輸協(xié)議,權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議具有以下基本性質(zhì):

(1)協(xié)議的正確性:在協(xié)議完成后,如果發(fā)送方和接收方能夠正確執(zhí)行協(xié)議,那么接收方可以通過(guò)協(xié)議以一定的比重正確獲得自己想要獲得的秘密消息。

(2)發(fā)送方的隱私性:執(zhí)行完協(xié)議后,即使是惡意的接收方不能夠遵守協(xié)議內(nèi)容,那么他也無(wú)法獲得其余N- 1 個(gè)秘密消息。

(3)接收方的隱私性:執(zhí)行完協(xié)議后,發(fā)送方無(wú)法以任何方式得知接收方恢復(fù)的是哪一條秘密消息。

4.3 權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議功能

權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議可以根據(jù)接收者的實(shí)際需求設(shè)置相應(yīng)的權(quán)重進(jìn)行獲取,而這種形式的通信代價(jià)并不會(huì)因此而提高,相反還會(huì)優(yōu)于許多一般的n 選1 不經(jīng)意傳輸協(xié)議,因此它能夠在保證自身通信代價(jià)的同時(shí),滿足了我們?cè)趶?fù)雜的網(wǎng)絡(luò)環(huán)境中多樣化的需求。

4.4 權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議的設(shè)計(jì)

表1 符號(hào)說(shuō)明

設(shè)q是一個(gè)大素?cái)?shù),所有的數(shù)據(jù)操作都在一個(gè)以g為生成元的循環(huán)群Zq上進(jìn)行,符合Diffie-Hellman 假設(shè),此外,還假設(shè)存在一個(gè)隨機(jī)預(yù)言機(jī)H(通常是一個(gè)哈希函數(shù))。 方案框架如圖1。

圖1 權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議框架

初始化:Alice 選擇N- 1 個(gè)隨機(jī)常量C1,C2,…,CN-1(滿足公式PK0·PKi=Ci)。 他還選擇了一個(gè)隨機(jī)數(shù)r并計(jì)算gr。C1,…,CN-1和gr的值均被發(fā)送給Bob。 所有傳輸都將使用相同的值。 (Alice 可預(yù)計(jì)算1 ≤i≤N-1 每個(gè)(Ci)r的值)。

(1)Bob 選擇m個(gè)隨機(jī)數(shù)kj(j= 1,2,…,m),并設(shè)置相應(yīng)的m個(gè)=gkj(j= 1,2,…,m)。 如果σ≠0, 他將計(jì)算m個(gè)=Cσ/(j= 1,2,…,m),并將這些值和m一同發(fā)送給Alice,并且已經(jīng)可以計(jì)算解密密鑰(gr)kj= ()r。

然后Alice 隨機(jī)選擇m- 1 種j∈{1,2,…,m} ,對(duì)其對(duì)應(yīng)的(m- 1)×N種()r利用其自身的公鑰pj一一進(jìn)行加密。 沒(méi)有被選擇到的唯一一個(gè)j記為j*。 并對(duì)自身持有的i 個(gè)消息(0 ≤i≤N- 1) 進(jìn)行j 次的復(fù)制(1 ≤j≤m),以形成的消息矩陣,以便后續(xù)的加密操作。Alice 選擇隨機(jī)字符串R。 然后,他通過(guò)計(jì)算H(()r,R,i,j) ⊕來(lái)加密每個(gè),并將這些加密數(shù)據(jù)和R發(fā)送給Bob。

(3) Bob 使用H(()r,R,σ,j) 來(lái)解密。但由于其中的()r有(m-1)×N種都被公鑰加密后的數(shù)據(jù)替代,也就是說(shuō)當(dāng)j取值到Alice 隨機(jī)選擇的m-1 種j∈{1,2,…,m} 中的任意一種都不能成功獲取秘密消息。 只有當(dāng)j取值為沒(méi)有被Alice 選取到的唯一值j*時(shí),才能成功獲取秘密消息。 也就是權(quán)重為1/m。

圖2 加密消息分布

該權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議方案與一般的n 選1 不經(jīng)意傳輸協(xié)議相比,初始化階段并沒(méi)有改動(dòng),而是通過(guò)接收者設(shè)置的權(quán)重將之前單一的加密消息變成m×N的加密矩陣的形式,再通過(guò)發(fā)送方持有公鑰對(duì)部分加密參數(shù)進(jìn)行再加密,接收方通過(guò)新增加密參數(shù)j進(jìn)而實(shí)現(xiàn)了以一定權(quán)重恢復(fù)選擇的秘密消息的功能。

5 三個(gè)性質(zhì)的分析

在本節(jié)重點(diǎn)介紹權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議的正確性分析、安全性分析以及對(duì)比分析。

5.1 正確性分析

對(duì)于權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議來(lái)說(shuō),其正確性主要依賴于方案中的隨機(jī)預(yù)言機(jī)H(通常是一個(gè)哈希函數(shù)),只有在接受到完整的隨機(jī)預(yù)言機(jī)H加密后的數(shù)據(jù)后,才可以對(duì)其進(jìn)行計(jì)算解密。

定理1:對(duì)于H(()r,R,σ,j) 來(lái)說(shuō),當(dāng)且僅當(dāng)知道正確的()r、σ以及j才能計(jì)算正確結(jié)果。

證明:對(duì)于本方案中的隨機(jī)原語(yǔ)H加密結(jié)果H(()r,R,σ,j),當(dāng)且僅當(dāng)接收者知道正確的()r、σ以及j*才能計(jì)算正確結(jié)果獲得想要的秘密信息。 接收者在收到m×N個(gè)加密結(jié)果后,根據(jù)自己事先選擇的消息序號(hào)σ,以及預(yù)先計(jì)算好的解密密鑰()r= (gr)kj, 隨機(jī)選擇j∈{1,2,…,m},將計(jì)算結(jié)果H(()r,R,σ,j) 與該j相對(duì)應(yīng)的加密結(jié)果進(jìn)行模加,如果該j =j*,則可以成功以1/m的權(quán)重獲取該秘密消息。

5.2 安全性分析

對(duì)于第三方來(lái)說(shuō),由于本方案中的隨機(jī)原語(yǔ)H(通常是一個(gè)哈希函數(shù))的存在,所以即使在傳輸過(guò)程當(dāng)中有第三方成功截獲了密文消息,那么也是難以恢復(fù)出秘密信息的。

發(fā)送方的安全性:在假設(shè)Diffie-Hellman 問(wèn)題難解的情況下,該方案使用的隨機(jī)預(yù)言機(jī)H在Diffie-Hellman 假設(shè)下可以證明其安全性。 由于接收方只能計(jì)算唯一的解密密鑰()r=(gr)kj,從而無(wú)法得知其余的N- 1 個(gè)解密密鑰,因此也就無(wú)法獲得除了自己選擇的消息外的任意消息,這保證了發(fā)送方的安全性與隱私性。

要注意的第一點(diǎn)是,如果接收方知道了一個(gè)以上的公共加密參數(shù)PK(例如PKi1和PKi2)的值(PKi1)r和 (PKi2)r, 那么就可以得出(PKi1)r/(PKi2)r=(Ci1/Ci2)r。 這反過(guò)來(lái)可以用來(lái)推導(dǎo)隨機(jī)數(shù)C和隨機(jī)數(shù)gr的Diffie-Hellman值:給定輸入A=ga和B=gb(其中目標(biāo)是計(jì)算gab),模擬器A 通過(guò)生成一個(gè)隨機(jī)數(shù)ri和gr=gb的常量Ci=Ari來(lái)模擬A。 如果A 在i1和i2上成功,則(Ci1/Ci2)r=gabri1/gabri2, 將后者提高到1/(ri1-ri2) 次冪就可以得到gab。

由于我們?cè)趨f(xié)議過(guò)程中使用了相同的C1,C2,…,CN-1和gr對(duì)Naor 方案進(jìn)行了m次復(fù)用生成了加密矩陣,我們應(yīng)該使用模擬器A′對(duì)控制了某些用戶子集的對(duì)手的操作進(jìn)行描述。 因此,隨機(jī)預(yù)言機(jī)H的輸入包含一個(gè)隨機(jī)元素R,它確保協(xié)議的不同調(diào)用中的輸入將不同。 與之前一樣,目標(biāo)是生成模擬器A 感興趣的值(并在理想模型中獲取它們)。 A′ 隨機(jī)選擇C1,C2,…,CL-1以及gr。 當(dāng)模擬器A 發(fā)送第m個(gè)消息時(shí),A′ 以(α0,α2,…,αN-1) 隨機(jī)進(jìn)行響應(yīng),用于加密Mi和隨機(jī)字符串Rm。 每當(dāng)A 在點(diǎn)(x,R′,σ,m) 上查詢H時(shí),A′都會(huì)檢查對(duì)于某些m是否滿足R′=Rm。 如果沒(méi)有,則給出一個(gè)隨機(jī)的答案,如果R′=Rm并且x=()r,則A′在理想模型中詢問(wèn)與σ對(duì)應(yīng)的值,并得到Mσ。 然后,它必須適當(dāng)?shù)卦O(shè)置H(()r,Rm,σ,m)=ασ⊕。 模擬的A 看到的分布和真實(shí)的分布之間的唯一區(qū)別發(fā)生在:

(2)提前查詢其中一個(gè)H(x,Rm,σ,m), 但對(duì)于每個(gè)查詢,這種情況發(fā)生的可能性很低。

需要注意的第二點(diǎn)是,如果該協(xié)議使用普通的ElGamal 加密而不是隨機(jī)的預(yù)言機(jī),那么該協(xié)議將是不安全的:假設(shè)轉(zhuǎn)移的形式為()r·,()r·。 然后,如果接收者事先知道其中一個(gè)傳輸?shù)脑?例如,), 即使他知道另一個(gè)元素的私鑰,他也可以從加密的消息中計(jì)算出相應(yīng)的加密密鑰()r。 因此,他可以計(jì)算()r和()r,將它們相乘并得到(Ci)r。此值使他能夠在每次其他傳輸中解密這兩個(gè)元素。

5.3 不經(jīng)意性分析

定理2:不經(jīng)意性也指一種模糊化的方式,具體是指發(fā)送方在整個(gè)協(xié)議的執(zhí)行過(guò)程中不會(huì)知道接收方具體選擇的是哪一個(gè)秘密消息。

6 對(duì)比分析

Naor[9]方案是一個(gè)基于Diffie-Hellman 假設(shè)的,并可復(fù)用的n 選1 不經(jīng)意傳輸協(xié)議,也是第一個(gè)真正意義上的n 選1 不經(jīng)意傳輸協(xié)議。 我們的方案就是基于Naor 方案進(jìn)行設(shè)計(jì)的,理論上對(duì)Naor 方案進(jìn)行了m次的復(fù)用并加以改進(jìn),但我們的初始化次數(shù)與傳輸階段只執(zhí)行一次,因此整個(gè)傳輸過(guò)程僅需進(jìn)行兩次信息的傳遞,而不是2m次,同時(shí)也避免了多次的初始化,增加計(jì)算量與通信負(fù)擔(dān),使其不較為刻板。

在Naor 提出他的n 選1 不經(jīng)意傳輸協(xié)議之后,Tzeng[10]也提出了一個(gè)方案基于Diffie-Hellman 假設(shè)的n 選1 不經(jīng)意傳輸協(xié)議,但他省去了初始化階段,相反地導(dǎo)致他的傳輸階段效率大大降低,比Naor 的還要低,同理在一定的條件下也要低于我們的權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議。

葉君曜等人[11]提出了可復(fù)用的基于門限思想的n 選1 不經(jīng)意傳輸協(xié)議,同樣僅僅進(jìn)行一次初始化即可完成多次的復(fù)用,他的安全性來(lái)自于shamir 門限方案的安全性。 在方案的效率通用性上,我們對(duì)其的傳輸階段輪數(shù)、是否初始化、安全性基礎(chǔ)以及相應(yīng)功能做了簡(jiǎn)單的對(duì)比,見(jiàn)表2。

表2 權(quán)重型方案與其他方案的對(duì)比

接下來(lái)我們將對(duì)我們的權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議、Naor 方案、Tzeng 方案以及葉君曜方案在協(xié)議的計(jì)算量與通信量上進(jìn)行對(duì)比分析。表3 給出了初始化階段的各方案在計(jì)算量和通信量上的對(duì)比、表4 給出了傳輸階段的各方案在計(jì)算量和通信量上的對(duì)比。

表3 初始化階段

表4 傳輸階段

由此可見(jiàn),我們的權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議初始化階段的計(jì)算量和通信量并沒(méi)有變化,并且小于葉君曜方案。

由此可見(jiàn),傳輸階段即使因?yàn)閷?shí)現(xiàn)以可變化的權(quán)重獲取信息的功能而增加了通信量,但是在一定的條件下,即素?cái)?shù)q p的情況下,我們的協(xié)議在傳輸階段的通信量是明顯小于葉君曜和Tzeng 方案的,因此我們的協(xié)議效率也是明顯要高于他們的。

7 權(quán)重型n 選1 不經(jīng)意傳輸舉例

在本節(jié)中,將用一個(gè)例子來(lái)解釋權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議。

例:假設(shè)Alice 有9 個(gè)秘密消息(M0,M1,…,M8),Bob 想以1/3 的權(quán)重獲得第7 個(gè)消息M6。

初始化:Alice 選擇8 個(gè)隨機(jī)常量C1,…,C8,隨機(jī)數(shù)r,并計(jì)算gr,(Ci)r,1 ≤i≤8。 將C1,…,C8和gr發(fā)送給Bob;

傳輸階段:

(1)Bob 選擇3 個(gè)隨機(jī)數(shù)k1,k2,k3, 并計(jì)算以及與之相對(duì)應(yīng)的

圖3 3 × 9 的加密參數(shù)矩陣

Alice 選擇隨機(jī)字符串R, 計(jì)算H(()r,R,i,j)⊕生成3× 9 的加密消息矩陣,將其和R發(fā)送給Bob;加密消息矩陣如圖4。

圖4 3 × 9 的加密消息矩陣

(3) Bobs 選擇j= 2, 又已知()r=(gr)k2、R、i= 6,因?yàn)閖=j*。 因此成功以1/3的權(quán)重解密第7 個(gè)消息M6。

通過(guò)舉例,我們可以總結(jié)出:本協(xié)議通過(guò)靈活的變形成功實(shí)現(xiàn)了以一定權(quán)重成功獲取秘密消息的功能,以此我們可以推廣應(yīng)用到現(xiàn)實(shí)生活的多個(gè)場(chǎng)景,如不經(jīng)意的網(wǎng)上訂購(gòu),消費(fèi)者可能不愿意暴露其購(gòu)買的某些商品( 如某些藥品) ;線上線下購(gòu)物平臺(tái)中,商家設(shè)置獎(jiǎng)品抽獎(jiǎng)環(huán)節(jié),可以根據(jù)獎(jiǎng)品等級(jí)高低固定相應(yīng)權(quán)重的數(shù)值,等級(jí)越高權(quán)重越低,等級(jí)越低權(quán)重越高,同時(shí)為了保護(hù)中獎(jiǎng)?lì)櫩偷碾[私,該協(xié)議可保證商家無(wú)法得知幾號(hào)顧客中了幾號(hào)獎(jiǎng)品。

8 權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議的實(shí)現(xiàn)

本節(jié)是對(duì)前文權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議的設(shè)計(jì)實(shí)現(xiàn),介紹了基于權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議的編程實(shí)現(xiàn),主要包括開(kāi)發(fā)工具、運(yùn)行環(huán)境介紹和權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議的功能實(shí)現(xiàn)。

8.1 開(kāi)發(fā)工具及運(yùn)行環(huán)境

本協(xié)議的實(shí)現(xiàn)采用IntelliJ IDEA Community Edition 2020.3.1 x64 作為技術(shù)平臺(tái)與開(kāi)發(fā)工具。

本程序在jdk1.8.0_131 版本、Windows 環(huán)境下運(yùn)行。

8.2 權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議功能模塊

本小節(jié)主要介紹權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議實(shí)現(xiàn)的各功能模塊和相關(guān)的功能測(cè)試。

8.2.1 測(cè)試功能模塊

我們Alice 的消息合集和Bob 的選擇以及權(quán)重等參數(shù)的設(shè)置均是在次模塊進(jìn)行。 如圖5所示,我們的消息合集為{2018,2019,2020,2021,2022},也就是n=5,Bob 的選擇σ=5,權(quán)重的設(shè)置為1/m= 1/2,選擇j= 2。

圖5 測(cè)試功能的參數(shù)設(shè)置

8.2.2 發(fā)送方功能模塊

我們通過(guò)for 循環(huán)生成了隨機(jī)常量C1,C2,…,CN-1和gr,如圖6 所示。

圖6 初始化隨機(jī)常量的生成

如圖7 所示,該部分完成了發(fā)送方的系列加密。 具體加密細(xì)節(jié)請(qǐng)見(jiàn)4.4 中傳輸階段的第2步。 最終發(fā)送方通過(guò)計(jì)算H(()r,R,i,j) ⊕來(lái)加密每個(gè)。

圖7 發(fā)送方進(jìn)行加密

8.2.3 接收方功能模塊

如圖8 所示,該部分完成了接收方m個(gè)隨機(jī)數(shù)kj(j=1,2,…,m)和相應(yīng)的m個(gè)=gkj(j= 1,2,…,m)的設(shè)置。 具體細(xì)節(jié)請(qǐng)見(jiàn)章節(jié)4.4中傳輸階段的第1 步。

圖8 接收方對(duì) = gkj 的準(zhǔn)備

如圖9 所示,該部分完成了接收方計(jì)算解密 密鑰(gr)kj= ()r。

圖9 接收方計(jì)算解密密鑰(gr)kj = ()r

如圖10 所示,該部分通過(guò)對(duì)H(()r,R,σ,j) 的計(jì)算完成了對(duì)秘密消息的解密。 具體細(xì)節(jié)請(qǐng)見(jiàn)章節(jié)4.4 中傳輸階段的第3 步。

圖10 接收方對(duì)自己的選擇進(jìn)行解密

8.3 功能測(cè)試

Alice 持有消息集 {2018,2019,2020,2021},共有4 個(gè)秘密消息,也就是n= 4。

Bob 的選擇σ= 2,也就是他的選擇是m2={2019}。

接下來(lái)Bob 設(shè)置權(quán)重為1/m= 1/3,同時(shí)選擇j= 1。

根據(jù)協(xié)議等價(jià)于Bob 通過(guò)計(jì)算H(()r,R,2,1) ⊕來(lái)進(jìn)行解密。 解密結(jié)果如圖11 所示,成功以1/3 的權(quán)重恢復(fù)該秘密消息。

圖11 Bob 成功恢復(fù)秘密信息

此時(shí)Bob 設(shè)置同樣權(quán)重為1/m= 1/3,但選擇j= 2。

根據(jù)協(xié)議等價(jià)于Bob 通過(guò)計(jì)算H(()r,R,2,2) ⊕來(lái)進(jìn)行解密。 解密結(jié)果如圖12 所示,未通過(guò)1/3 的權(quán)重成功恢復(fù)該秘密消息。

圖12 Bob 未成功恢復(fù)秘密信息

Alice 持有消息集{2018,2019,2020,2021,2022},共有5 個(gè)秘密消息,也就是n= 5。

Bob 的選擇σ= 5,也就是他的選擇是m5={2022}。

接下來(lái)Bob 設(shè)置權(quán)重為1/m= 1/2,同時(shí)選擇j= 1。

根據(jù)協(xié)議等價(jià)于Bob通過(guò)計(jì)算H((r,R,5,1) ⊕來(lái)進(jìn)行解密。 解密結(jié)果如圖13 所示,成功以1/2 的權(quán)重恢復(fù)該秘密消息。

圖13 Bob 成功恢復(fù)秘密信息

此時(shí)Bob 設(shè)置同樣權(quán)重為1/m= 1/2,但選擇j= 2。

根據(jù)協(xié)議等價(jià)于Bob 通過(guò)計(jì)算H(()r,R,5,2) ⊕來(lái)進(jìn)行解密。 解密結(jié)果如圖14 所示,未通過(guò)1/2 的權(quán)重成功恢復(fù)該秘密消息。

圖14 Bob 未成功恢復(fù)秘密信息

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

通過(guò)對(duì)已有的不經(jīng)意傳輸協(xié)議概念的研究,提出了權(quán)重型的不經(jīng)意傳輸協(xié)議,使接收方可以選擇一定的權(quán)重獲得自己需要的秘密消息,并對(duì)Naor 的n 選1 不經(jīng)意傳輸協(xié)議進(jìn)行研究,給出了具體的權(quán)重型n 選1 不經(jīng)意傳輸協(xié)議設(shè)計(jì)方案及分析,包括正確性、安全性、不經(jīng)意性分析和對(duì)比分析,滿足了我們?cè)趶?fù)雜的網(wǎng)絡(luò)中根據(jù)實(shí)際需要靈活變化和調(diào)整, 更好地適應(yīng)目前復(fù)雜網(wǎng)絡(luò)環(huán)境中不經(jīng)意傳輸協(xié)議的信息傳輸需求。 最后,我們還進(jìn)行了權(quán)重型n 選1 不經(jīng)意傳輸方案的編程實(shí)現(xiàn)和相關(guān)測(cè)試,證明了權(quán)重型n 選1 不經(jīng)意傳輸在未來(lái)應(yīng)用方面的可能性。