密码体制如何应对“量子霸权”?
黄金假面
随着量子计算的快速发展,量子模拟计算和量子计算架构的逐步实现,现有密码系统的安全性受到巨大的威胁。如何在后量子时代来临之际,保障数据的机密性、完整性和密文数据的有效处理和利用,是学术界和工业界面临的研究热点和迫切需要解决的问题。
密码学界很早就在研究可以抵抗量子计算机攻击的密码算法,最早可以追溯到1978到1979年的McEliece加密、Merkle哈希签名等。但在那时,量子计算机对密码算法的威胁并没有很明确,也没有“后量子”的概念。直到最近十几年,后量子密码的重要性逐渐显现出来。
现行的四种后量子公钥密码算法:
一、基于哈希函数的公钥算法
基于hash算法构造的签名体制,最经典的是Merkle hash树签名体制,由传统的hash函数和任意的一次性签名算法,共同构造出一个完全二叉树来实现数字签名。由于该体制不依赖于大整数分解和离散对数等难解问题,所以被认为可以抵抗量子密码分析。
尽管Merklehash树签名体制在签名效率方面具有RSA等签名体制不可比拟的优势,但因为签名数量和签名大小的限制,Merkle hash树数字签名并没有得到很好的应用。事实上,这类签名都是一次性签名,况且不能用于公钥加密,也无法实现原有系统中的许多密钥交换功能,因而难以在开放环境下大量使用。
二、基于编码理论的公钥算法
基于编码理论构造的公钥体制,其理论基础是解码问题的困难性,即仅在已知生成矩阵的情况下,在码空间中寻找一个码字与已知码的Hamming距离最短。如果已知码为0,则问题就是最小权重问题。
Berlekamp、McEliece和Tilborg证明,最小权重问题是NP-完全问题。McEliece于1978年提出了基于Goppa码的加密算法,但该算法的密钥空间太大,不能用于数字签名,且安全性近年来也一直受到挑战,2008年荷兰的研究人员就宣称,已经能成功破译该算法。
尽管对该算法的改进可以用于数字签名,但总的来说,基于编码理论的许多签名算法的安全性一直受到质疑。到目前为止,尚具有较好安全性的基于编码理论的公钥签名体制只有由Courtois等人提出的CFS签名体制。
三、基于格的公钥算法
基于格的公钥密码是基于格理论建立的密码学技术。格是指N维线性空间的离散加法子群。
rId8
比较著名的有Goldreich、Goldwasser和Halevi在1996年提出的GGH密码体制,Ajtai和Dwork在1996年提出的Ajtai-Dwork密码体制等,但最有代表性的算法是由美国数学家Hoffstein、Pipher和Silverman于1996年提出,并在以后作了修改的NTRU公钥密码系统,它既可用于加密,也可用于签名。
但格理论中有许多难解问题,迄今也没有发现有效的量子求解算法能够抵抗量子计算机的攻击。
四、基于多变量的公钥算法
多变量公钥密码体制是一大类各具特色的公钥密码算法的统称,也是近年来MASK后量子公钥密码的研究热点。这类体制主要基于有限域上的多元二次多项式方程组的难解性。与RSA、DH、ECC相比,多变量公钥密码的安全性很难被证明等价于一个已知的可简单表述的数学难题,因而也被认为是很难找到相应量子攻击算法的难题,从而被看成具有抗量子计算的性能。
MASK首先引出一种快速签名算法BPQS,该算法是MASK的抗量子密码算法的核心,结合多元二次多项式方程组,其签名长度和私钥长度具有很大的优势。
其原理是利用专用链或图像结构,以减少密钥生成、签名、验证的成本,以及签名的大小。当一个密钥被重用于合理数量的签名时,BPQS会优于现有的哈希算法,如果有需要的话,它还支持一种回滚机制,可允许实际数量不限的签名。
相较于其它抗量子算法,MASK抗量子算法开销小、签名和验证速度更快,并且能够有效抵抗量子计算攻击,安全性非常高。
