後量子密碼學是一個能夠抵抗量子電腦攻擊的加密演算法,當下廣泛使用的公鑰密碼系統,例如,RSA、ECC 橢圓曲線加密等等,它們的安全性都是建立在"大數質因數分解"或"計算離散對數"這些數學問題的難度上。不過量子電腦的出現,它可以利用量子力學的特性,從而具有破解以上提及的數學問題的能力,例如,Shor's algorithm。因此當大型量子電腦問世,或者已經能商用化時,就會出現重大危機,就是現在在網路通訊、銀行安全系統、密碼保護等中使用的加密技術都會被輕易攻破。
後量子密碼學的出現
後量子密碼學的目標是尋找和標準化新的加密演算法,這些演算法的安全性基於即使量子電腦也覺得很難解決的數學問題,從而確保我們的數位基礎設施在量子時代依然安全。
主要技術類型
後量子密碼學不僅僅是一種方法,它包含多個分支,基於不同的數學難題:
而這個系列就會介紹基於格的密碼學,格就像是一個在多維空間中無限延伸、按固定規律排列的點陣,可以想像成一個無限大的多維棋盤。
基於格的密碼學是一種利用點格(Lattice)上計算困難問題作為安全基礎的密碼學方法。在過去十年中,該領域取得了重大進展,主要聚焦於兩個基礎性的平均情況問題:短整數解(SIS) 和 帶誤差的學習(LWE) 問題(及其更高效的環基變體)。這些問題在最壞情況下格問題難解假設下具有可證明的硬度,並已被用於構建多種實際密碼應用。
核心特性
格密碼學具有多個吸引人的特性,使其在後量子密碼學中佔據核心地位:
抗量子攻擊性(Quantum Resistance)
與大多數依賴於整數分解或離散對數問題的數論密碼學(如Diffie-Hellman、RSA)不同,格密碼學所基於的問題(如SVP、CVP、SIS、LWE)目前尚未發現高效的量子演算法(Shor演算法對其無效)。已知的唯一優勢是通用的量子加速,這使得基於格的系統被認為是後量子時代的重要候選方案。
演算法簡單、高效且具高度並行性
格密碼系統的運算通常由模較小整數的向量和矩陣上的線性操作組成,演算法簡單,並易于高度並行化。特別是基於環的代數結構(如NTRU密碼系統)的構造可以非常高效,在某些情況下甚至比傳統數論系統更高效。
基於最壞情況硬度的強安全性保證
密碼學需要平均情況下的難解性,而Ajtai的開創性工作揭示了格問題在最壞情況與平均情況硬度之間的深刻聯繫:他證明某些格問題在平均情況下(對於密碼學有用的分佈)是難解的,若且唯若相關的格問題在最壞情況下是難解的。這意味著,密碼構造被證明是安全的,除非所有相關格問題的實例都能被高效解決。這提供了遠超傳統密碼學的安全性保證。
功能強大且多樣化的密碼學原語構造
格密碼學使得構建強大且多功能的密碼學原語成為可能,解決了密碼學中許多長期未決的問題。其中最著名的例子包括:
格的數學基礎與困難問題
同一個格,不同的基: 同一個格可以由不同的向量組(稱為「基」)來生成。
格密碼學的安全性基於以下公認的計算困難問題,特別是在只給定“壞基”時:
SIS和LWE正是這些最壞情況困難問題在平均情況下的表現形式,並直接用於密碼構造。
總結
格密碼學因其抗量子性、高效性、源自最壞情況的強安全保證以及構建強大應用(如FHE和ABE)的能力,成為後量子密碼學無可爭議的核心之一。
關於現代格密碼學的進一步閱讀,可參考以下資源(請注意該領域發展迅速,部分調查可能未能涵蓋最新進展):