量子算法與後量子密碼學

量子計算也許早就不是什麼熱門話題了，那我也來炒個冷飯，科普下針對密碼學的量子算法，以及抗量子攻擊的後量子密碼學。

首先，簡單介紹下什麼是量子計算，量子計算是一種基於量子力學原理的計算方式，利用量子比特（qubit）進行計算，與傳統計算機不同，量子計算機利用量子力學中的量子疊加、糾纏等現象，理論上在處理某些特定問題時展現出極大的計算速度優勢。

量子門及門矩陣，圖片來自知乎，作者見水印

爲什麼要限制在特定問題呢，我的理解是量子計算機和量子算法現在都還沒完善到可以解決所有計算問題的程度，量子算法只在某些特定設計的問題上，藉助量子疊加和糾纏的特性，得到了很好的計算結果（指速度上），不過量子計算機的設計不在今天的討論之列，作爲密碼學科普文章，今天我們主要介紹針對密碼學問題的量子算法，以及如何抗量子攻擊。

各種量子計算機設計

在引入量子算法之前，先簡單介紹一下它今天攻擊的目標，大名鼎鼎的RSA，RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的，RSA就是他們三人姓氏開頭字母拼在一起組成。這個密碼算法有多重要呢？因爲這個貢獻，三人被授予了圖靈獎。RSA算法自提出以來一直是最廣泛使用的公鑰加密系統之一，它基於大整數分解問題，即破解它的難度，與將一個大整數分解爲兩個素數的難度相同。

這個過程很難嗎，不就是分成兩個素數嗎，小學都學過素數了，2，3，5，口算算算不就行了（

還真不是，這是一個主觀上很具有誤導性的問題，素數分解沒有高效的公式，只能窮舉，數字小的時候特別容易，但是當數字特別大時，只能靠計算機的計算速度了，這也是RSA安全性的底氣。

那是不是量子計算機計算速度超快，可以快速窮舉所有的素數？

是，也不是，這就是著名量子算法Shor算法的精妙之處，Shor算法是由彼得·肖爾（Peter Shor）於1994年提出的，它是一種基於量子計算的整數分解算法。與傳統的算法如大整數因子分解相比，Shor算法在量子計算機上具有指數級別的加速優勢。

Shor算法的基本思想是利用量子計算的並行性和量子疊加原理，對大整數進行因子分解。算法的主要思想如下是，首先生成一個隨機數r，並與待分解的大整數n相除，得到一個小整數q。然後對q進行量子隨機漫步，即不斷地對q進行量子旋轉門操作，直到找到一個因子。最後，用找到的因子去整除n，重複步驟（1）和（2），直到n分解完成。

Shor算法量子實現線路圖

可能確實，看不懂什麼原理，只要知道這個算法在量子計算機上跑的飛快就行了，如果量子計算機被髮明出來了，那麼所有依賴於RSA的加密系統就全部崩潰了。而且，通過對shor算法原理的剖析，我們可以知道，對於任何具備轉化爲求週期函數的週期爲目標的問題都可以用同樣算法以指數加速來快速解決，比如離散對數(ElGamal), ECC之類的非對稱加密算法都可以用同樣的思想來解決。所以說，量子算法對密碼學的打擊是毀滅性的。

當然，我們這種密碼工作者肯定不會坐以待斃，所以一個新的方向--後量子密碼學誕生了，所謂“後”，是因爲量子計算機的出現，現有的絕大多數公鑰密碼算法（RSA、Diffie-Hellman、橢圓曲線等）能被足夠大和穩定的量子計算機攻破，所以可以抵抗這種攻擊的密碼算法可以在量子計算和其之後時代存活下來，所以被稱爲“後”量子密碼。也有人稱之爲“抗量子密碼”，說的都是一個意思。英文中的表述是："Post-quantum Cryptography (PQC)"，或者 "Quantum-resistant cryptography"。

實現後量子密碼算法主要有4 種途徑，基於哈希函數，基於編碼，基於多變量和基於格，其中，基於格的密碼算法最受關注，因爲其計算速度快、通信開銷較小，且能被用於構造各類密碼學算法和應用，因此被認爲是最有希望的後量子密碼技術。

格的定義，其實可以看做作爲基的向量生成的線性空間

下面我們稍微介紹一下基於格的密碼算法的原理，格(lattice)是一種數學結構，定義爲一組線性無關的非0向量（稱作格基）的整係數線性組合。下圖表示了一個二維格和兩組不同的格基：

二維格可以理解爲平面點陣

一個格的格基可以不是唯一的，例如， ((2,1),(1,1)) 和 ((1,0),(0,1)) 都是二維整數格的一組格基。從上圖中可以看到，即使是定義了同樣的格的兩組格基，其長度也可能相差很大。數學家和密碼學家們普遍認爲，對於一個維數足夠高的格，通過一組隨機選取的格基找到一組短格基，或得到一組線性無關的短格向量是困難的。這個問題稱作最短獨立向量問題(SIVP)。

而公鑰密碼學的安全源於數學上的困難問題，所以利用格上的困難問題可以很輕鬆的構建密碼算法。不過需要注意的是，這些算法的安全性，仍然依賴於有沒有可以快速求解其底層數學問題或直接對算法本身的高效攻擊算法。換句話說，這些算法被稱爲抗量子算法，是因爲目前沒有量子算法可以攻擊他們，而不是它們真正擁有抵抗所有（包括未來）量子算法的能力。這很有趣，所謂共同進化就是這麼一回事，武器越先進，防禦手段就越有利，但也反過來促進了攻擊手段的發展。