常泓,吳怡婷,林崧

(1福建師范大學(xué)數(shù)學(xué)與信息學(xué)院,福建 福州 350007;2福建師范大學(xué)數(shù)字福建大數(shù)據(jù)安全技術(shù)研究所,福建 福州 350007;3福建師范大學(xué)數(shù)字福建環(huán)境監(jiān)測物聯(lián)網(wǎng)實(shí)驗(yàn)室,福建 福州 350007)

0 引言

隨著量子技術(shù)的迅速發(fā)展,量子密碼[1]已經(jīng)成為當(dāng)前量子信息領(lǐng)域的一個(gè)重要研究熱點(diǎn)。與經(jīng)典密碼不同,量子密碼的安全基于量子力學(xué)基本原理而非計(jì)算復(fù)雜度,因此它具有理論上的無條件安全性。近年來,人們充分開發(fā)量子力學(xué)特性來解決安全問題,如:密鑰分發(fā)[2-5]、數(shù)字簽名[6]、網(wǎng)絡(luò)編碼[7]、安全多方計(jì)算(SMC)[8-23]等。其中,SMC[8]是密碼學(xué)領(lǐng)域的一個(gè)重要分支,它經(jīng)常被用來構(gòu)建電子選舉、門限簽名以及電子拍賣等復(fù)雜安全系統(tǒng)。目前,研究人員正在試圖利用量子密碼協(xié)議來實(shí)現(xiàn)經(jīng)典安全多方計(jì)算中一些難以解決甚至無法解決的安全任務(wù),并形成了一些新的研究分支,如:量子保密比較[9-13]、量子私密查詢[14-17]、量子安全多方求和(QSMS)[18-23]等。

安全多方求和(SMS)是SMC中的一個(gè)重要分支,它可以用來為其他多方計(jì)算,特別是數(shù)值計(jì)算,建立復(fù)雜的安全協(xié)議。在一個(gè)SMC中,有n個(gè)參與者P1,P2,···,Pn,且每個(gè)參與者Pi都有一個(gè)私密數(shù)據(jù)Mi。它們希望正確地計(jì)算求和函數(shù)f(M1,M2,···,Mn)而不泄露任何一方的私密數(shù)據(jù)。函數(shù)f的結(jié)果可以公開或私下透漏給某個(gè)特定的參與者。2007年,Vaccaro等[18]首次在匿名投票和調(diào)查的量子協(xié)議中提出將經(jīng)典SMS推廣到量子力學(xué)領(lǐng)域的QSMS。在這個(gè)協(xié)議中,每個(gè)參與者通過對各自的粒子進(jìn)行相位旋轉(zhuǎn)操作進(jìn)行投票。然后,所有的參與者都把他們的粒子發(fā)送到計(jì)票人手中。同年,Du等[19]提出了基于非正交態(tài)的量子保密模加方案,允許累加者把一個(gè)數(shù)保密地累加在一個(gè)未知數(shù)上。該方案對于竊取者是漸進(jìn)安全的,n-1方的共謀攻擊不會(huì)使得另一方泄露全部信息。隨后,研究人員利用不同的量子信息處理技術(shù)設(shè)計(jì)一些各具特色的QSMS協(xié)議[20-23],如:量子傅里葉變換、量子隱形傳態(tài)等。

本文利用糾纏交換特性提出了一種QSMS協(xié)議。所提協(xié)議通過半可信的第三方在參與者之間分發(fā)糾纏的Bell態(tài),利用初態(tài)和結(jié)果態(tài)之間的關(guān)系,允許多個(gè)相互不信任的各方安全地計(jì)算其私密數(shù)據(jù)的總和,同時(shí),通過對信號粒子進(jìn)行酉操作來保持其數(shù)據(jù)的私密性。所提協(xié)議不僅可以抵御木馬攻擊,也可以很好地抵御一些常見的外部攻擊和內(nèi)部攻擊。

1 預(yù)備知識

一般來說,Bell態(tài)[24]的形式可表示為

式中x,y∈{0,1},⊕表示加法模2,|0〉和|1〉為單量子比特的一組計(jì)算基。通過對Bell態(tài)上的后一個(gè)粒子進(jìn)行4個(gè)Pauli操作,就可以實(shí)現(xiàn)4個(gè)Bell態(tài)之間的轉(zhuǎn)化,可描述為

式中:t∈ {0,1},U00=I=|0〉〈0|+|1〉〈1|,U01=Z=|0〉〈0|-|1〉〈1|,U10=X=|0〉〈1|+|1〉〈0|,U11=iY=|0〉〈1|-|1〉〈0|為 4 個(gè) Pauli操作。

糾纏交換[25]是目前量子信息領(lǐng)域中實(shí)現(xiàn)信息傳輸?shù)囊环N非常重要的途徑,它是在不同粒子之間測量交換糾纏的過程。糾纏交換可使從未直接發(fā)生相互作用的量子系統(tǒng)產(chǎn)生糾纏,從而達(dá)到實(shí)現(xiàn)信息傳遞的目的。假設(shè)有兩個(gè)EPR對(1,2)和(3,4)分別處于Bell態(tài)|B(a1,b1)〉12和|B(a2,b2)〉34,其中下標(biāo)1、2、3、4表示不同粒子。如果對粒子2和3進(jìn)行Bell測量,得到測量結(jié)果|B(x1,y1)〉23,那么粒子1和4就坍縮到Bell態(tài)|B(a1⊕a2⊕x1,b1⊕b2⊕y1)〉14。將這種情形推廣到n方,可以得到

其中

本文所提出協(xié)議就是以Bell態(tài)為信息載體,利用上述關(guān)系實(shí)現(xiàn)安全多方求和任務(wù)。

2 量子安全四方求和協(xié)議

為了簡便起見,首先對量子安全四方求和協(xié)議進(jìn)行描述,然后再將其推廣到n方。在四方協(xié)議中,假設(shè)有4個(gè)參與者P1、P2、P3和P4,每個(gè)參與者都擁有一個(gè)私密數(shù)據(jù)其中L表示秘密字符串的長度,4個(gè)參與者在一個(gè)半可信的第三方P0的協(xié)助下,通過下述步驟實(shí)現(xiàn)安全求和任務(wù)。

步驟一:P0制備5個(gè)長度為L+R的Bell態(tài)鏈其中上標(biāo)j=1,2,···,L+R表示Bell態(tài)鏈中粒子的順序,下標(biāo)表示粒子,ti=0,1由P0隨機(jī)確定。將每條鏈中第k個(gè)粒子取出,形成粒子序列Sk,k=1,2,···,10。這樣,P0就得到10個(gè)有序的粒子序列S1,S2,···,S10。然后,如圖1(a)所示,P0在4個(gè)參與者之間分發(fā)這些粒子序列。具體地,他將粒子序列S2和S3發(fā)送給P1,S4和S5發(fā)送給P2,S6和S7發(fā)送給P3,S8和S9發(fā)送給P4,并將S1和S10保留在自己手中。

步驟二:在Pi(i=1,2,3,4)接收到各自的粒子序列后,Pi分別從粒子序列S2i和S2i+1中隨機(jī)選取R/2個(gè)粒子來檢測傳輸是否安全。首先,Pi隨機(jī)選擇基或基對手中的檢測粒子進(jìn)行測量。然后,Pi公布檢測粒子的位置,并要求P0公布相應(yīng)Bell態(tài)的初態(tài)。最后,Pi要求與之共享Bell態(tài)的Pi-1和Pi+1用相同的基測相對應(yīng)的粒子,并公布測量的結(jié)果。Pi檢查這些測量結(jié)果是否相關(guān)。如果錯(cuò)誤率超過某一閾值,協(xié)議將被終止,并從步驟一重新開始,否則協(xié)議會(huì)繼續(xù)。這里,閾值是由參與者們事先協(xié)商設(shè)定,主要與實(shí)際的量子信道噪聲情形和協(xié)議要求的具體安全級別有關(guān)。

步驟三:所有參與者丟棄手中粒子序列Sj中的檢測粒子,得到新的粒子序列參與者Pi(i=1,2,3,4)根據(jù)自己的私有數(shù)據(jù)Mi,對粒子序列中的剩余粒子進(jìn)行編碼操作,j=1,2,···,L。

步驟四:Pi(i=1,2,3,4)對手中的粒子序列和中的第j個(gè)粒子進(jìn)行Bell基測量[如圖1(b)所示],并記錄測量結(jié)果與此同時(shí),P0對手中的粒子序列和中的第j個(gè)粒子進(jìn)行Bell基測量,并記錄測量結(jié)果

步驟五:P0要求4個(gè)參與者按照隨機(jī)的順序公布他們的測量結(jié)果。然后,他利用(4)式很容易計(jì)算出

圖1 四方協(xié)議。(a)P0在四方之間分發(fā)粒子序列;(b)Pi(i=1,2,3,4)對序列和的第 j個(gè)粒子執(zhí)行Bell基測量Fig.1 Four-party protocol.(a)P0distributes particle sequences among four participants;(b)Pi(i=1,2,3,4)performs Bell base measurements on the j-th particle of sequence and

3 安全分析

在本節(jié)中,將對所提協(xié)議的安全性進(jìn)行討論。通過對常見的外部攻擊和內(nèi)部攻擊的分析,表明所提協(xié)議在理論上是安全的。

3.1 外部攻擊

外部攻擊者的目的是竊取參與者的私密輸入。雖然在步驟五中參與者公開了他的測量結(jié)果,但這個(gè)測量結(jié)果與他的編碼操作是無關(guān)的。這是因?yàn)榫幋a操作針對參與者Pi對手中粒子序列中的粒子進(jìn)行操作,與參與者Pi對手中粒子序列和Bell測量結(jié)果無直接關(guān)系,即根據(jù)這個(gè)結(jié)果無法獲得關(guān)于編碼操作的任何信息。這就意味著,為了獲得秘密,外部攻擊者將不得不對傳輸中的信號粒子進(jìn)行攻擊。然而,這也是不可行的,具體分析如下:外部攻擊者的攻擊只能發(fā)生在P0向Pi傳送粒子的過程中,但在Pi接收到粒子后對任意信號粒子序列都會(huì)進(jìn)行步驟二中傳輸過程的檢測。當(dāng)外部攻擊者對傳輸粒子進(jìn)行攻擊時(shí),就會(huì)破壞粒子之間的相關(guān)性,必然導(dǎo)致錯(cuò)誤而被參與者發(fā)現(xiàn)。因此,外部攻擊者是無法在不引入錯(cuò)誤的情形下竊取私密輸入的,協(xié)議對外部攻擊是安全的。

3.2 半可信第三方P0的攻擊

對P0的攻擊情形進(jìn)行分析。由于他是半可信的,不能與其他參與者勾結(jié)。為了簡單起見,假設(shè)P0希望獲得P2的私有數(shù)據(jù),為了竊取P2的私有數(shù)據(jù),P0必須識別P2在他的粒子序列上執(zhí)行了怎樣的操作。由于P0將Bell態(tài)發(fā)送出去后,粒子就在P2手中,沒有被傳送回去,所以P0無法獲得P2的操作。另外,根據(jù)測量結(jié)果,P0也無法推得P2的操作。因此,為竊取P2的秘密信息,P0必須對合法信號粒子進(jìn)行攻擊。

在這種情況下,P0常見的攻擊策略是制備7組Bell態(tài)序列,分別將其中的一組粒子序列代替合法的信號粒子序列傳給參與者。如圖2所示。然后,當(dāng)參與者對手中的兩個(gè)粒子序列進(jìn)行相應(yīng)的Bell測量后,P0也對他手中的2個(gè)粒子序列進(jìn)行相應(yīng)的Bell測量,這樣就實(shí)現(xiàn)了糾纏交換。當(dāng)P2公布測量結(jié)果后,P0就可以根據(jù)他的測量結(jié)果以及2個(gè)Bell態(tài)的初態(tài)推得P2的操作,這就意味著P0可以竊取P2的秘密信息。但是,這種攻擊將在竊聽檢測中被發(fā)現(xiàn)。因?yàn)?P1手中的粒子序列S3中的第j個(gè)粒子和P2的粒子序列S4中的第j個(gè)粒子并不處于一個(gè)真正的Bell態(tài),P0可以對粒子序列對和進(jìn)行相應(yīng)的Bell基測量,這就使得粒子序列對(S3,S4)和(S5,S6)坍縮為某一Bell態(tài),并根據(jù)測量結(jié)果公布一個(gè)假消息以此來躲避竊聽。然而,在所提協(xié)議中粒子初態(tài)只能為|B00〉或|B11〉,而粒子序列對(S3,S4)和(S5,S6)將以隨機(jī)等概率坍縮為4個(gè)Bell態(tài)之一,故有1/4的概率被檢測出來。因此,該種攻擊策略也不可行。此外,由于在本攻擊中錯(cuò)誤率達(dá)到25%,故步驟二中的閾值應(yīng)設(shè)置為小于0.25。

圖2 半可信第三方攻擊Fig.2 The semi-trusted third party’s attack

3.3 不誠實(shí)參與者的攻擊

在一個(gè)n方協(xié)議中,由于每個(gè)參與者都要獲得計(jì)算的結(jié)果,因此如果有n-1個(gè)不誠實(shí)的參與者,那么顯然這n-1個(gè)參與者根據(jù)這些信息和自己的輸入很容易推得另一個(gè)誠實(shí)參與者的秘密。同理,如果有n-k個(gè)不誠實(shí)的參與者共謀攻擊,他們顯然可以獲得剩余k個(gè)誠實(shí)參與者私密數(shù)據(jù)的和,因此這些情況是平凡的。

在討論多個(gè)參與者聯(lián)合攻擊的情況時(shí),主要考慮除了這部分信息以外的其他秘密信息。例如,在四方協(xié)議中,假設(shè)P1和P3是不誠實(shí)的,他們顯然能獲得P2和P4秘密的異或和。協(xié)議的關(guān)鍵是防止他們獲得P2或P4的秘密,接下來對這種情況進(jìn)行簡要分析。

顯然,P1和P3聯(lián)合竊取P2的秘密比P4的容易,由于P1和P3都是不誠實(shí)的參與者,為了竊取P2的信息他們不對自己手中的粒子序列進(jìn)行Bell基測量,如圖3所示。P2作為誠實(shí)的參與者,他在步驟三中對粒子序列S5執(zhí)行酉操作,并對粒子序列S4的第j個(gè)粒子和S5的第j個(gè)粒子進(jìn)行Bell基測量,然后公布測量結(jié)果隨之,P1的粒子序列S3的第j個(gè)粒子和P3的粒子序列S6的第j個(gè)粒子將坍縮為一個(gè)新的Bell態(tài),P1和P3可以對粒子S3序列的第j個(gè)粒子和S6序列的第j個(gè)粒子進(jìn)行Bell基測量。在這種情況下,如果兩個(gè)不誠實(shí)的參與者知道粒子序列對(S3,S4)和(S5,S6)的初態(tài),他們就可以根據(jù)測量結(jié)果和糾纏交換關(guān)系式推出P2的私密數(shù)據(jù)。然而這些粒子的初態(tài)始終只有P0知道,即使P1和P3聯(lián)合攻擊,也無法獲得P2的私密數(shù)據(jù)。因此,所提協(xié)議可以很好地抵御不誠實(shí)參與者的共謀攻擊。

圖3 一些不誠實(shí)參與者的聯(lián)合攻擊。(a)P0在四方之間分發(fā)粒子序列;(b)P2對序列S4和S5的第 j個(gè)粒子執(zhí)行Bell基測量Fig.3 The collusion attack of some dishonest participants.(a)P0distributes particle sequences among four participants;(b)P2performs Bell base measurements on the j-th particle of sequence S4and S5

4 多方協(xié)議

把協(xié)議推廣到n方。假設(shè)有n個(gè)參與者Pi(i=1,2,···,n),每個(gè)參與者有一個(gè)私密數(shù)據(jù)Mi=他們在半可信第三方P0的協(xié)助下可以安全地計(jì)算出的結(jié)果,其中:L是每個(gè)私有數(shù)據(jù)字符串的長度。協(xié)議步驟如下。

步驟一:P0制備n+1個(gè)長度為L+R的Bell態(tài)鏈其中上標(biāo)j=1,2,···,L+R表示Bell態(tài)鏈中粒子的順序,下標(biāo)表示粒子,ti=0,1由P0隨機(jī)確定。將每條鏈中第k個(gè)粒子取出,形成粒子序列Sk,k=1,2,···,2(n+2)。這樣,P0就得到2(n+2)個(gè)有序的粒子序列S1,S2,···,S2n+1,S2n+2。然后,P0在n個(gè)參與者之間分發(fā)這些粒子序列。具體地,他將粒子序列S2i和S2i+1發(fā)送給Pi,并將粒子序列S1和S2n+2保留在自己手中(i=1,2,···,n)。

步驟二:在Pi(i=1,2,···,n)接收到各自的粒子序列后,Pi分別從粒子序列S2i和S2i+1中隨機(jī)選取R/2個(gè)粒子來檢測傳輸是否安全。首先,Pi隨機(jī)選擇{|+〉,|-〉}基或{|0〉,|1〉}對手中的檢測粒子進(jìn)行測量;然后,Pi公布檢測粒子的位置,并要求P0公布相應(yīng)Bell態(tài)的初態(tài);最后,Pi要求與之共享Bell態(tài)的Pi-1和Pi+1用相同的基測相對應(yīng)的粒子,并公布測量的結(jié)果。Pi檢查這些測量結(jié)果是否相關(guān)。如果錯(cuò)誤率超過某一閾值,協(xié)議將被終止,并從步驟一重新開始,否則協(xié)議會(huì)繼續(xù)。

步驟三:所有參與者丟棄手中粒子序列Sj中的檢測粒子,得到新的粒子序列參與者Pi根據(jù)自己的私密數(shù)據(jù)Mi,對粒子序列中的第j個(gè)粒子進(jìn)行編碼操作,j=1,2,···,L?？傊?Pi對手中的粒子序列執(zhí)行操作。

步驟四:Pi(i=1,2,···,n)對手中的粒子序列和中的第j個(gè)粒子進(jìn)行Bell基測量,記錄測量結(jié)果與此同時(shí),P0對手中的粒子序列和中的第j個(gè)粒子進(jìn)行Bell基測量,并記錄測量結(jié)果

步驟五:P0要求n個(gè)參與者按照隨機(jī)的順序公布他們的測量結(jié)果。然后,P0計(jì)算

即n個(gè)參與者的私有數(shù)據(jù)串Mi中的第j個(gè)私有數(shù)據(jù)之和并將該結(jié)果告訴參與者。這樣,n個(gè)參與者就可以在不公布私密輸入的前提下獲得求和結(jié)果。

5 結(jié)論

提出了一個(gè)利用Bell態(tài)糾纏交換來實(shí)現(xiàn)多方安全求和的量子協(xié)議。協(xié)議中半可信第三方P0負(fù)責(zé)制備Bell態(tài)并將這些信號粒子發(fā)送給每個(gè)參與者。然后,根據(jù)各自的私密數(shù)據(jù),每個(gè)參與者對信號粒子進(jìn)行相應(yīng)的編碼操作,并通過Bell基測量實(shí)現(xiàn)糾纏交換。最后,P0利用測量結(jié)果和信號粒子的初態(tài)推得這些私密數(shù)據(jù)的異或和。對協(xié)議中一些常見內(nèi)部和外部攻擊下的分析表明所提協(xié)議在理論上是安全的。同時(shí),由于信號粒子在信道中僅進(jìn)行一次單向傳輸,常見的物理攻擊(如木馬攻擊[26,27])對所提協(xié)議也是無效的。此外,除檢測粒子外,協(xié)議利用一組Bell態(tài)來計(jì)算兩個(gè)經(jīng)典比特的異或和,與現(xiàn)有一些QSMS協(xié)議[18-23]相比,所提協(xié)議取得了更高的效率。另一方面,與這些協(xié)議相比,所提出協(xié)議僅要求參與者具有單粒子酉操作和Bell基測量的能力,可行性也更高。當(dāng)然,本協(xié)議在執(zhí)行過程中每個(gè)參與者都需要將多個(gè)粒子高效地存儲(chǔ)在本地,即要求參與者具有量子存儲(chǔ)能力,這在目前的實(shí)驗(yàn)水平下仍是困難的,因此如何設(shè)計(jì)一個(gè)在現(xiàn)有技術(shù)條件下可行的多方安全求和量子協(xié)議(如:無需量子存儲(chǔ)等)將是下一步研究的主要工作之一。