948
0
0
2022-10-12 09:39:02
2022-10-12
2021年12月6日至10日，程池老師與研究生張曉涵在線參加了亞洲密碼學2021年年會，并作學術報告，題目為 “對NIST格密鑰封裝候選方案密鑰不匹配攻擊的系統性研究與分析（A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs）”。該項工作為程池老師團隊與中國科學院數學與系統科學研究院、中科院信工所、清華大學、北京雁棲湖應用數學研究院的合作成果，通信作者為程池老師。亞洲密碼學年會為國際密碼學三大頂級會議之一，在密碼學界享有很高的聲譽。
程論文研究的對象是格公鑰密碼的實用安全性，論文提出了一種針對所有基于格的NIST候選KEM方案的統一評估方法，可用于尋找密鑰不匹配攻擊的下界（平均所需最少問詢次數）。該方法也能幫助找到更合適的參數來提高實際密鑰不匹配攻擊的效果。特別地，能極大地減少針對CCA安全的格KEM方案的側信道攻擊所需的問詢次數。
該論文的研究背景是NIST正在進行的抗量子密碼標準評選。由于量子計算機的快速發展，傳統基于數論的公鑰密碼算法的安全性受到嚴重威脅，因此從目前使用的公鑰算法到抗量子公鑰算法的過渡變得迫在眉睫。自2016年2月以來，NIST在全球范圍內征集抗量子公鑰算法，計劃在2022-2023年間發布抗量子公鑰密碼算法標準。抗量子密碼標準化的目標是建立能同時抵御量子計算機和經典計算機的加密系統，并較好地集成到現有的網絡和通信系統中。在NIST候選方案中，基于格的方案一馬當先，在進入NIST第三輪的四個KEM候選方案中，有三個為基于格的方案。
近年來，研究者發現密鑰重用攻擊不僅對CPA安全的格密鑰交換方案有效，而且在側信道攻擊中，還可以用來攻擊CCA安全的密碼方案。目前的攻擊方案大都只針對單獨的某個方案，因此存在一個基本問題，即能否找到一種統一的方法來評估針對所有NIST候選方案發起密鑰不匹配攻擊所需的問詢（即密鑰匹配和不匹配）次數？在2019年歐密會上，B?etu等人試圖回答該問題，但他們的大多數結果僅與部分未進入第二輪的候選方案有關，并未實現對所有候選方案的統一評估。該論文的基本思想是將尋找問詢次數下界的問題轉化為尋找一棵最優二叉恢復樹（BRT）；通過利用哈夫曼編碼技術，可以成功構建一棵最優BRT，并得到其平均問詢次數的下界。
圖1：通過哈夫曼編碼技術構建最優BRT
值得一提的是，通過使用程論文的方法選取的參數可有效改進針對格KEM方案的側信道攻擊。作為對比，Ravi等人在CHES 2020中完整恢復第二輪KYBER512方案私鑰所需的問詢次數為2560，而使用程論文中的參數和攻擊方法所需的理論平均問詢次數為1312，而且成功率為100%，而Ravi等人由于參數選擇的原因，始終無法給出完整恢復。
