后量子密码并不是量子密码的升级,本义指可以抵抗量子计算攻击的密码。
目前,有一些计算复杂性问题尚未找到高效的量子计算攻击方法,基于这些问题设计的密码叫做后量子密码,主要包括基于格的密码（基于格上的最短向量、最近向量等困难问题设计的密码）、基于纠错码的密码（基于随机编码的译码困难问题设计的密码）和基于多变量的密码（基于多变量二次方程求解困难问题设计的密码）。
一、基于格的密码
作为一个数学概念,格的研究可追溯到17世纪的约瑟夫·拉格朗日和卡尔·F高斯等著名数学家。格最早应用到密码学是作为一个分析工具出现的,即利用LLL格基归约算法来分析Knapsack、RSA、NTRU等密码算法。
格作为一种设计工具用于设计密码算法的研究始于1996年,但这些密码算法的密钥尺寸巨大,无法满足现实应用需求。2005年,格密码算法的研究有了突破性进展,与第一代格密码算法相比,密钥尺寸得到极大改善。目前,格密码已经成为最具吸引力的后量子密码算法之一。谷歌公司已在其浏览器Chrome中测试了基于格的密钥交换算法。微软公司也公开了其开发的基于格的密钥交换算法的源代码,并分析了其经典安全性和量子安全性。
二、基于纠错码的密码
基于纠错码的密码的安全性依赖随机线性码译码的困难性,该问题是一个数学困难问题。基于纠错码的密码的密钥尺寸较大,因此,没有能像基于因子分解与离散对数的公钥密码那样被广泛使用。
基于Goppa码的McEliece公钥加密算法是最著名的基于纠错码的公钥密码算法,不过其密钥尺寸太大使效率很低。其后,人们尝试用其他纠错码来替换Goppa码,但很多都被攻破了。
三、基于多变量的密码
多变量密码系统的安全性建立在求解有限域上随机产生的非线性多变量多项式方程组的困难性上,其优点是运算均在较小的有限域上完成,因此效率较高。其不足是密钥尺寸较大,且随着变量个数与多项式次数的增多,密钥尺寸增长较快。
如今,公认高效、安全的多变量密码体制不多,但该研究方向在密码分析方面得到了许多不错的研究成果,可广泛应用在分析对称密码。
