2019-08-30 | 编辑：文/信息技术部

近年来，量子计算机技术发展迅速，它对传统公钥密码算法的安全性带来了潜在的巨大威胁。因此，美国、中国、欧盟等世界主要国家和地区纷纷开始研制抗量子计算机攻击的密码算法。其中，美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）于2016年面向全球征集抗量子密码算法标准，并于2017年底完成了首轮候选算法的征集工作。

在所有候选算法中，基于格的密码算法是数量最多的一类，其基于的主要数学问题是带错学习问题(LWE)及其变种、NTRU求逆问题等。

Compact-LWE算法由澳大利亚联邦科学与工业研究组织（CSIRO）的Liu，Li，Kim和Nepal所提交，其本质上是基于LWE的密码算法的推广。LWE问题由于其取自离散高斯分布的错误项比较小，易遭受来自格算法的攻击。因此，在构造Compact-LWE的时候，设计者试图将错误项增大，使得格攻击失效，从而仅需要较小的参数，就可以在保证算法效率的同时获得足够的安全性。然而，LWE问题中较小的错误为构造基于LWE的密码算法提供了非常便利的条件。如果将错误项增大，Compact-LWE势必需要引入特殊的结构来保证解密的正确性。而这些特殊的结构，恰恰成为了Compact-LWE的弱点所在。

虽然设计者认为Compact-LWE能完美抵抗格算法的攻击，但信息技术部潘彦斌等研究人员[1]发现，通过格基约化技术，可以在唯密文攻击模型下有效地恢复出其明文。实际上，Compact-LWE在加密过程中首先加密一个秘密向量l，然后将l和公钥u的内积d作为临时会话密钥对明文进行对称加密，而解密时，首先恢复该内积，然后利用其进行解密。设计者认为在唯密文攻击模型下，从密文恢复l是不可行的，因而不可能有效地从密文恢复明文。然而，解密真正需要的是l和u的内积，而不是l。从而，可以利用格基约化算法恢复出向量l'，虽然l'和l可能不同，但其和u做内积后得到的d与之前完全相同，因此，利用d就可以恢复出相应的明文。另外，他们同时考虑了对Compact-LWE的私钥恢复攻击。该攻击主要利用正交格、格基约化、交格等技术，充分利用公私钥之间的代数关系，一步步地恢复出等价私钥。针对Compact-LWE的参数选取，实验表明，他们的攻击总能成功。因此，Compact-LWE加密算法并不安全。

由于他们的攻击，Compact-LWE加密算法未能进入NIST后量子密码标准化的第二轮。

[1] Haoyu Li, Renzhang Liu, Yanbin Pan, Tianyuan Xie：Ciphertext-Only Attacks against Compact-LWE Submitted to NIST PQC Project， Cryptology ePrint Archive: Report 2018/020.