概要

• 量子計算機將對網(wǎng)絡(luò)安全構(gòu)成重大威脅。大型容錯量子計算機建造出來后，最常用的密碼系統(tǒng)將分崩離析。這一威脅事關(guān)重大，其應對具有緊迫性。
• 保護完全經(jīng)典的協(xié)議，免受量子技術(shù)武裝的對手是可能的，但需格外謹慎，不能僅限于認真選擇密碼系統(tǒng)。
• 量子技術(shù)還會對網(wǎng)絡(luò)安全帶來積極影響。采用最先進技術(shù)的量子設(shè)備可用來提升安全性，實現(xiàn)傳統(tǒng)不可能實現(xiàn)的任務，比如具有完美安全性的密鑰擴展。量子計算機將成為未來通信和計算網(wǎng)絡(luò)中不可或缺的一部分，我們需要開發(fā)實用的方法，使用與安全經(jīng)典計算具有相同安全保證的量子計算機。

計算機系統(tǒng)和攻擊者在軟硬件方面與時俱進，不斷創(chuàng)新非常重要。人們可以想象到的最引人注目的發(fā)展，莫過于計算模型范式的變化。量子技術(shù)似乎讓我們接近這種變化。本文探究網(wǎng)絡(luò)安全和量子技術(shù)研究的交叉領(lǐng)域。

量子技術(shù)時代的開端。量子論的發(fā)展是20世紀的重大科學革命之一。從早期一直到完整數(shù)學形式主義的發(fā)展，以及隨后第一批應用(比如晶體管和超導體等)，量子論在許多不同的環(huán)境中非常成功。然而，按預期控制量子系統(tǒng)的能力有限，這限制了技術(shù)應用的種類。

近年來，這種情況發(fā)生了變化，對量子系統(tǒng)的控制已大大增強，而由于興趣和投入加大，加上已有的科學突破，似乎有希望在不遠的將來取得進一步的進展。全球多國已啟動了國家量子技術(shù)計劃，投入的資金龐大。谷歌、IBM、微軟和BAT等各大工業(yè)公司及眾多量子初創(chuàng)公司已設(shè)立了開發(fā)量子硬件的實驗室。這掀起了所謂的“第二場量子革命”：按預期操控量子系統(tǒng)的能力引領(lǐng)了新時代，眾多新技術(shù)層出不窮，在一些情況下有望取代現(xiàn)有的解決方案。

可以說，最重要的量子技術(shù)將是開發(fā)利用量子現(xiàn)象的計算設(shè)備(即量子計算機)。量子計算機可能會成為顛覆性創(chuàng)新，提供比經(jīng)典計算機強大得多的計算能力。

早已取得了杰出的量子技術(shù)成就。僅舉兩例：谷歌最新的量子處理器Bristlecone擁有創(chuàng)記錄的72個量子比特，錯誤率很低。衛(wèi)星量子密鑰分配已實現(xiàn)，可以在7600千米的跨洲距離上實現(xiàn)信息理論安全加密。

量子網(wǎng)絡(luò)安全。大型量子計算機的發(fā)展及其帶來的額外計算能力會給網(wǎng)絡(luò)安全帶來可怕的后果。比如說，如果開發(fā)出足夠大的“容錯”通用量子計算機，可高效解決分解因子和離散對數(shù)之類的重要問題——這些問題的難度確保了許多廣泛使用協(xié)議(比如RSA、DSA和ECDSA)的安全性。然而，應對采用量子技術(shù)帶來的重大風險不是網(wǎng)絡(luò)安全界的唯一問題，量子技術(shù)在網(wǎng)絡(luò)安全界必將發(fā)揮作用。

量子網(wǎng)絡(luò)安全領(lǐng)域的研究影響通信和計算安全和隱私的方方面面，這都離不開量子技術(shù)的發(fā)展。

量子技術(shù)被對手利用時對網(wǎng)絡(luò)安全會帶來消極影響，但被誠實方使用時則會帶來積極影響。量子安全研究一般分為三類，這取決于誰可以使用量子技術(shù)、這種技術(shù)有多先進(見圖1)。在第一類中，我們確保目前可以執(zhí)行的任務保持安全;在另兩類中，我們探究量子技術(shù)帶來的新前景。

圖1.量子網(wǎng)絡(luò)安全研究領(lǐng)域的示意圖

與密碼學中一樣，先假設(shè)資源方面的最糟糕場景：誠實方完全借助經(jīng)典技術(shù)(沒有量子能力)，而對手可使用任何量子技術(shù)(不管這項技術(shù)目前是否存在)。尤其是，假設(shè)對手擁有大型量子計算機。確保經(jīng)典協(xié)議的安全和隱私保證完好無損就叫后量子安全。

在第二類中，我們允許誠實方使用量子技術(shù)以獲得增強的屬性，但限制只能使用那些現(xiàn)有的量子技術(shù)。同樣，對手可以使用任何量子技術(shù)。在這一類中，我們專注于獲得經(jīng)典功能，但通過使用目前最先進的量子設(shè)備，能夠增強經(jīng)典協(xié)議的安全或效率。

在第三類中，著眼于更長遠的未來，分析因量子計算機而帶來的協(xié)議具有的安全和隱私。到時會有涉及量子計算機和通信，處理量子信息的任務，有關(guān)方想保持數(shù)據(jù)的隱私，又想要所處理任務的安全有保證。這段時期不會太遙遠，因為如今開發(fā)的量子設(shè)備已突破量子計算的限制，經(jīng)典超級計算機可以模擬量子計算。

這三類涵蓋網(wǎng)絡(luò)網(wǎng)絡(luò)的所有方面。本文著重介紹量子計算機給密碼攻擊和利用新量子硬件漏洞的攻擊帶來的影響。至于利用現(xiàn)有經(jīng)典硬件其他漏洞的方法(比如時序攻擊)，我們預計不會顯著受益于量子技術(shù)，因而不作深入探討。

量子計算的誤區(qū)與現(xiàn)實

量子計算機常被描述成神奇的計算設(shè)備，可瞬間解決幾乎任何難題。實際上，量子計算機的能力沒那么夸張。我們下面澄清下量子計算機和量子對手的計算能力，以及四個最常見的誤解。

誤區(qū)1.量子計算機執(zhí)行運算方面比經(jīng)典計算機快得多。

從每秒執(zhí)行大量操作的角度來看，量子計算機并非速度更快。量子計算機之所以能加快計算速度，是由于量子論允許算法支持經(jīng)典計算機幾乎不可能執(zhí)行的操作。因此，實現(xiàn)加速需要發(fā)明適當使用這些操作的新算法，這并非易事。確實，加速效果主要取決于考慮的特定問題。這解釋了為什么量子對手只能破解某些公鑰密碼系統(tǒng)，其他人只需稍加改動(比如改動密鑰長度)就能保持安全。

誤區(qū)2.量子計算機同時執(zhí)行(概率)計算的所有分支，可以立即找到接受路徑。

量子計算機以一種獨特的方式探索新的可能性或計算分支。這類似經(jīng)典概率計算機(Bpp)，重要區(qū)別在于量子計算機的行為存在帶有復雜值的“概率”。該行為導致某些分支被“取消”。該屬性以及利用它的算法帶來量子加速。然而在量子計算結(jié)束時，僅通過一次讀出/測量來獲得結(jié)果，因此所有“未實現(xiàn)”的分支都不起作用，與這個誤區(qū)恰好相反：量子計算機并行執(zhí)行所有分支，某人可以提取那些分支中的所有信息。

誤區(qū)3.量子計算機可以有效地解決NP完全問題(比如旅行商問題，即TSM問題，是最基本的路線規(guī)劃問題)。

量子計算機可以有效解決的一類決策問題名為BQP。它與其他已知類的(推測)關(guān)系可從圖2中看到。尤其是，NP并不包含在BQP中，量子計算機無法有效地解決NP完全問題。不過值得一提的是，量子計算機在處理BQP之外的許多問題(比如二次搜索加速)時，可提供多項式或恒定加速，包括針對NP完全問題的這種加速。針對許多任務，即便這種小幅加速也可能很重要。比如在網(wǎng)絡(luò)安全界，它影響保證要求的安全級別所需要的密鑰大小。

圖2.復雜性類的推測關(guān)系。

誤區(qū)4。使用量子計算機難以解決問題，足以使密碼協(xié)議免遭任何量子攻擊。

這是必要但并非充分的條件。量子攻擊者會以各種方式使用量子性，不僅為了更快地解決一些經(jīng)典問題。接下來我們舉例(疊加攻擊)，并指明安全定義和證明技術(shù)都需要改動。

后量子安全：量子對手

我們現(xiàn)在需要對付量子攻擊者，這有三大原因。首先，安全有可能被未來的技術(shù)破解。比如，如果一些機構(gòu)攔截并存儲發(fā)送的加密電子郵件，開發(fā)出量子計算機后，可以用來解密郵件。其次，開發(fā)后量子安全的密碼解決方案，獲得高效率。對這些解決方案的安全樹立信心，需要多個獨立頂尖研究小組開展多年的研究。第三，我們改變密碼基礎(chǔ)設(shè)施需要數(shù)年的時間。

根據(jù)對手使用“量子能力”的方式，可將后量子密碼學研究分為三類(見圖1)。第一類是對手是經(jīng)典對手，擁有還能解決BQP問題的額外能力。換句話說，這類對手如同標準的經(jīng)典對手，可另外訪問oracle/量子計算機。在第二類和第三類中，我們?yōu)閷κ仲x予額外的能力，比如允許他們發(fā)送量子態(tài)的輸入(查詢)，然后使用(量子)輸出及其量子計算機oracle，以危及協(xié)議安全。第二類討論安全定義的建模和改動以及直接后果。第三類討論這種新的量子安全模型中(涉及的)證明技術(shù)所需的改變。

應注意，就使用的技術(shù)而言，后量子安全類別中的所有協(xié)議都是完全經(jīng)典的協(xié)議。所有如實步驟都在經(jīng)典設(shè)備中實現(xiàn)。了解量子計算(問題的難度)和總體量子技術(shù)(為其他類型的攻擊建模)對于證明安全性至關(guān)重要。

防范使用oracle量子計算機的敵手。第一個也是研究最深入的領(lǐng)域是，確保所用協(xié)議的安全性基于對量子計算機來說仍很難的問題具有的難度。這顯然是優(yōu)先事項，因為一旦制造出量子計算機，攻擊涉及的問題對量子計算機并不難的密碼系統(tǒng)將輕而易舉。如圖2所示，存在BQP之外的NP問題;在對手可以訪問oracle量子計算機的情況下，公鑰密碼仍切實可行。

有許多密碼系統(tǒng)可以防御這種類型的攻擊。它們可以分為基于散列、基于代碼、基于格、多元和密鑰等密碼技術(shù)。這里探討三個問題：信心、易用性和效率。

問題很難，而在一些情況下，問題源自包含復雜性類的理論含義，這種觀念常基于無法找到高效的解決方案或無法改進現(xiàn)有解決方案，盡管許多小組長期付出了努力。為經(jīng)典計算機分解因子面臨的困難就是這種情況。我們針對量子計算機分析密碼系統(tǒng)中所用的問題具有的難度時，我們的信心一般更弱。更重要的是，量子算法和量子復雜性理論方面的研究也是新的，從量子對手的角度對系統(tǒng)進行適當?shù)拿艽a分析還不如經(jīng)典計算來得透徹。

最后，可能最大的挑戰(zhàn)是效率問題。對于國防和金融市場等某些應用而言，即使以性能較差為代價，也需要最高安全性，但對于眾多日常應用，服務速度變慢不可接受?？紤]到所有方面，現(xiàn)有的后量子密碼系統(tǒng)缺乏效率。改進這方面或確定哪些應用可以容忍這其中一方面效率較低，是活躍的研究領(lǐng)域。

疊加攻擊：改動安全概念。安全性通常根據(jù)對手在某些假設(shè)的交互活動中獲勝的可能性方面來加以定義。比如說，有人將不可區(qū)分(indistinguishability)定義為對手無法以高于50%的概率獲勝的活動，這表明隨機猜測明文比特是所能采取的最好方法。

在該活動中，對手獲得使用學習階段的額外能力，可以請求所選擇明文的密文。提供這些額外能力的動機基于這種場景：對手可能說服誠實方加密所選擇的信息。為了確保隱私，這番操作不會為對手在試圖解密消息方面提供任何優(yōu)勢。現(xiàn)在，我們要考慮這種活動中有另外的能力進行量子查詢(并接收量子答案)的對手。量子對手可能嘗試使用這些疊加密文來破解密碼系統(tǒng)。

值得強調(diào)的是，擁有疊加與使用所有疊加項不一樣。比如說，如果某人直接測量這種疊加，會收到隨機選擇的明文密文，安全不會受到危害。相反，攻擊需要在可揭示密碼系統(tǒng)隱藏結(jié)構(gòu)的另一種量子算法中使用密文狀態(tài)的這種輸出疊加。

防范量子對手的證明技術(shù)。我們應該將量子對手的內(nèi)部空間建模為通用量子態(tài)，將其所有動作以及與誠實方的通信建模為通用量子操作。用量子手段為對手建模有兩個影響。一方面，它給了對手更多的偏離/攻擊方式，比如上述的疊加攻擊中。另一方面，它對如何證明安全性有影響，因為模擬視角需要模擬量子過程而不是經(jīng)典過程。請注意，表明證明技術(shù)不適用并不意味著找到破解相應密碼系統(tǒng)的攻擊，只意味著它不再可以被證明是安全的。

量子增強安全：面向經(jīng)典用戶的量子設(shè)備

量子技術(shù)還可以為網(wǎng)絡(luò)安全研究提供優(yōu)勢。不妨考慮在(誠實)協(xié)議中加入量子步驟的可能性，旨在與相應的完全經(jīng)典環(huán)境相比獲得某些改進。改進在原則上是可行的，最有名的例子就是量子密鑰分配(QKD)。在QKD中，使用不可信的量子通道和驗證身份的經(jīng)典通道，可以在空間上分離的雙方之間建立共享的密鑰，并擁有信息理論安全。僅使用經(jīng)典通信，不可能完成這項任務(實際上是信息理論安全密鑰擴展)。重要的是，擁有信息理論安全的協(xié)議意味著，其安全并不基于任何計算假設(shè)，因此即使攻擊者使用量子計算機也保持安全。量子增強的另一個例子是量子指紋，雙方可使用少量通信來確定是否在共享同樣的比特串。

量子增強安全領(lǐng)域的大部分研究針對QKD，然而存在其他諸多協(xié)議和功能，它們承認增強，需要類似或稍微復雜的量子技術(shù)。其中一些技術(shù)包括：量子隨機數(shù)生成器、量子指紋識別、量子數(shù)字簽名、量子硬幣翻轉(zhuǎn)、電子投票、拜占庭協(xié)議、量子貨幣、量子秘密信息檢索、安全多方計算(SMPC)和位置驗證。

量子技術(shù)發(fā)展迅速，越來越多的量子增強協(xié)議變?yōu)楝F(xiàn)實，實用量子設(shè)備的前景隨之廣闊起來。比如說，除了各方之間的簡單量子通信外，我們現(xiàn)在可以讓各方擁有小型量子處理器。當前是進行這種研究的大好時期，我們可以考慮量身定制的構(gòu)造，以增強特定的相關(guān)加密協(xié)議(比如電子投票或SMPC)的性能。

量子實現(xiàn)的安全：安全使用量子計算機

量子計算機在處理許多問題時具有計算方面的優(yōu)勢。如果有這種設(shè)備，人們在處理還需要隱私和安全的任務時，自然想利用這額外的計算能力;換句話說，我們尋求量子支持的協(xié)議具有安全性。所有安全概念都需要改動，才適用于量子信息和量子計算，比如身份驗證、加密以及更復雜的概念(比如加密數(shù)據(jù)計算和安全多方計算)。當然，這種問題要具有意義，我們先要有相當龐大的量子計算設(shè)備，為日常問題提供實在的計算優(yōu)勢。我們有望很快突破經(jīng)典模擬的極限，正進入量子技術(shù)加速的時代。量子加速用于處理重要的日常問題的時間可能也不遠了。

這類研究正日新月異，已經(jīng)有許多協(xié)議，適用于量子加密、量子驗證、量子非延展性、盲量子計算、安全多方量子計算和功能量子加密等。有多種協(xié)議在不同的優(yōu)值方面進行優(yōu)化，比如最小化量子(或經(jīng)典)通信，最小化某幾個有關(guān)方的整體量子資源或量子資源，提供最高級別的安全(信息理論vs后量子計算)。

這類協(xié)議大多數(shù)需要雙方之間進行量子通信，在大多數(shù)情況下，須對通訊的量子信息進行量子計算。這引起了兩個問題：一個是理論上，一個是實踐上。要實現(xiàn)這種任務，需要與量子通信設(shè)備兼容的量子計算設(shè)備。一方面，量子通信的最佳平臺是光子型的，因為很容易遠距離發(fā)送用光子編碼的量子信息。另一方面，量子計算設(shè)備最有前途的一種方法基于超導量子位。對通信和計算而言，優(yōu)選的量子比特類型并不一致;此外，目前甚至不知道它們是否兼容。目前不知道超導量子計算機是否可以成為“網(wǎng)絡(luò)架構(gòu)”的一部分，因為它們目前用單體架構(gòu)來制造，不清楚是否有可能發(fā)送和接收量子態(tài)。

未來

安全通信和高效計算的能力對社會無比重要?；ヂ?lián)網(wǎng)和物聯(lián)網(wǎng)對這個世界產(chǎn)生了革命性的影響。今后5至10年，隨著量子技術(shù)成為主流計算和通信領(lǐng)域的一部分，我們會看到廣闊的前景。未來的網(wǎng)絡(luò)肯定同時包括經(jīng)典設(shè)備及鏈路，以及量子設(shè)備和鏈路。

實現(xiàn)復雜的經(jīng)典和量子通信網(wǎng)絡(luò)，就必須依賴牢固的新基礎(chǔ)：能夠預見并處理實際實施和新應用的復雜性。

圖3.未來的通信和計算網(wǎng)絡(luò)

后量子安全為經(jīng)典互聯(lián)網(wǎng)保持安全性鋪平了道路，而量子增強安全旨在從量子互聯(lián)網(wǎng)發(fā)展受益，以實現(xiàn)經(jīng)典通信無法取得的無與倫比性能。同時，具備各種功能的量子云服務正普及開來。量子支持的安全提供了平臺，使?jié)撛谟脩舸_信量子云中這種前所未有的新計算能力，具有適當?shù)臏蚀_性、可靠性和隱私標準。