象链洞见|浅析后量子安全公钥密码技术的发展

随着量子计算的快速发展，量子模拟计算和量子计算架构的逐步实现。现有密码系统的安全性受到巨大的威胁。如何在后量子时代来临之际，保障数据的机密性、完整性和密文数据的有效处理和利用，是学术界和工业界面临的研究热点和迫切需要解决的问题。

象链科技也一直关注着行业内最新的进展，本文简要介绍了近年来后量子密码的解决方案，包括基于纠错编码、基于格、基于 hash 等多种方式的抗量子公钥体制，尤其是基于格的后量子密码和全同态加密。

1.四种后量子公钥密码算法

目前的密码体制通常分为对称密码与非对称密码（也称公钥密码）。而近年来公钥密码体制已经显示出其独特的优势。目前几乎所有的信息安全系统，都使用了公钥密码体制，其中绝大部分使用了RSA、ElGamal和ECC等几个最为著名的公钥体制，以实现密钥交换、数字签名和身份认证等。

抵抗量子计算攻击的公钥密码，可以依据计算环境分为两大类，一类基于量子计算和量子通信环境，属于量子密码。量子密码的优势在于确能抗量子计算机的攻击，安全性很高，但建立量子密码系统需要昂贵的量子信道，在量子通信尚未普及的时候，应用范围受到极大限制，所以至少在量子通信问题解决之前并不能大范围适用。

另一类基于经典计算（即非量子计算）环境，属于经典抗量子密码。通常，当人们说到后量子公钥密码时，更多的是指这一类密码。

除量子公钥密码外，后量子公钥密码都是基于不能转换成离散傅立叶变换的数学难题而建立，主要有以下几种类型。

（1）基于hash算法构造的Merkle型签名算法

基于hash算法构造的签名体制，最经典的是Merkle hash树签名体制，由传统的hash函数和任意的一次性签名算法，共同构造出一个完全二叉树来实现数字签名。由于该体制不依赖于大整数分解和离散对数等难解问题，所以被认为可以抵抗量子密码分析。尽管Merklehash树签名体制在签名效率方面具有RSA等签名体制不可比拟的优势，但因为签名数量和签名大小的限制，Merkle hash树数字签名并没有得到很好的应用。事实上，这类签名都是一次性签名（一次一密），况且不能用于公钥加密，也无法实现原有系统中的许多密钥交换功能，因而难以在开放环境下大量使用。

（2）基于编码的公钥算法

基于编码理论构造的公钥体制，其理论基础是解码问题的困难性，即仅在已知生成矩阵的情况下，在码空间中寻找一个码字与已知码的Hamming距离最短。如果已知码为0，则问题就是最小权重问题。

Berlekamp、McEliece和Tilborg证明，最小权重问题是NP-完全问题。McEliece于1978年提出了基于Goppa码（一种代数编码）的加密算法，但该算法的密钥空间太大，不能用于数字签名，且安全性近年来也一直受到挑战，2008年荷兰的研究人员就宣称，已经能成功破译该算法。尽管对该算法的改进可以用于数字签名，但总的来说，基于编码理论的许多签名算法的安全性一直受到质疑（许多签名算法相继被破译）。到目前为止，尚具有较好安全性的基于编码理论的公钥签名体制只有由Courtois等人提出的CFS签名体制。

（3）基于格的公钥算法

基于格的公钥密码是指在大维数的格上，基于最短向量问题（SVP）和最近向量问题 （CVP ）等数学难题而构造的公钥密码体制。SVP 是指在大维数格中寻找长度最短的非零向量，而CVP是指在大维数格中寻找和固定向量距离最短的向量，这两个问题都是N P 难问题。比较著名的有Goldreich、Goldwasser和Halevi在1 996 年提出的GGH密码体制，Aj tai和Dwork 在1996年提出的Ajtai-Dwork密码体制等，但最有代表性的算法是由美国数学家Hoffstein、Pipher和Silverman于1996年提出，并在以后作了修改的NTRU公钥密码系统，它既可用于加密，也可用于签名。基于格上的难解问题设计的公钥加密算法，由于没有大整数的运算，运算速度和RSA相比要快得多。更重要的是，目前还没有针对基于格中密码体制的量子算法。目前NTRU算法由NTRU公司（资本雄厚且有美国政府支持）拥有，其理论和工程指标都日趋成熟。NTRU公司不仅在多国注册了NTRU算法的基础性专利，还开发了一系列示范性产品（IC卡、手机、3G、无线互联网、电子商务、可信计算等），并试图就该算法建立相应的国际标准。不过，由于算法的安全性还没有获得充分认可，特别是其签名的安全性远低于加密的安全性，不太适用于建立网络信任体系，加之知识产权的障碍，所以该算法并没有得到广泛应用。

（4）基于多变量的公钥算法

多变量公钥密码体制（Multivariate-quadratic-polynomialsPublicKeyCryptosystem，简称MQ或MPKC）是一大类各具特色的公钥密码算法的统称，也是近年来后量子公钥密码的研究热点。这类体制主要基于有限域上的多元二次多项式方程组的难解性。与RSA、DH、ECC相比，多变量公钥密码的安全性很难被证明等价于一个已知的可简单表述的数学难题，因而也被认为是很难找到相应量子攻击算法的难题，从而被看成具有抗量子计算的性能。最早提出的多变量密码体制是在1988年，但因其很快就被攻破，并且很多变型也没有达到安全的标准，使得这个体制一直不受重视。直到2000年以后，出于抗量子算法攻击的考虑，对多变量的研究才重新受到重视。

2.后量子公钥密码研究新的特点

目前，国际上关于后量子公钥密码的研究趋势有以下几个明显的特点。

一是研究步伐逐步加快。这从近几年召开的后量子密码会议可见一斑。2006年，在比利时的Leuven召开了第一届国际后量子密码学会议，2008年在美国的Cincinnati召开了第二届，2010年在德国的Darmstadt召开了第三届，基本上是两年一届。但今年，将在中国台北召开第四届，且以后将每年一届，时间节奏明显加快。

二是更加注重相关基础研究。例如对近年提出的后量子算法的数学理论基础有了更多的探讨，加强了对算法的安全性分析，对与抗量子性能相关的量子复杂性理论的研究也越来越多。

三是更加注重算法的有效性与可用性。因为可实用的量子计算机的问世已越来越迫近，可用性与效率都是无法回避的问题。

四是各国政府的支持力度也越来越大。表面上看，后量子密码的研究属于学术领域，但背后往往有政府的参与，因为这是涉及未来若干年国家安全的重大学术问题。

- END-

关于象链科技

象链科技（上海）有限公司，是一家快速成长的区块链领先企业，一直以“区块链技术 服务民生”为理念，致力于区块链基础研究和应用研发，为人工智能、智慧城市、智慧政务、民生服务的发展助力。象链科技的愿景是打造区块链+人工智能数字经济新生态，拥有首个融合ABCD（A-AI B-Blockchain C-Cloud D-BigData）产业的高性能自主研发公链底层兼容联盟链平台EleChain。

—-

编译者/作者：象链科技

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。