2022-1-14
格密码体制的安全性分析（潘彦斌）
为应对量子计算机给当前公钥密码体制带来的巨大威胁，美国国家标准与技术研究院（NIST）于2016年面向全球征集抗量子密码算法标准。在所有候选算法中，格密码目前被广泛认为是最有希望被标准化的后量子密码。因此，对格密码的安全性分析具有十分重要的理论价值和现实意义。我们今年在此领域取得的主要成果如下：
1、首次提出利用分解域求解理想格上的最短向量问题
为了提高格密码的效率，基于理想格的密码算法被大量构造出来，其安全性基于理想格上最短向量问题的困难性。但学界目前对理想格上最短向量问题的困难性知之甚少，特别是，虽然理想格拥有丰富的代数结构，但尚不清楚如何利用这些代数结构来显著降低其最短向量问题的困难性。
鉴于素数和素理想在数论中基础研究地位，我们首次对素理想格中的最短向量问题进行深入研究，并利用素理想的分解域提出了新的求解算法，证明了对有理数域Galois扩域中的素理想格，素理想与分解域的交格中的近似短向量，一定是原素理想格中的近似短向量，而该交格可能具有更小的秩，因此在其中求解短向量比在原素理想格中求解要更容易。利用该思想，我们对在密码学中广泛使用的一类分圆域，严格证明了其上素理想格的精确最短向量可以通过求解其与某子域的交格中的最短向量问题来获得，并在合理分布下，一个随机素理想格上的最短向量问题能以不可忽略的概率在多项式时间内被求解。相关结果可以推广到该分圆域中的一般理想格上，从而进一步刻画了理想格上最短向量问题求解的困难性，首次揭示了其困难性的分层现象。
2、系统分析和改进了基于格的NIST后量子密码候选算法的密钥不匹配攻击
随着对NIST候选格密码的安全性评估不断深入，我们急需研究格密码算法在各类实用场景下的安全性。密钥不匹配攻击，指当格密码算法被用于建立共享密钥时，如果通讯的一方重用密钥，另一方试图借助可以判断双方共享密钥是否一致的谕言机来恢复该重用密钥。
对谕言机的查询次数是判断密钥不匹配攻击是否高效的一个重要指标。目前改进该攻击的主要目的就是降低查询次数。我们首次考虑了如下问题：攻击成功的必要查询次数是多少？通过将查询返回的比特串视为私钥候选值的编码，我们成功引入霍夫曼编码技术，并对基于格的NIST后量子密码候选算法，得到了恢复私钥所需要的平均谕言机查询次数的下界，从而揭示了目前已有攻击的可改进空间。同时，利用该思想，我们通过精心构造密文，使得谕言机所返回的字符串可以尽可能地接近预先设定的霍夫曼编码的码字，从而大大改进了已有的攻击，得到了目前最优的更接近理论下界的谕言机查询次数。
1、首次提出利用分解域求解理想格上的最短向量问题
意义：我们的算法首次提出利用素理想的分解域来研究理想格上的最短向量问题，为理想格上最短向量问题的求解提供了新工具和新方法，同时揭示了密码学中理想格上短向量求解的弱实例，相关结果将有助于我们进一步理解理想格上最短向量问题的困难性，以及相关密码算法的安全性。
评价：相关论文发表于密码学顶级会议之一的欧密会上。审稿人认为：“The paper is clearly worth publication, as it is a potential tool to be used for more complicated though more general attacks on structured lattices”；“The present work is well executed and interesting”；“This is definitely an interesting read，and the research question is clearly an active one”.
目前论文被他引2次（Google Scholar），英国帝国理工学院的科研人员Porter, Mendelsohn, Ling在引用我们的论文时写到：“Recently, Pan, Xu, Wadleigh and Cheng pioneered a remarkable technique to approach the problem of SVP in prime and general ideal lattices”。
2、系统分析和改进了基于格的NIST后量子密码候选算法的密钥不匹配攻击
意义：我们得到了对格密码密钥不匹配攻击的谕言机查询次数下界，从理论上揭示了此类攻击可被改进的空间，并得到了目前最优的攻击。相关攻击可以被应用于密钥重用情形，以及对格密码实现的侧信道攻击，从而揭示了在设计和实现格密码算法时预防此类攻击的必要性。
评价：相关论文发表于密码学顶级会议之一的亚密会上。审稿人认为：“The novel contributions here are the general approach…I see value in having a more general approach”；“This paper contains an interesting idea of using the Huffman code”；“the idea is novel and elegant”。
目前论文被引用3次，其中他引1次（Google Scholar）。
1. Yanbin Pan, Jun Xu, Nick Wadleigh, Qi Cheng: On the Ideal Shortest Vector Problem over Random Rational Primes. In Proc. of Eurocrypt 2021, Part I, LNCS 12696, 559–583, 2021.
2.Yue Qin, Chi Cheng, Xiaohan Zhang, Yanbin Pan, Lei Hu, Jintai Ding: A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs. In Proc. of ASIACRYPT 2021, LNCS 13093, pp. 92–121, 2021.
