科研進展
   新聞動態
      科研進展
      綜合新聞
      傳媒掃描
現在位置:首頁 > 新聞動態 > 科研進展
(潘彥斌)格算法及后量子密碼的安全性分析
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 Melchor,Aragon等設計的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. 

    

附件下載:
 
 
【打印本頁】【關閉本頁】
電子政務平臺   |   科技網郵箱   |   ARP系統   |   會議服務平臺   |   聯系我們   |   友情鏈接
网上兼职赚钱项目