对密钥不匹配攻击的进一步理论分析--以NTRU-HRSS为例

目前,由美国国家标准技术研究院发起的对抗量子密码算法标准化的进程已进入最后一轮,其中基于格上困难问题的方案备受青睐.已有研究表明,若公私钥对被重复使用,则可以对选择明文攻击安全的格密钥封装机制发起密钥不匹配攻击;甚至在侧信道信息的辅助下,相关攻击能对选择密文攻击安全的格KEM奏效.在现有的针对格KEM方案的密钥不匹配攻击中,大多数攻击方案假设敌手一次只能恢复一个私钥系数,然而一次性恢复多个私钥系数是更为合理的假设,并且也将进一步减少密钥不匹配攻击所需的平均问询次数.鉴于此,本文进一步分析了密钥不匹配攻击中恢复私钥系数所需的平均问询次数的理论值下界的问题.其基本思路是将该问题转化为寻找一棵最优二叉恢复树的问题,进而证明了平均问询次数的理论值下界十分接近香农熵.在此基础上,本文提出了一套计算模型,并将其应用于NTRU-HRSSKEM方案,得到了更为准确的理论值下界;进一步地,据此提出了一种成对恢复NIST第三轮入选方案NTRU-HRSSKEM私钥的密钥不匹配攻击方案.实验结果表明,与现有的攻击方案相比,在成功率基本持平的基础上,平均问询次数减少了35.3%,耗时减少了47.3%.此外,本文提出的攻击方案也能够用于优化现有的针对CCA安全的NTRU-HRSSKEM方案的侧信道攻击,并将所需的问询次数由2447减少到1193.