基于量子求和的安全多方量子排序協(xié)議

王蕊聰,馮雁

(1北京電子科技學院網(wǎng)絡空間安全系,北京 100070;2西安電子科技大學,陜西 西安 710126;3中國科學技術大學,安徽 合肥 230026)

0 引言

在安全多方計算執(zhí)行的過程中,計算可能發(fā)生在互不信任甚至互相競爭的多方中,安全多方排序問題是信息保密的安全多方計算的核心問題之一,其主要思想是:假設有n名參與者P1,P2,P3,···,Pn,每個參與者各自擁有一個秘密數(shù)值x1,x2,x3,···,xn,他們希望在沒有可信第三方的情況下,能夠設計出某種計算方式,讓所有參與者參與排序,每個參與者可以安全獲得自己秘密數(shù)值的排名,且排名在各參與者之間也同樣保密的一種安全方案。

目前,國內外圍繞安全多方排序開展了很多研究,取得了不少研究成果。關于傳統(tǒng)多方排序[1?3],大多數(shù)采用了基于比較的排序思想,即文獻[4]中對百萬富翁問題的自然推廣,人們針對這個問題,利用傳統(tǒng)的密碼算法設計了各種能夠提高排序效率的協(xié)議,但卻至少需要nlogn次兩方秘密比較,計算開銷大。文獻[5]提出了隨機化的安全希爾排序,雖然以較高概率成功排序,但該協(xié)議需要執(zhí)行O(log2n)輪,通信和計算開銷較大。也有基于經(jīng)典密碼學的同態(tài)加密[6]體制的保密排序方案,以及基于大數(shù)分解NP問題的RSA密碼體制[7]設計的排序方案,這些方案的安全性主要取決于計算機計算能力的強弱,即隨著攻擊者計算能力的增強,這些方案的安全性也會降低。與基于量子的安全多方排序相比,傳統(tǒng)多方排序方案都存著效率不高或安全性保障不強等問題。

量子密碼與經(jīng)典密碼學對應的許多方面也得到了相應的研究,如量子密鑰分配協(xié)議[8?11]、量子秘密共享協(xié)議[12?14]、量子多方計算協(xié)議[15?18]等。而關于量子化的排序問題,文獻[19]較早提出了利用形變量子化方法進行研究,推導出排序相關分布函數(shù)的一般方法,但只是從理論上分析了利用量子排序的可能性;文獻[20]設計了基于量子隱式模n+1加法的保密排序協(xié)議,但由于用到了特殊濾光器以避免不可見光子進入操作系統(tǒng),設備復雜度高,實際應用實現(xiàn)難度大。

本文受到文獻[21]中關于向量編碼,以及文獻[22]中基于量子傅里葉變換的安全多方量子求和[23,24]的啟示,將向量編碼與安全多方量子求和方法結合起來,提出了一個新的安全多方量子排序協(xié)議,該協(xié)議簡單、安全且效率較高。

1 預備知識

1.1 安全性定義

圖1 安全性定義圖Fig.1 Diagram of security definition

1.2 安全多方量子求和

本方案用量子傅里葉變換方法進行多方安全求和,以下為對該量子傅里葉變換的定義。對未知態(tài)|x〉進行傅里葉變換,定義為[22]

對態(tài)|y〉進行傅里葉逆變換,定義為[22]

且存在右邊定義[22]

基于態(tài)|y〉進行傅里葉逆變換推導,可得

在安全多方求和計算過程中每個參與者對自己收到的中間數(shù)據(jù)需要進行一個Cj操作,Cj操作符定義為

(6)式中的下標t代表該粒子發(fā)送到量子信道中,|j〉t表示參與者從發(fā)起求和的發(fā)起者那里接受到的輔助量子態(tài),用以輔助求和計算。|x〉i即為算符U一個特征值為exp(2πixi/N)的特征向量。

2 安全多方量子排序協(xié)議

假設有N個富翁P1、P2、P3、···、Pn,每個富翁Pi的資產(chǎn)為si(其中s1≠s2≠s3···≠sn),每個富翁都想安全地知道自己的資產(chǎn)在所有富翁資產(chǎn)中的排名,又不想向其他富翁泄漏自己的資產(chǎn),借鑒向量編碼和安全多方量子求和的思想,將排序問題轉化為求和問題,所有參與者根據(jù)向量編碼規(guī)則執(zhí)行n次多方求和協(xié)議,從而確定各自的秘密在整個序列中的位置,達到保密計算的效果。

所提出協(xié)議執(zhí)行過程如下:

2.1 參與者準備階段

1)協(xié)議由n個參與者P1、P2、P3、···、Pn(半誠實)和一個第三方P0(半誠實)組成,每個參與者擁有各自的秘密si,且si∈ {1,2,···,n}。

2)P1、P2、P3、···、Pn各自擁有秘密si∈{1,2,···,n},每個參與者將各自的秘密數(shù)值si用一個長度為N的向量表示為Vi=(xi1,xi2,···,xin),其中向量的編碼規(guī)則為如果1≤j

3)首先發(fā)起人P0準備一個m-bit長的隨機的基態(tài)|x0〉h,其中m=log2N(其中N為上述的向量長度)且|x0〉h是P0的私有態(tài),然后P0對|x0〉h應用量子傅里葉變換得到

4)P0再準備另外一個m-bit的輔助態(tài) |0〉t,并對 |φ1〉|0〉t執(zhí)行m個 CNOT 門,得到

很顯然|φ2〉是個糾纏態(tài),下標h代表著該粒子是用戶保留,而下標t代表該粒子發(fā)送到量子信道中。

5)每個參與者Pi都根據(jù)自己的向量準備n個私有粒子態(tài) |x1〉i,|x2〉i,|x3〉i,···,|xn〉i。

2.2 協(xié)議操作階段

1)P0將計算得到的m-bit粒子(輔助量子態(tài)|j〉t)通過默認量子信道發(fā)送給P1。

2)P1接收到輔助量子態(tài)|j〉t,首先準備自己的私有粒子態(tài)|x1〉1,然后對|j〉t|x1〉1應用一個操作符Cj,其中|x1〉1即為U的一個特征值為exp(2πix1/N)的特征向量,隨即對整個P0和P1的復合量子系統(tǒng)進行一個Cj操作[(6)、(7)式],得到

3)P1通過量子信道傳送輔助態(tài)|j〉t給P2,將手中的|x1〉1保留。P2執(zhí)行與P1類似的過程,操作完后同樣通過量子信道傳送輔助態(tài)|j〉t給P1。之后的每個用戶均執(zhí)行該過程,如果每位用戶均誠實執(zhí)行操作過程,會得到

4)最后,Pn發(fā)送輔助量子態(tài)|j〉t給P0,P0對其應用m重CNOT門,得到結果

至此,協(xié)議參與者進行的操作階段已經(jīng)完成。

2.3 測量公布結果階段

1)P0在適當測量基上測量第二個m-bit位的粒子(|0〉t),如果測量的結果均為|0〉,則繼續(xù)下一步,否則認為可能存在第三方攻擊者竊取并修改了中間數(shù)據(jù),立即結束本次交互。

4)P0將該數(shù)字序列公布,該序列即為si的由小至大的升序排序序列,各參與者尋找與si相等的序列號,該序列號對應的數(shù)值即為各參與者的排名。

理論上,該方案適用于整數(shù)N確定后,任意不大于N的參與者,均可使用該方案獲得參與者秘密數(shù)據(jù)在所有參與者數(shù)據(jù)中的排名。

3 實驗驗證

使用量子計算云平臺IBM Q Experience上的模擬器對本協(xié)議核心量子求和部分的正確性進行驗證,即將量子計算過程轉化為量子可逆邏輯電路[26,27],在模擬器上設計出實驗電路圖,根據(jù)實驗結果確定本協(xié)議執(zhí)行的正確性。

3.1 實驗量子電路圖

基于文獻[28],驗證重點是關于量子傅里葉變換理論計算到邏輯電路的實現(xiàn),量子傅里葉變換即作用在空間C2n上的離散傅里葉變換,其把一組標準正交基{|x〉}用另一組標準正交基{|y〉}表示:Y=UX。此處U即為量子傅里葉變換的核心操作,即作用在Hilbert空間中任意矢量上的變換矩陣UQFT,該矩陣可拆分為一系列邏輯門。一個量子比特的量子傅里葉變換就是單個H門操作,多量子位態(tài)空間上的傅里葉變換就是對H門的推廣。將任意量子態(tài)制備成疊加態(tài),從而進行酉變換完成指數(shù)級加速。根據(jù)方案中的量子多方求和方法設計量子電路,完成關于安全多方量子排序的驗證。

驗證:當參與者數(shù)目m=4,參與者擁有私密數(shù)據(jù)1≤n<8,即N=7,假設有參與者P1、P2、P3、P4,P1所擁有秘密數(shù)值是6,P2是5,P3是3,P4是7。實驗電路如圖2～4所示,其中q[6]、q[7]、q[10]、q[11]分別表示參與者P1、P2、P3、P4,q[3]、q[4]、q[5]則為輔助量子比特,第三方測量位P0用q[0]、q[1]、q[2]表示。

1)P1、P2、P3、P4各個用戶將各自的秘密用一個長度為N的向量表示,其生成的二維向量分別為:V1=(0,0,0,0,0,1,1)、V2=(0,0,0,0,1,1,1)、V3=(0,0,1,1,1,1,1)、V4=(0,0,0,0,0,0,1)。由此可知,需要進行7次求和計算,并公布計算結果,方可得出4個參與者的排名。

2)P0開始初始化,進行傅里葉變換并用CNOT門添加輔助量子進行輔助檢測,電路圖如圖2所示。

3)參與者依次通過Cj(這里使用CNOT門和Toffoli門分割量子態(tài))向下復合,并將結果傳回給P0。此處以參與者輸入手中擁有的數(shù)字1、1、1、0為例,電路圖如圖3所示。

4)P0通過執(zhí)行CNOT門變換及傅里葉逆變換,并最終對q[0]、q[1]、q[2]進行測量并收集結果,電路圖如圖4所示。

圖2 量子傅里葉變換和CNOT門初始化Fig.2 Quantum Fourier transform and initialization of CNOT gate circuit

圖3 實驗電路圖Fig.3 Diagram of experimental circuit

圖4 傅里葉逆變換和測量電路Fig.4 Inverse Fourier transform and measurement circuit

圖5 實驗結果Fig.5 Experimental results

3.2 實驗結果分析

分別改變參與者輸入為 0、0、0、0,0、0、1、0,0、1、1、0,1、1、1、0以及 1、1、1、1得到計算結果,并繪制結果如圖6,其中橫坐標代表的二進制編碼表示的是依次按列調用排序協(xié)議得到的統(tǒng)計結果,將二進制編碼轉化成十進制即為排名信息分布,縱坐標代表計算的每一列,例如縱坐標5表示第5列計算結果對應010(十進制數(shù)為2)。

至此P0只需將該數(shù)據(jù)公布,各參與者把自己的數(shù)字當做編號,對照查看自己的排名(由小至大)。例如參與者P1秘密數(shù)字為6,查看縱坐標6對應橫坐標排名為3,所以根據(jù)參與者P1、P2、P3、P4的秘密數(shù)字為6、5、3、7,其所得到的排名分別為3、2、1、4。

圖6 計算結果分布Fig.6 Distribution of calculation results

4 安全性分析

4.1 內部參與者攻擊

由協(xié)議可知,P1無法得到關于P0私有秘密s1的任何信息,因為P0只向P1發(fā)送了輔助量子比特|j〉t,其中沒有任何有用信息,現(xiàn)在對P1和P2進行分析,分兩種情況:一種是參與者對第三方發(fā)送過程的中間數(shù)據(jù)進行攻擊,一種是參與者對其他參與者進行攻擊。

1)P1測量輔助量子比特|j〉t,顯然他可以以相同概率1/N得到|j〉(j∈{0,1,···,N?1}),然而測量結果j與P0手中的糾纏態(tài)沒有關系,也無法推導出更多數(shù)據(jù),因此這樣的攻擊無效。

2)在將U操作算子應用于輔助比特|j〉t后,P2再次測量它。P2知道P1的秘密狀態(tài)|x1〉已經(jīng)進化成與|j〉t相同的狀態(tài)?；诹孔痈道锶~變換的輔助態(tài)|j〉t,他可以在輔助態(tài)|j〉t上執(zhí)行量子傅里葉逆變換,期望提取|x1〉。其攻擊描述可表示為

通過上述推導,如果P2測量輔助狀態(tài),他會以等概率1/N得到|l〉t(l∈{0,1,···,N?1})。這意味著P2無法獲得任何關于P1的秘密信息,因為他不能從具有下標h和t的糾纏量子系統(tǒng)的部分量子位中提取全局相位信息。事實上,任何局部酉算子都是如此(除非直接測量),否則部分量子位不能完全分離復合系統(tǒng)的糾纏。因此,即使P2執(zhí)行這種攻擊,他仍然無法得到任何關于P1的私密信息|x1〉。

4.2 截取-重發(fā)攻擊

協(xié)議采用對協(xié)議2.2中步驟3)、4)和協(xié)議2.3中步驟1)中的輔助量子比特進行檢測,來避免截取-重發(fā)攻擊。在協(xié)議中,參與者事實上并沒有將自己的私有數(shù)據(jù)通過量子信道傳送,而是將自己的私有態(tài)通過U操作與初始量子系統(tǒng)進行復合得到糾纏態(tài),再根據(jù)適當?shù)母道锶~逆變換操作來得到求和結果。假設有攻擊者通過量子信道獲取P0所發(fā)送的中間數(shù)據(jù)|j〉t,攻擊者得到的中間數(shù)據(jù)只有|j〉t,攻擊者一旦對其進行測量,由于該復合系統(tǒng)是糾纏的,就會對P0手中擁有的量子態(tài)進行塌縮,在協(xié)議2.3步驟1)中P0對復合系統(tǒng)進行CNOT門還原,再對|j〉t進行測量,理論上,如果沒有攻擊者攻擊,可以測得|j〉t為|0〉t,但是由于攻擊者攻擊,使之前的數(shù)據(jù)塌縮,P0可以正確獲得|j〉t剛好為|0〉t的概率為1/2N,所以P0會發(fā)現(xiàn)信息被竊取,可以立即停止當前協(xié)議,廢除數(shù)據(jù),重新開始協(xié)議進行計算。同理,攻擊者對P1及其它參與者采取這樣的攻擊都適用上述分析,因此,理論上協(xié)議可以抵御截取-重發(fā)攻擊。

5 結論

將多方排序問題轉化為求和問題,基于量子傅里葉變換求和設計出一種安全多方量子排序協(xié)議,以求取一組秘密數(shù)據(jù)的排序序列,參與者可獲得自己對應的排名,且該排名不會被其他參與者知曉。相較于其他量子排序協(xié)議,所提出協(xié)議只需要執(zhí)行O(n)輪次就能夠得到排名,一定程度上降低了通信和計算開銷。通過在IBM Q平臺上對協(xié)議進行驗證,可知此協(xié)議執(zhí)行正確有效。同時,此協(xié)議還能夠抵御惡意攻擊者的截取-重發(fā)攻擊,以及n?2名以下參與者的聯(lián)合攻擊。