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

胡志泉 ，薛 立 德 ，楊 威

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

0 引言

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

1 量子貨幣方案的內容和概況

1.1 量子貨幣的研究背景

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

1.2 量子貨幣的一般方案

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

（1）銀行：接受經典密文〈x〉，并從〈x〉準備量子貨幣態 |〉（有時還準備一個經典序列號）。

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

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

2 攻擊隱藏子空間方案

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

2.1 安全缺陷

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

然后矩陣Λ為：

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

算法1獲得集合R

輸出：集合 R

1:初始化 R=?

5: else

12:end if

13:end for

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

定理1根據算法1獲得的集合R具有以下性質：

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

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

證明：考慮密度矩陣

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

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

定理1揭示了由微型方案構造的量子貨幣態具有一定的規律性，這些規律性將成為攻擊方案的主要基礎。

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

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

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

（2）數量大于等于1的目標量子貨幣態的副本；

（3）調用 Ver或 UA的次數遠小于 Ω（2n/4）。

那么使用如下算法2就可以成功獲取目標態的所有經典密文。

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

輸入：微型子空間方案中一些目標量子貨幣態的副本|A〉；

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

輸出：|A〉的經典密文。

1: 初始化集合 γi，i∈{1，2，…，maxR}，令其為的一組組合數，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:初始化計數器i=1和集合S=?

3:對目標量子貨幣態的副本（副本數≥1）在標準基下測量,獲得一組線性無關的結果Z：

14：算法失敗（但對算法 5來說，仍然產生了有用的輸入）

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

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

算法3糾纏檢測

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

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

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

3:for m≤i do

4: 假設 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ˉ構成的矩陣），其中M是系數矩陣，因此M可以分為 A和 B兩部分，并滿足 Zv=AZu，Zw=BZu。這樣劃分的原因如下，假設目標量子態為：

算法4更新集合γi

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

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

（1）他只有一份未知量子貨幣態的副本；

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

根據微型方案的定義，構成量子貨幣態的子空間A應該以相等的概率隨機選擇，但是現在看來，不同的子空間具有不同的安全性，量子位之間的糾纏越復雜，該方案就越安全。

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

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

其中:

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

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

算法5擴展攻擊方案

輸入：微型子空間方案中一些目標量子貨幣態的副本|A〉；算法 2的輸出。

輸出：|A〉的經典密文。

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

2:偽造者在標準基下測量所有其擁有的目標態的副本,所有線性無關的測量結果保存在I中

4: 算法失敗,然后結束

5:else

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

3 隱藏子空間方案的改進

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

3.1 改進的方案

其中A滿足兩個條件：

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

根據以上定義，量子貨幣態的結構被固定為n量子比特糾纏的純態。雖然子空間的選擇是有限的，但糾纏可以帶來優勢。

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

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

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

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

3.2 安全性證明

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

引理1（糾纏和負條件熵[15]）假設|AB〉是復合量子系統AB的純態，則|AB〉當且僅當條件熵S（B|A）＜0時才糾纏。

引理2假設存在一個糾纏的純態ρ，其復合系統為 AB。 令 trB（ρ）=ρA，trA（ρ）=ρB，不存在量子算符 ε能使得 ε（ρA?ρB）=ρ。

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

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

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

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

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

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

4 結論

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

（1）量子貨幣態的副本數：本文的算法可以執行最少一個副本。它不影響算法的成功率和對Ver（或UA）的調用次數。在這里副本數影響算法的計算復雜度。

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