後量子密碼並不是量子密碼的升級,本義指可以抵抗量子計算攻擊的密碼。

现在,有一些計算複雜性問題尚未找到高效的量子計算攻擊方法,基於這些問題設計的密碼叫做後量子密碼,主要包括基於格的密碼（基於格上的最短向量、最近向量等困難問題設計的密碼）、基於糾錯碼的密碼（基於隨機編碼的譯碼困難問題設計的密碼）和基於多變量的密碼（基於多變量二次方程求解困難問題設計的密碼）。

一、基於格的密碼

作為一個數學概念,格的研究可追溯到17世紀的約瑟夫·拉格朗日和卡爾·F高斯等著名數學家。格最早應用到密碼學是作為一個分析工具出現的,即利用LLL格基歸約算法來分析Knapsack、RSA、NTRU等密碼算法。

格作為一種設計工具用於設計密碼算法的研究始於1996年,但這些密碼算法的密鑰尺寸巨大,無法滿足現實應用需求。2005年,格密碼算法的研究有了突破性進展,與第一代格密碼算法相比,密鑰尺寸得到極大改善。现在,格密碼已經成為最具吸引力的後量子密碼算法之一。谷歌公司已在其瀏覽器Chrome中測試了基於格的密鑰交換算法。微軟公司也公開了其開發的基於格的密鑰交換算法的原始碼,並分析了其經典安全性和量子安全性。

二、基於糾錯碼的密碼

基於糾錯碼的密碼的安全性依賴隨機線性碼譯碼的困難性,該問題是一個數學困難問題。基於糾錯碼的密碼的密鑰尺寸較大,因此,沒有能像基於因子分解與離散對數的公鑰密碼那樣被廣泛使用。

基於Goppa碼的McEliece公鑰加密算法是最著名的基於糾錯碼的公鑰密碼算法,不過其密鑰尺寸太大使效率很低。其後,人們嘗試用其他糾錯碼來替換Goppa碼,但很多都被攻破了。

三、基於多變量的密碼

多變量密碼系統的安全性建立在求解有限域上隨機產生的非線性多變量多項式方程組的困難性上,其優點是運算均在較小的有限域上完成,因此效率較高。其不足是密鑰尺寸較大,且隨着變量個數與多項式次數的增多,密鑰尺寸增長較快。

如今,公認高效、安全的多變量密碼體制不多,但該研究方向在密碼分析方面得到了許多不錯的研究成果,可廣泛應用在分析對稱密碼。