2021年12月6日至10日，程池老師與研究生張曉涵在線參加了亞洲密碼學(xué)2021年年會，并作學(xué)術(shù)報告，題目為 “對NIST格密鑰封裝候選方案密鑰不匹配攻擊的系統(tǒng)性研究與分析（A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs）”。該項工作為程池老師團隊與中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院、中科院信工所、清華大學(xué)、北京雁棲湖應(yīng)用數(shù)學(xué)研究院的合作成果，通信作者為程池老師。亞洲密碼學(xué)年會為國際密碼學(xué)三大頂級會議之一，在密碼學(xué)界享有很高的聲譽。

程論文研究的對象是格公鑰密碼的實用安全性，論文提出了一種針對所有基于格的NIST候選KEM方案的統(tǒng)一評估方法，可用于尋找密鑰不匹配攻擊的下界（平均所需最少問詢次數(shù)）。該方法也能幫助找到更合適的參數(shù)來提高實際密鑰不匹配攻擊的效果。特別地，能極大地減少針對CCA安全的格KEM方案的側(cè)信道攻擊所需的問詢次數(shù)。

該論文的研究背景是NIST正在進行的抗量子密碼標(biāo)準(zhǔn)評選。由于量子計算機的快速發(fā)展，傳統(tǒng)基于數(shù)論的公鑰密碼算法的安全性受到嚴(yán)重威脅，因此從目前使用的公鑰算法到抗量子公鑰算法的過渡變得迫在眉睫。自2016年2月以來，NIST在全球范圍內(nèi)征集抗量子公鑰算法，計劃在2022-2023年間發(fā)布抗量子公鑰密碼算法標(biāo)準(zhǔn)?？沽孔用艽a標(biāo)準(zhǔn)化的目標(biāo)是建立能同時抵御量子計算機和經(jīng)典計算機的加密系統(tǒng)，并較好地集成到現(xiàn)有的網(wǎng)絡(luò)和通信系統(tǒng)中。在NIST候選方案中，基于格的方案一馬當(dāng)先，在進入NIST第三輪的四個KEM候選方案中，有三個為基于格的方案。

近年來，研究者發(fā)現(xiàn)密鑰重用攻擊不僅對CPA安全的格密鑰交換方案有效，而且在側(cè)信道攻擊中，還可以用來攻擊CCA安全的密碼方案。目前的攻擊方案大都只針對單獨的某個方案，因此存在一個基本問題，即能否找到一種統(tǒng)一的方法來評估針對所有NIST候選方案發(fā)起密鑰不匹配攻擊所需的問詢（即密鑰匹配和不匹配）次數(shù)？在2019年歐密會上，B?etu等人試圖回答該問題，但他們的大多數(shù)結(jié)果僅與部分未進入第二輪的候選方案有關(guān)，并未實現(xiàn)對所有候選方案的統(tǒng)一評估。該論文的基本思想是將尋找問詢次數(shù)下界的問題轉(zhuǎn)化為尋找一棵最優(yōu)二叉恢復(fù)樹（BRT）；通過利用哈夫曼編碼技術(shù)，可以成功構(gòu)建一棵最優(yōu)BRT，并得到其平均問詢次數(shù)的下界。

圖1：通過哈夫曼編碼技術(shù)構(gòu)建最優(yōu)BRT

值得一提的是，通過使用程論文的方法選取的參數(shù)可有效改進針對格KEM方案的側(cè)信道攻擊。作為對比，Ravi等人在CHES 2020中完整恢復(fù)第二輪KYBER512方案私鑰所需的問詢次數(shù)為2560，而使用程論文中的參數(shù)和攻擊方法所需的理論平均問詢次數(shù)為1312，而且成功率為100%，而Ravi等人由于參數(shù)選擇的原因，始終無法給出完整恢復(fù)。