本科生沈牧言在国际密码协会旗舰会议CHES上发表论文

近日，太阳新城官网程池老师团队与瑞典隆德大学郭骞老师合作的论文研究成果“Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber”被CHES接收，该论文第一作者为程老师指导的大四本科生沈牧言。CHES是由国际密码协会（IACR）主办的密码工程与物理安全方向的旗舰会议，会议上的论文展现了国际学术界和产业界在密码芯片、密码嵌入式系统领域的最高水平。

密码是信息安全的基石，目前美国已经开始向新一代抗量子密码的迁移进程。随着量子计算机技术的高速发展，目前广泛使用的基于大整数因子分解和离散对数问题构建的公钥密码学体制将不再安全。美国国家标准技术研究院（NIST）从2016 年开始征集抗量子密码算法标准，在NIST第三轮筛选中，共有4 个密钥封装方案和3 个数字签名方案候选。2022年7 月，NIST公布了最新的待标准化算法的筛选结果。Kyber在4个候选密钥封装方案（KEM）中成为了唯一被选中进行标准化的算法，这意味着在接下来的几年里，Kyber将广泛地被适配和应用在各种计算平台上。

该论文的研究对象是格公钥密码的侧信道安全性，以抗量子密码算法Kyber为例，对实际侧信道攻击中普遍存在噪声或干扰问题提出了一种处理方案。相比于传统的多数投票（Majority-Voting）等方法，该方法能减少约一半的问询次数。

密码算法的侧信道安全作为密码实例化安全中的一个重要领域，近年来受到学术界和工业界的高度关注。对抗量子KEM算法的侧信道攻击目标通常是服务器复用的私钥，相关攻击可归为两大类：第一大类中敌手借助攻击解密结果（Message）来逐步恢复出私钥，第二大类中敌手以算法的特定组件（如NTT）为攻击对象，效率更高但依赖特定的目标架构、以及代码编译方式等因素。

该论文基于的攻击模型是第一大类中的Plaintext-Checking Oracle-based Attack，也可称为Key Mismatch Attack。论文关注了侧信道分析在具体实践中的所面临的额外挑战：受环境噪音、测量方式等因素影响，获取到的信息比特可能翻转，进而导致恢复的密钥出现差错。传统的做法通常通过多数投票、或波形聚合等方法来确保密钥恢复的准确性。在论文中作者提出了一种新的解决方案，对基于格构建的KEM算法具有一定通用性，其基本思想是：粗粒度恢复-检错-纠错。与论文标题“Find the Bad Apples”对应，这一思路最大的挑战在于设计“检错”步骤。作者借助已恢复的私钥信息进行密文重构设计了一套特殊的“检错”密文，并运用了编码的相关理论在原有的攻击模型（即Oracle）下完成了一套检错方案。

由于密文选取需紧密与算法本身性质结合，并非每一种编码方式都存在对应的密文。下图是一种可行的验证系数块(0,2)的编码方式，作者将(0,2)编码到一个特殊码字“01”上，用这个独特的Oracle返回值序列区分出其他系数块值。为寻找出类似的密文来检测所有系数块的可能值，作者首先对符合条件的密文特征进行了理论分析，给出了相关引理并进行了证明。随后结合穷举搜索和分治法得到了所有密文，实现了通过两次问询检测四个系数的高效检错方法。

注意到对于噪声更强的环境，“检错”这一过程本身也可能出错，作者提出了一种Mix-voting方法来解决应对。进而，论文提出的密钥恢复方法在多种环境下都有较好的表现。

论文采用了模拟实验和板上实验相结合的方式进行评估与验证，并与多数投票消错（Ravi等人在CHES2020上使用）以及波形聚合消错（Ueno等人在CHES2022使用，为目前最好结果）两种方法进行了对比。实验结果表明，该论文中方法相比于后者可以减少45.9%, 55.4%的总问询次数。在此同时，类似于Ueno 等人的效果，该论文提出的方法可以成功恢复几乎全部的多项式系数，即在512个系数中平均只有0.04或0.05个发生错误。

论文PDF：https://tches.iacr.org/index.php/TCHES/article/view/9948

论文相关代码：https://github.com/7a17/Find-the-Bad-Apples/

通讯员：程池

审核：陈占龙

校对：石剑峰