1、计算Hermite标准型的新型快速算法
任意一个整数矩阵都可以通过初等变换约化为Hermite标准型。Hermite标准型在计算数论、公钥密码学等领域有十分广泛的应用。
在2019年的符号与代数计算国际研讨会(ISSAC)上,我们提出了一种求解整数矩阵Hermite标准型的新算法。新算法通过求解带模线性方程组来计算Hermite标准型,可以更有效地控制中间变量的膨胀;对“随机”整矩阵而言,在合理假设下面,新算法的期望时间复杂度是同规模矩阵乘法复杂度的常数倍。
这项研究有助于在实践中加速已有的Hermite标准型求解算法,另外,对假设的研究,也为从理论上加速Hermite标准型求解算法的时间复杂性提供了可行的途径。
2、对NIST后量子密码标准候选算法的安全性分析
为应对量子计算机对当前公钥密码的严重威胁,美国国家标准与技术研究院(NIST)于2016年面向全球征集抗量子密码算法标准,随后,NIST公开征集对首轮候选算法的外部评估。关于NIST的首轮候选算法的安全性分析,我们主要有如下工作:
我们攻破了澳大利亚联邦科学与工业研究组织(CSIRO)提交的Compact-LWE格加密体制,可以由其公钥有效恢复出其私钥,以及从其密文直接恢复出明文。由于我们的攻击,Compact-LWE加密算法未能进入NIST后量子密码标准化的第二轮。
我们攻破了Hecht和Kamlofsky提出的基于八元数的HK17密钥交换算法。该攻击可以在多项式时间内完成,首次在现实中实现了对HK17所有参数下的成功攻击。因此,提交者主动撤回了HK17算法。
我们攻破了法国Aguilar Melchor,Aragon等设计的HQC体制的IND-CPA安全性,证明了HQC所基于的数学问题是易于求解的,同时提出了相应的修补方案。设计者修补该方案后,该方案进入第二轮。
相关论文:
1. Renzhang Liu, Yanbin Pan:Computing Hermite Normal Form Faster via Solving System of Linear Equations.In Proc. of ISSAC 2019, ACM, 2019.
2. Zhen Liu, Yanbin Pan, Tianyuan Xie: Breaking the Hardness Assumption and IND-CPA Security of HQC Submitted to NIST PQC Project (extended version). Accepted by IET Information Security, 2019.
3. Haoyu Li, Renzhang Liu, Qutaibah M. Malluhi,Yanbin Pan, Yongge Wang, Tianyuan Xie: Breaking HK17 in Practice.In Proc. of ISIT 2019, IEEE, 2019.
附件下载: