基于隱藏子空間的量子貨幣的攻擊研究*

胡志泉 ，薛 立 德 ，楊 威

（1.中國科學(xué)技術(shù)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 合肥230026；2.中國科學(xué)技術(shù)大學(xué) 蘇州高等研究院，江蘇 蘇州215000）

0 引言

隨著量子密鑰分發(fā)（QKD）[1]的應(yīng)用，量子密碼協(xié)議正處于蓬勃發(fā)展的階段，但是作為最早出現(xiàn)的量子密碼學(xué)問題之一，量子貨幣問題尚未得到適當(dāng)?shù)慕鉀Q。由于很難長時間維持量子態(tài)的相干性，并且在量子貨幣方案中，偽造者可以在驗證算法提示下獲得有關(guān)未知量子態(tài)的更多詳細(xì)信息，因此量子貨幣方案通常需要更嚴(yán)格的安全證明。量子認(rèn)證，尤其是量子簽名，與量子貨幣有潛在的聯(lián)系，量子貨幣本身可以被視為一種特殊類型的量子簽名。量子貨幣方案各種變體還可形成具有不同功能的量子密碼協(xié)議，現(xiàn)有量子簽名協(xié)議，例如ZMWZ協(xié)議[2]、文獻[3]所提協(xié)議以及基于相位編碼的協(xié)議[4]都基于QKD技術(shù)，因此量子貨幣方案的研究將帶來量子簽名的新方向。

1 量子貨幣方案的內(nèi)容和概況

1.1 量子貨幣的研究背景

量子貨幣的概念最初是在1969年提出的，其主要目的是允許銀行發(fā)行不可偽造和可驗證的量子貨幣態(tài)。隨后，Wiesner提出了第一個私鑰量子貨幣方案[5]，該方案由產(chǎn)生鈔票（量子貨幣態(tài)）的銀行和驗證鈔票真實性的驗證算法組成。雖然在信息理論上已被證明是安全的，但后來發(fā)現(xiàn)它存在許多安全缺陷-“驗證問題”：由于其作為私鑰量子貨幣方案的性質(zhì)，只有生產(chǎn)鈔票的銀行才能驗證其真實性；“數(shù)據(jù)庫問題”：銀行需要為其發(fā)行的每張鈔票存儲一個經(jīng)典描述（1983年，Wiesner[6]等人使用偽隨機函數(shù)解決了“數(shù)據(jù)庫問題”，并將原始方案變成了計算安全的方案）；“攻擊問題”：有很多有效的攻擊方案，例如 Lutomirski的“在線攻擊問題”[7]，Nagaj等人的“自適應(yīng)攻擊”[8]等。 在最初的私鑰方案之后，由Aaronson[9]提出的公鑰量子貨幣方案引起了很多關(guān)注，它的核心思想是公開驗證算法，以便每個人都可以驗證鈔票的真實性。隨后，F(xiàn)arhi等提出了基于結(jié)的量子貨幣方案[10]，其鈔票是具有相同亞歷山大多項式的編碼狀態(tài)的疊加。盡管到目前為止尚未發(fā)現(xiàn)對該方案的有效攻擊，但也沒有證明該方案是安全的。Aaronson和Christiano隨后提出了一種在隱藏子空間上基于公鑰的量子貨幣方案[11]，并證明了它的計算安全性，他們構(gòu)建了安全的微型量子貨幣方案，并將其與數(shù)字簽名相結(jié)合，以防止量子選擇明文攻擊。雖然該方案存在一些缺陷（將在第2.1節(jié)中討論該問題），但仍提出了許多有用的建議，Aaronson等表明量子貨幣由于其無糾纏的性質(zhì)而具有很高的實用性。 但是，隨著諸如“量子態(tài)恢復(fù)[12]”之類攻擊算法的出現(xiàn),大多數(shù)當(dāng)前的量子貨幣方案可以被有效攻擊，尤其是無糾纏的量子貨幣方案，其根本是許多無糾纏的方案，它們的驗證算法由秩為1的投影測量構(gòu)成，因此對于量子貨幣，糾纏方案受到更多關(guān)注。在實驗領(lǐng)域，Bartkiewicz[13]首先通過實驗重新審視了Wiesner的想法，表明可以使用量子態(tài)制備無法真實克隆的鈔票，Bozzio[14]的實驗也朝著實現(xiàn)量子貨幣邁出了關(guān)鍵的一步。如上所述，量子貨幣問題尚未完全解決，面臨的最重要挑戰(zhàn)之一是計算安全性不充分，原因之一是大多數(shù)安全性建立在偽造者應(yīng)使用方案提供的預(yù)言黑盒（oracle）的假設(shè)，這可能會限制偽造者的攻擊手段，所以量子貨幣方案需要更深入的研究。

1.2 量子貨幣的一般方案

一個通用量子貨幣方案S由兩個主要部分組成：銀行和驗證算法（Ver）。銀行每次都會使用經(jīng)典密文〈x〉來制造 Ver接受的鈔票，其中〈x〉可以是真正的隨機、偽隨機或特殊含義的字符串，Ver可以是酉或非酉操作。給出以下簡要定義：

（1）銀行：接受經(jīng)典密文〈x〉，并從〈x〉準(zhǔn)備量子貨幣態(tài) |〉（有時還準(zhǔn)備一個經(jīng)典序列號）。

（2）Ver：接受輸入的鈔票并輸出“Accept”=1或“Reject”=0。

對于任何偽造者C，假設(shè)C的可用資源為：一張或多張目標(biāo)鈔票，多次調(diào)用Ver的能力，驗證后的量子態(tài)的檢索和多項式量子計算能力。令|1〉=|2〉=…=|q〉（q≥1）分別為存儲在 q 組寄存器中的q張相同的目標(biāo)鈔票，而|Σ〉是 C的輔助態(tài)。C的所有輸出態(tài)都存儲在h（h≥1）組寄存器中。令：

2 攻擊隱藏子空間方案

本節(jié)將重點介紹A＆C的隱藏子空間方案，并詳細(xì)說明其中的一些安全漏洞，以及利用這些漏洞的攻擊算法。

2.1 安全缺陷

A＆C方案的核心是隱藏子空間微型方案，其定義如下：

然后矩陣Λ為：

當(dāng) rank（Λ）=n/2時，存在滿足的矩陣 Λα和 Λβ：

算法1獲得集合R

輸出：集合 R

1:初始化 R=?

5: else

12:end if

13:end for

其元素Ri也是子空間A的集合，并得到定理1。

定理1根據(jù)算法1獲得的集合R具有以下性質(zhì)：

（1）A&C方案的每個量子貨幣態(tài)都可以寫成：

其中 f（Ri，j）代表 Ri在矩陣 Λ 中的第j個元素的原始位置 （例如當(dāng)矩陣Λ不執(zhí)行行交換操作以獲得Λα和 Λβ時，Ri的第j個元素所在的 Λ 的行數(shù)）。

證明：考慮密度矩陣

其中，ai是長度為|Rh|的位串，bi是長度為（n-|Rh|）的位串,1≤h≤|R|。

其中，v?{f（Rh，l）|1≤l≤|Ri|}。

定理1揭示了由微型方案構(gòu)造的量子貨幣態(tài)具有一定的規(guī)律性，這些規(guī)律性將成為攻擊方案的主要基礎(chǔ)。

2.2 微型隱藏子空間方案的攻擊算法

對于子空間比較簡單的情況，同時假設(shè)具有如下屬性的偽造者：

（1）足夠的計算能力（不需要是指數(shù)級）；

（2）數(shù)量大于等于1的目標(biāo)量子貨幣態(tài)的副本；

（3）調(diào)用 Ver或 UA的次數(shù)遠小于 Ω（2n/4）。

那么使用如下算法2就可以成功獲取目標(biāo)態(tài)的所有經(jīng)典密文。

算法2微型隱藏子空間方案的攻擊

輸入：微型子空間方案中一些目標(biāo)量子貨幣態(tài)的副本|A〉；

預(yù)估的糾纏量子比特的最大數(shù)量：maxR=maxRi∈R|Ri|。

輸出：|A〉的經(jīng)典密文。

1: 初始化集合 γi，i∈{1，2，…，maxR}，令其為的一組組合數(shù)，e.g.，γ2={（1，2），（1，3），…，（n-1，n）}，γ3={（1，2，3），（1，2，4），…，（n-2，n-1，n）}，… ，是 γi中的第i個元素

2:初始化計數(shù)器i=1和集合S=?

3:對目標(biāo)量子貨幣態(tài)的副本（副本數(shù)≥1）在標(biāo)準(zhǔn)基下測量,獲得一組線性無關(guān)的結(jié)果Z：

14：算法失?。ǖ珜λ惴?5來說，仍然產(chǎn)生了有用的輸入）

攻擊算法2的核心思想是在一個標(biāo)準(zhǔn)基上測量目標(biāo)量子貨幣態(tài)，然后使用試錯法來逐一攻擊量子貨幣的子系統(tǒng)，并注意該過程不會消耗任何量子貨幣,同時由于|Ri|相對較小，計算復(fù)雜度很低。將定理1與先前的測量結(jié)果結(jié)合起來，分析可能的情況并將其輸入到UA中進行驗證。

算法 2中集合 γi和 S用于存儲量子位之間的關(guān)系，調(diào)用算法3來檢測每個可能的關(guān)系，最后如果算法成功運行，則得到輸出的目標(biāo)態(tài)的經(jīng)典密文。

算法3糾纏檢測

輸出：0 或者（1，|S〉）

1:計算下面向量集的維度d

2:初始化計數(shù)器m=d和集合g=?假設(shè) Zu={Zu1，Zu2，…，Zud}?Q 是 Q 的最大線性無關(guān)向量組

3:for m≤i do

4: 假設(shè) Zv={Zv1，Zv2，…，Zvd}?Q，Zw={Zw1，Zw2，…，Zwd}?Q，Zu∪Zv=Zu∪Zw=Zv∪Zw=?

5: for each Zvdo

Zu是其一組基，并且令 Zu∪Zv是另一組行向量，這些向量可以通過Zu的元素進行線性組合。

令 Zuˉ=MZu（此 處 Zu或 Zuˉ也 代 表 由 集 合 Zu或 Zuˉ構(gòu)成的矩陣），其中M是系數(shù)矩陣，因此M可以分為 A和 B兩部分，并滿足 Zv=AZu，Zw=BZu。這樣劃分的原因如下，假設(shè)目標(biāo)量子態(tài)為：

算法4更新集合γi

其中 δi是在算法 2的步驟（4）的前 i-1個回合中添加到集合S中的量子比特數(shù)（即已被算法2破解的量子比特數(shù)），并且如果δmaxR+1=n，則算法 2成功?？梢钥闯?，不僅與 n有關(guān)，而且與maxR有關(guān)，并且不再隨n的增加而呈指數(shù)增加。當(dāng)maxR足夠小時，。從以上分析可以看出，對 UA的調(diào)用與所需副本之間沒有直接聯(lián)系。副本的數(shù)量主要影響算法3的執(zhí)行速度，即偽造者擁有的副本越多，算法3的執(zhí)行速度就越快。另一方面，它還顯示了以下定理2與文獻中的定理20[11]相反。

定理2對于具有足夠計算能力的對手，即使：

（1）他只有一份未知量子貨幣態(tài)的副本；

（2）UA的調(diào)用次數(shù)受到限制（遠遠小于Ω（2n/4））。當(dāng)maxR足夠小時，他仍然可以成功地攻擊微型隱藏子空間方案。

根據(jù)微型方案的定義，構(gòu)成量子貨幣態(tài)的子空間A應(yīng)該以相等的概率隨機選擇，但是現(xiàn)在看來，不同的子空間具有不同的安全性，量子位之間的糾纏越復(fù)雜，該方案就越安全。

2.3 微型隱藏子空間方案的擴展攻擊方案

攻擊算法的成功之處在于與maxR的值直接相關(guān)。當(dāng)maxR太大時，攻擊算法無法破解所有量子貨幣的經(jīng)典信息，尤其是那些具有較大|Ri|的信息。但是某些子空間中的隱患遠不止算法2。例如n=10，而量子貨幣態(tài)可以寫成：

其中:

如果算法 2預(yù)設(shè) maxR=3，因為|R3|＞3，所以無法獲得與R3相對應(yīng)的態(tài)。但是|A1〉和|A2〉可以被破解，可以推斷出與|A3〉對應(yīng)的向量空間的維數(shù)為2。接下來只要獲得目標(biāo)量子貨幣態(tài)的幾個副本，并在標(biāo)準(zhǔn)基上對其進行測量，即可得到空間A3的另一結(jié)果（其中一個已在算法2中獲得），然后可以知道|A3〉的所有經(jīng)典信息。

上面的示例顯示了從算法2派生的潛在攻擊方案。即使先前的攻擊算法失敗，有關(guān)已破解的未知態(tài)的信息也對后續(xù)攻擊有用。當(dāng)|Ri|很大，但是向量空間的維數(shù)很小時，它仍然面臨著非常嚴(yán)峻的安全風(fēng)險。關(guān)于該攻擊方案更正式的描述在算法5中給出。

算法5擴展攻擊方案

輸入：微型子空間方案中一些目標(biāo)量子貨幣態(tài)的副本|A〉；算法 2的輸出。

輸出：|A〉的經(jīng)典密文。

1:假設(shè)算法 2沒有破解目標(biāo)態(tài)的第q1，q2，…，qm個量子比特，其他破解的態(tài)記為|A1〉，|A2〉，…，|Ak〉,其中 dimAi=di，i∈{1，2，… ，k}

2:偽造者在標(biāo)準(zhǔn)基下測量所有其擁有的目標(biāo)態(tài)的副本,所有線性無關(guān)的測量結(jié)果保存在I中

4: 算法失敗,然后結(jié)束

5:else

6: 取I中所有元素作為基向量，在所有可能的線性組合上迭代，使τ成為這些結(jié)果的集合

3 隱藏子空間方案的改進

前面的算法僅對滿足要求的子空間有效。本節(jié)將改進原始的隱藏子空間方案，并從信息論的角度為安全性提供新的證明。

3.1 改進的方案

其中A滿足兩個條件：

（2）態(tài)|A〉的每個量子位相互糾纏（即 A的 R集滿足|R|=1）。

根據(jù)以上定義，量子貨幣態(tài)的結(jié)構(gòu)被固定為n量子比特糾纏的純態(tài)。雖然子空間的選擇是有限的，但糾纏可以帶來優(yōu)勢。

首先，將潛在的攻擊方案分為兩類：

（2）整體攻擊：與部分攻擊相反，如在圖1中，ρA=|A〉〈A|和 trA（So）=ρA。

圖1 偽造者潛在攻擊的一般模型

算法2和算法5都屬于部分攻擊。在這里，攻擊的分類并不限制偽造者的操作，而在A＆C的方案中，它隱含了對偽造者只能使用單一操作的限制。這就是本文改進攻擊方案行之有效的原因。

3.2 安全性證明

首先給出一些量子信息論中的引理，將在后面使用。

引理1（糾纏和負(fù)條件熵[15]）假設(shè)|AB〉是復(fù)合量子系統(tǒng)AB的純態(tài)，則|AB〉當(dāng)且僅當(dāng)條件熵S（B|A）＜0時才糾纏。

引理2假設(shè)存在一個糾纏的純態(tài)ρ，其復(fù)合系統(tǒng)為 AB。 令 trB（ρ）=ρA，trA（ρ）=ρB，不存在量子算符 ε能使得 ε（ρA?ρB）=ρ。

根據(jù)引理2可以推斷出，如果偽造者C想要使用部分攻擊，則 ρA?ρA和 ρB?ρB在圖 1中 C線路的任何階段都不會存在。如果C的攻擊線路有效并且線路上出現(xiàn) ρA?ρA和 ρB?ρB，則線路的量子運算必然與引理2矛盾。

引理 3在圖 1中， 量子算符 εΣ不能使 ρA與 Σ糾纏。

將引理2和引理3結(jié)合在一起，可以得出關(guān)于改進方案的安全性的重要結(jié)論。

如果C要通過部分攻擊來克隆鈔票，引理2表明，在圖1的C線路中的任何階段都不會出現(xiàn)ρA?ρA和 ρB?ρB，即 C 輸出的復(fù)合態(tài)不能寫成張量積的形式。因此，它必須是一個糾纏態(tài)，這與引理3相矛盾。引理 3也表明，量子算符 εΣ不能使 ρB與 Σ糾纏。

以上結(jié)論表明，在圖 1中，trA（So）≠ρA，更進一步，根據(jù)引理 2，trA（So）≠ρB，即偽造者不能通過輸入目標(biāo)量子貨幣態(tài)的部分態(tài)來破解改進方案（該結(jié)論仍然適用于多個系統(tǒng)）。

對于整體攻擊，A＆C的證明已經(jīng)足夠（也適用于本文改進的方案）。為了測量整個量子貨幣態(tài)以了解經(jīng)典密文，他們通過限制具有相同經(jīng)典密文的紙幣的流通來解決了這個問題。

4 結(jié)論

本文通過理論分析,證明了A＆C量子貨幣方案的子空間結(jié)構(gòu)存在漏洞,并非所有的子空間都絕對安全。由大量子空間產(chǎn)生的量子貨幣態(tài)可以由多個純態(tài)子系統(tǒng)的直積表示，每個子系統(tǒng)的量子比特數(shù)量要比整個系統(tǒng)小得多。設(shè)計算法演示的攻擊方案具有如下特點：

（1）量子貨幣態(tài)的副本數(shù)：本文的算法可以執(zhí)行最少一個副本。它不影響算法的成功率和對Ver（或UA）的調(diào)用次數(shù)。在這里副本數(shù)影響算法的計算復(fù)雜度。

通過在子空間上添加約束改進了原始的隱藏子空間方案,確保了每個量子貨幣子空間結(jié)構(gòu)的健壯和復(fù)雜，并且確保每個量子位之間必須存在糾纏。最后，從信息論角度看，如果偽造者想要克隆未知的量子貨幣，那他必須開始從整個系統(tǒng)進行攻擊，而不是像以前那樣攻擊子系統(tǒng)。在這種情況下，偽造者將面對原始A＆C方案的完美安全性。