ENGLISH    
 
  中国科学院    
 
 
     
 
首 页  
组织机构
科研成果
研究队伍
人才培养
信息公开
人才招聘
   科研进展
   新闻动态
      头条新闻
      综合新闻
      科研进展
现在位置:首页 > 新闻动态 > 科研进展
(高小山)布尔方程求解的量子算法与主流密码的抗量子攻击属性
2018-06-13 | 编辑:华罗庚数学中心

  布尔方程系统求解问题是算法设计中的核心问题。判定其是否有解是NPC问题,而求解布尔方程系统则是NP问题。该问题涉及到量子算法核心问题,即NPC问题的多项式时间量子算法是否存在?该问题也是密码学研究的核心问题:它是流密码、分组密码、Hash函数等主流密码体系主要分析方法,也是抗量子计算候选密码多变量公钥密码(MPKC)的数学基础。 

  本工作给出了布尔多项式系统求解的第一个量子算法,其复杂度关于方程大小和方程的条件数是多项式的,从而实现了对条件数小的稀疏布尔方程系统指数级加速。 

  这一算法揭示了主流密码的抗量子计算攻击属性。非对称密码的三类主流密码体系包括AESTriviumSHA3/Keccak. 其中AES是分组密码国际标准(2001),已经广泛使用;Trivium是流密码国际标准;SHA3/Keccak是新一代Hass函数国际标准。这些密码的破解都可以归结为非线性布尔方程的求解问题。应用本工作提出的布尔方程求解量子算法于以上主流密码的抗量子计算攻击分析,揭示了基于方程求解的密码体系的抗量子计算攻击属性:基于方程求解的密码体系只有在其条件数非常大时才可以抵抗量子计算攻击,进而揭示了对应方程的条件数是设计抗量子计算攻击密码的主要标准之一。 

  

 

  1.主流密码体系的抗量子计算攻击属性 

  

与本成果相关的论文: 

  1. Y.A. Chen and X.S. Gao, Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems, arXiv 1712.06239, 2017. 

附件下载:
 
 
【打印本页】【关闭本页】
 
研究院电子政务平台    中科院邮件系统    图书馆    会议服务平台
 
新闻动态 | 学术期刊 | 创新文化 | 党建文化 | 校友会 | 网站地图 | 联系我们
版权所有 © 中国科学院数学与系统科学研究院  京ICP备05002806号  京公网安备110402500020号
地址:北京市海淀区中关村东路55号  邮政编码:100190
电话:86-10-82541777  Fax:86-10-82541972  Email:contact@amss.ac.cn