我院程池老师团队参加2021年亚密会并作学术报告

（通讯员：章丽平）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等人由于参数选择的原因，始终无法给出完整恢复。