科研进展
(潘彦斌)格算法及后量子密码的安全性分析
发布时间:2020-01-09 |来源:

   1、计算Hermite标准型的新型快速算法

  任意一个整数矩阵都可以通过初等变换约化为Hermite标准型。Hermite标准型在计算数论、公钥密码学等领域有十分广泛的应用。 

  2019年的符号与代数计算国际研讨会(ISSAC)上,我们提出了一种求解整数矩阵Hermite标准型的新算法。新算法通过求解带模线性方程组来计算Hermite标准型,可以更有效地控制中间变量的膨胀;对随机整矩阵而言,在合理假设下面,新算法的期望时间复杂度是同规模矩阵乘法复杂度的常数倍。 

  这项研究有助于在实践中加速已有的Hermite标准型求解算法,另外,对假设的研究,也为从理论上加速Hermite标准型求解算法的时间复杂性提供了可行的途径。 

  2、对NIST后量子密码标准候选算法的安全性分析 

  为应对量子计算机对当前公钥密码的严重威胁,美国国家标准与技术研究院(NIST)于2016年面向全球征集抗量子密码算法标准,随后,NIST公开征集对首轮候选算法的外部评估。关于NIST的首轮候选算法的安全性分析,我们主要有如下工作: 

  我们攻破了澳大利亚联邦科学与工业研究组织(CSIRO)提交的Compact-LWE格加密体制,可以由其公钥有效恢复出其私钥,以及从其密文直接恢复出明文。由于我们的攻击,Compact-LWE加密算法未能进入NIST后量子密码标准化的第二轮。 

  我们攻破了HechtKamlofsky提出的基于八元数的HK17密钥交换算法。该攻击可以在多项式时间内完成,首次在现实中实现了对HK17所有参数下的成功攻击。因此,提交者主动撤回了HK17算法。 

  我们攻破了法国Aguilar MelchorAragon等设计的HQC体制的IND-CPA安全性,证明了HQC所基于的数学问题是易于求解的,同时提出了相应的修补方案。设计者修补该方案后,该方案进入第二轮。 

    

  相关论文: 

  1.   Renzhang Liu, Yanbin PanComputing 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. 

    


附件下载:

    联系我们
    参考
    相关文章