量子信息安全的小烏雲
前言
經典的安全通訊協議往往只能提供計算上的安全性（Computational security），其通常假設參加通訊的各方，包括竊聽者，只有有限的計算能力。而且其也依賴於一些演算法複雜度的假設，例如離散對數問題不能在多項式時間內被解決。而量子安全通訊協議則可以提供一種不依賴於通訊雙方的能力（計算能力，量子操作的能力等），而只基於資訊理論的安全性，即資訊理論安全（Information-theoretic security）。為了達到資訊理論安全，即使通訊過程中的各方有著無窮的計算能力，我們也要保證我們的協議是安全的。
在密碼學中，我們為各種各樣的密碼學問題設計各種各樣的安全通訊協議。比如為了達到保密通信，我們希望能加密我們的數據。我們發現使用一次性密碼本（One-time pad）的方法可以使我們安全通信（使用AES）。但是在通訊的時候我們需要傳遞密碼本。為了傳遞密碼本，我們發明了公鑰密碼學的RSA協議，這使得我們可以安全地在通訊雙方分發密碼本。在保密通訊中，我們的通訊協議有賴於兩個小的安全性問題的通訊協議的安全性。在這裡小的安全問題是密碼本的分發以及在有一次性密碼本情況下的安全通訊。在經典情況下，一次性密碼本是資訊理論安全的，密鑰分發是計算安全的，故保密通訊是計算安全的。如果我們能使密鑰分發的過程也是資訊理論安全的，我們就能使保密通訊也達到資訊理論安全。像這樣，在構造複雜的安全通訊的時候，我們常常可以把我們面臨的問題分解成更小的安全性問題的組合。有一些經常被用到的安全性問題被稱為密碼學原語（Cryptographic primitive）。在這裡我列出維基百科上的給出的常見的密碼學原語。
One-way hash function, sometimes also called as one-way compression function—compute a reduced hash value for a message (e.g., SHA-256)
AuthenticationSymmetric key cryptography—compute a ciphertext decodable with the same key used to encode (e.g., AES) Public key cryptography—compute a ciphertext decodable with a different key used to encode (e.g., RSA) Digital signatures—confirm the author of a message Mix network—pool communications from many users to anonymize what came from whom Private information retrieval—get database information without server knowing which item was requested
Commitment scheme—allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal it later Cryptographically secure pseudorandom number generator Retrieved from Cryptographic_primitive, Wikipedia
上個世紀，量子密鑰分發（QKD）協議的誕生讓人們對量子通訊協議的前景充滿了信心。QKD可以資訊理論安全地在通訊雙方之間分享一個密鑰（密碼本），從而解決了公鑰密碼學（Public key cryptography）想要解決的問題，使得保密通訊在有量子信道的情況下可以達到資訊理論安全。使用量子力學天然的隨機性，我們還可以輕易地解決隨機數生成的問題，從而使得上表中的Cryptographically secure pseudorandom number generator（密碼學安全偽隨機數生成器）問題達到資訊理論安全。
QKD與量子隨機數生成的成功使人們不禁去想，那些密碼學原語，是否都能通過量子力學的效應來達到資訊理論安全。如果事實如此，那麼人類的信息安全將在量子技術成熟以後全面進入資訊理論安全的時代。這聽起來挺誘人的，我猜當時的人們一定對這個目標懷有巨大的憧憬。但是事實上，量子力學的引入並不總能給人們帶來驚喜。在上個世紀最後幾年，人們意識到有兩個重要的密碼學原語一定不能通過量子的方式來達到資訊理論安全。這個消息實在是令人悲傷，因為如果量子力學也不能使我們達到資訊理論安全的話，我們看上去對這些問題永遠束手無策了。接下來我將介紹一些被證明無法在量子力學框架內被解決的密碼學問題。它們分別對應表中的Commitment scheme與Private information retrieval。
比特承諾（Quantum Bit Commitment）
比特承諾問題是一個很重要的密碼學原語。從它出發我們能構造出很多有用的協議（參見維基百科Commitment_scheme）。我們設協議雙方是Alice和Bob（密碼學吉祥物）。在比特承諾問題中，Alice先決定了一個比特是0還是1，然後放在一個容器里，作為承諾的內容。然後再將這個容器交給Bob，作為承諾的證據。Alice在把容器交給Bob之後不能再修改承諾的內容。Bob收到容器之後，並不能通過容器立即知道Alice的承諾。但是在一段時間過後，Bob可以在Alice的指導下打開容器，從而知道Alice之前承諾的內容。
在這裡，這個容器可以是一個量子態，一串加密後的比特，等等。如果你沒法想到上面描述的密碼學問題有什麼用或者沒有看懂我在敘述什麼，你可以設想你去一個賭場賭博，你要對一個擲硬幣的結果下注（即上文中的承諾）。但是在擲硬幣的結果公布之前，你並不想讓莊家知道你的下注內容，因為那樣莊家就可能使用某種作弊手段，比如用磁鐵控制硬幣向你下注的相反方向運動。但是莊家也不傻，他不會允許你在結果公布之後改變你的下注結果，要不然你豈不是局局都能贏？在這個賭場模型中，你就是比特承諾問題中的Alice，而莊家就是Bob。
還有一個例子是，有一個人想讓你相信他有預測股票市場的能力，但是他又不想讓你拿他的預測結果去買股票。這事時他就可以利用比特承諾協議，把他的預測放在容器里，在股票運行完畢時候再與你一起打開容器，印證自己的預測。
對於一個安全的比特承諾協議我們需要有兩點
- Alice在作出承諾之後不能再修改承諾內容。
- Bob不能在Alice揭示承諾之前知道承諾的內容。
在經典情況下我們只有
對於量子的協議，一開始人們認為可以用類似於QKD的方法來實現一個QBC（Quantum Bit Commitment）的協議。一開始的時候人們非常樂觀，提出了一些協議。有意思的是，這些協議還長時間被認為是安全的。直到在1998年，Lo-Chau與Mayers分別獨立地證明了無條件安全的量子比特承諾是不可能的。（無條件安全（Unconditional security）是指不依賴於假設（比如複雜度假設）的安全，其實說資訊理論安全更加準確，但是由於歷史原因這裡寫作無條件安全）Lo-Chau指出，一般的比特承諾協議具有以下步驟
- 態製備：
Alice選擇承諾的內容（0或1），製備相應的兩個正交的態 ，記Alice的態的空間為
。同時，Bob也準備一個態
這個態在空間
中。
- 承諾：
Alice與Bob一起施加酉變換在整個系統 上。
Lo-Chau指出如果Bob完全沒有任何承諾的信息，那麼Alice可以通過量子糾纏隨意地改變承諾的內容。證明如下。
我們記 為承諾為0,1時，大系統
所處的態。由於Alice和Bob都知道協議的內容，他們知道所有對他們手裡量子態的操作，所以他們可以計算出
。由於Bob完全不知道承諾的信息，在整個系統處於
的時候，在他看來應該是一樣，即
考慮對系統 有施密特分解。
與
是空間中的幾組正交矢。
利用上式展開partial trace
故有
故我們可以把 寫成
兩個分解的施密特係數相同。唯一的不同在於 ，與
。由於
與
是兩組正交矢，我們可以找到一個
上的酉變換
使
。從而實現承諾內容的改變。在這裡因為
是作用在
上的，所以Bob既不能阻止也不能發現Alice的cheating。故不存在資訊理論安全的QBC協議。這個不存在性被稱為MLC no-go定理。
Lo-Chau用上述方法證明了之前提出的QBC協議的不安全性。你有可能覺得Lo的模型有些簡陋，好像有很多的情況沒有被列舉進去。事實上雖然確實如此，現在（2018）在美國西北大學的Yuen在2000年左右曾對MLC no-go定理的原始證明進行過有效的攻擊。但是有意思的是，Lo-Chau與Mayers的理論在被後來的學者修修補補後，得到的結論依然是資訊理論安全的QBC是不可能的。
資訊理論安全的QBC協議的不可能性的發現，意味著人們發現了一個密碼學原語，對於這個原語，量子力學也無計可施。這使得人們意識到量子密碼學的局限性。同時，QBC的不安全性也意味著，如果你要構建一個資訊理論安全的量子安全協議，然後你發現通過這個協議，我們可以實現資訊理論安全的QBC，那麼你要建立的的這個協議很可能是不存在的。QBC的不安全性使得我們降低了對一些量子信息安全協議的期待，從而節省了研究者的時間。從某種意義上講，QBC成為了一個量子密碼學裡不可能性的原語。
不過有趣的是，事情其實並沒有想像中的悲觀。我們需要注意的是，量子力學並不足以描述這個世界，我們還要考慮相對論效應。1998年Adrian Kent指出，在考慮了相對論效應之後，資訊理論安全的QBC協議是可能的。在2014年，中科大的Yang Liu，Yuan Cao與西班牙Vigo大學的Marcos合作對Adrian的協議進行了實驗的驗證。我們不禁會想，對於給定的一個物理系統，到底是什麼決定了安全協議的存在與否。量子資源理論（Quantum Resource Theory）興許是一個很好的研究工具。在量子資源理論中，我們定義什麼是我們可以隨意產生的自由態，隨意進行的自由操作。並在此基礎上定義什麼是不自由的資源。對於不同的物理系統，我們可以定義不同的QRT，繼而研究這個系統可以做什麼事情。
還有一點是，如果你去查閱目前認為是最前的MLC no-go定理的證明，你會發現他們給出的證明根本不是上文給出的這麼簡單的。他們用非常多的筆墨來證明在廣泛的情況下，no-go定理都是成立的。由於他們的文章非常的長，而且讀起來非常困難，所以導致一般人並不會去專門檢查文章中的錯誤。但是證明的變長常常意味著更容易出錯。中山大學的何廣平教授就認為他找出了這些證明中的不少錯誤，並且提出了一個他認為是安全的QBC協議。但是他的成果並沒有得到太多的注意。有可能是他的發現確實沒有太大的意義，但也有可能是因為證明太長導致了學界的普遍盲從。具體是哪一個，我也不知道。到目前世界上認為no-go定理是錯誤的，數得上名的人，只有三個。何教授和美國的Yuen佔了兩個。
安全的雙邊計算 (Quantum Secure Computation)
通過相似的手法，Lo證明了某種量子安全雙邊計算是不可能的。他設想了以下場景
- Alice有一個私密的輸入
，
- Bob有一個私密的輸入
，
- Alice幫助Bob計算一個約定好的函數
- 最終，Bob準確地得到
（Bob就得到單純的一個數字）
- Alice不知道
- Bob不知道
（除了從邏輯上可以推測的）
Lo證明了在這種場景下，不可能達到資訊理論安全。這個證明不是很難，使用的手法跟QBC問題中及其相似。最終可以發現，Bob可以通過在自己的系統上施加一個酉操作使得他可以在計算結束後改變一開始的輸入 ，從而獲得全部的
。
量子私密查詢 (Quantum Private Query)
量子私密查詢（QPQ）是一個很有直接的現實應用前景的安全問題。設想你得到了你所在大學所有女生的電話號碼，組成一個資料庫。你想要通過出售資料庫數據來賺錢。那些春心蕩漾的男生想要從你這裡購買電話號碼。但是如果他們直接告訴你他們想要查詢的人是誰，他們就會暴露自己具體喜歡哪個女生，這是他們不願看到的。他們希望在你不知道他們要查詢的數據的情況下獲得數據。這就是私密查詢問題，對應我在前言里列出的密碼學原語中的Private information retrieval。
在這裡，安全性有兩重
- 資料庫不想暴露更多的信息
- 用戶不想資料庫知道自己查詢的目標
一旦我們要求資料庫完全不知道用戶查詢的內容，就會陷入像上文中一樣的完美封藏（Perfect concealing）局面。此時用戶就可以使用與上文一樣的伎倆，獲取資料庫的所有信息。
接下來，我將用一個簡單的例子來解釋這一點。假設資料庫里有兩個元素，用戶可以進行一次查詢。我們可以認為資料庫是上文量子安全雙邊計算中的Alice，而用戶是Bob。資料庫的輸入為 （待查詢的數據），而用戶的輸入為
。他們要計算的函數是
。根據Lo的理論，這個過程不可能是資訊理論安全的。
雖然說，又一個密碼學原語問題被證明是無法是資訊理論安全的。但是值得注意的是，QPQ問題可以用QKD的方法來非完美解決。Markus Jakobi等人在2010年給出了一個基於QKD的QPQ協議。在這個協議中，我們可以使用戶只多知道一點點的資料庫內容。QKD是一個相對成熟的協議，並且已經有了很多現實的應用。我相信QPQ也會在將來被廣泛應用。
自我介紹
筆者為南方科技大學16級本科生，目前隸屬於南方科技大學翁文康教授的課題組。主要研究量子安全雙邊計算中的一些課題。業餘時間喜歡看動畫，立志成為@Macro kuo那樣的硬核動畫評論家。
這個專欄是我發起的，我希望能為中國互聯網提供更多的中文物理知識。畢竟中國沒有Physics Stack Exchange與Physics Forum這些優秀的網站。知乎雖然有缺點，但是也沒有什麼別的選擇。
Acknowledgement
感謝中山大學何廣平教授耐心而誠懇的郵件。也感謝北京郵電大學魏春艷博士富有啟發的交談。
學習材料
QKD：BB84 協議
施密特分解：Schmidt decomposition_Wikipedia
量子計算（張量積，partial trace）：量子計算與量子信息的一些材料
引用
畢竟不是正經論文我就不遵守引用規範了。
MLC no-go定理的原始證明Lo, Hoi Kwong, and H. F. Chau. "Is Quantum Bit Commitment Really Possible?." Phys.rev.lett 78.17(1996):3410-3413.Mayers, Dominic. "Unconditionally Secure Quantum Bit Commitment is Impossible." Phys.rev.lett 78.17(1997):3414.Yuen的對原始證明的反駁H. P. Yuen, quant-ph/0006109, 0305144, 0505132, 0702074H. P. Yuen, arXiv:0808.2040目前公認正確的MLC no-go定理的證明
DAriano, Giacomo Mauro, et al. "Reexamination of quantum bit commitment: The possible and the impossible." Physical Review A76.3(2006):399-406.Chiribella, Giulio, et al. "A short impossibility proof of quantum bit commitment." Physics Letters A 377.15(2013):1076-1087.何廣平教授認為是無條件安全的QBC協議：Phys. Rev. A 74, 022332 (2006)arXiv:1307.7318基於相對論的QBC協議Kent, Adrian. "Unconditionally Secure Bit Commitment." Physical Review Letters 83.7(1998):1447-1450.Lunghi, T, et al. "Experimental bit commitment based on quantum communication and special relativity." Physical Review Letters111.18(2013):180504.Liu, Y., et al. "Experimental unconditionally secure bit commitment. " Physical Review Letters 112.1(2014):010504.量子安全雙邊計算
Lo, Hoi Kwong. "Insecurity of quantum secure computations." Physical Review A 56.2(1996):1154-1162.基於QKD的QPQ協議Jakobi, Markus, et al. "Practical private database queries based on a quantum-key-distribution protocol." 83.2(2011):773-781.量子資源理論Chitambar, Eric, and G. Gour. "Quantum Resource Theories." (2018).
推薦閱讀：
