G.O.S.S.I.P 阅读推荐 2024-01-15 大破量子危机

下面首先插播两条新闻：

近期，有市场传言称由于预算及盈利等原因，阿里达摩院对旗下量子实验室进行了大幅裁员，并可能裁撤整个团队。对于相关传言，阿里达摩院于2023年11月26日回应表示，为了进一步推动量子科技协同发展，达摩院联合浙江大学发展量子科技，将量子实验室及可移交的量子实验仪器设备捐赠予浙江大学，并向其他高校和科研机构进行开放。
2024年1月，百度量子计算研究所传出变动消息。官方已证实，旗下量子实验室及可移交的量子实验仪器设备将捐赠予北京量子信息科学研究院。

尽管量子计算对传统密码算法构成了潜在的重要威胁，但是密码学研究社区很早就着手构建抗量子计算安全（即后量子安全）的密码算法，足以对抗（可能研发成功的）量子计算机的威胁，这也导致量子研究还没开始就走向终点的可能原因之一拥有量子黑科技的外星人无法再监听我们地球人。今天我们就要来看看密码学界的007们大破量子危机的又一进展。

如果大家对相关背景知识比较陌生，可以看看去年我们介绍过的关于后量子密码算法竞赛的文章（G.O.S.S.I.P 阅读推荐 2023-07-19 NIST开启新一轮后量子数字签名竞赛），NIST其实当时就已经批准了四个算法（包含一个公钥加密Kyber和三个数字签名Dilithium, Falcon, SPHINCS+）。我们也在当时强调，NIST期望在这一轮的征集中寻找不基于结构格的数字签名算法，这样即使基于结构格的数字签名方案被削弱甚至攻破的情况下，仍然有成熟高效的备选方案。今天我们要介绍的两篇论文就是对相关需求的回应：第一篇PKC 2024介绍了一种基于编码问题的数字签名方案ReSolveD，第二篇美国密码年会CRYPTO 2023论文介绍了一种基于哈希的数字签名方案SPHINCS-ɑ

基于编码问题的数字签名方案——ReSolveD

在这篇已被国际密码学会在公钥密码领域的顶级会议PKC 2024（International Conference on Practice and Theory in Public Key Cryptography）录用的论文ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head中（论文的第一作者是上海交通大学郁昱教授团队的博士生崔泓睿），作者设计了一个基于规则噪声校验子译码问题（regular syndrome decoding）以及不经意线性函数运算模拟（VOLE-in-the-head）的后量子签名算法ReSolveD，是一个基于编码的（code-based）的数字签名算法。去年我们曾经提到，在NIST此前的算法竞赛中，仅有两个基于编码的签名算法，并且都没有活过第一轮海选，而现在形势已经大不同了：今天介绍的ReSolveD算法，选取了合适的编码问题，结合最新的零知识证明技术，获得了PKC 2024审稿人的一致认可。

ReSolveD的安全性基于编码问题中的随机线性码在规则噪声（regular noise）下的校验子译码问题（SD）的困难性，可看作是著名的校验子译码问题（SD）的一个成熟变体。签名方案通过在最新的 VOLE-in-the-head 框架中设计一种新的零知识证明协议获得，该协议使用随机线性组合的方式证明一个向量的汉明重量恰好为1，通过多次重复技术证明规则噪声的结构正确。

如表1所示，在标准台式机的单个核上验证了128位安全强度的签名大小为3.99 KB，签名时间为27.3毫秒，验证时间为23.1毫秒。与最先进的基于编码的签名方案相比，论文的签名方案在常见的“签名大小+公钥大小”度量方面实现了1.5~2倍的改进，同时保持了同等级别的计算效率。

表1：论文提出的数字签名与基于编码的数字签名算法在128比特安全等级下的性能对比

表2：论文提出的数字签名与NIST后量子数字签名投稿作品FAEST（基于对称密码）、SDitH（基于编码问题）的性能对比

基于哈希的签名方案——SPHINCS-ɑ

今天介绍的第二篇论文Revisiting the Constant-sum Winternitz One-time Signature with Applications to SPHINCS+ and XMSS 发表于国际密码学会旗舰会议——美国密码年会CRYPTO 2023（International Cryptology Conference）上，论文的第一和第二作者分别是上海交通大学郁昱教授指导的博士生张凯羿和崔泓睿。论文提出了一个基于哈希函数（hash function）的数字签名算法——SPHINCS-ɑ，这个算法也入围了正在进行的NIST后量子数字签名标准征集。那么，这个算法又有什么先进之处呢？

我们首先要介绍一下研究背景。Leslie Lamport（2013年图灵奖得主）于1979年首次提出基于单向函数的一次签名（即一个密钥只能签名一条消息），在此基础上，利用通用单向哈希函数（Universal One-Way Hash Function）可构造出标准意义的数字签名算法（当然也可以基于单向函数构造）。然而，这一思想主要给出了基于对称密码构造数字签名的可行性，其实际效率较为低下。之后的一系列工作对基于对称/哈希的签名进行了改进和优化，目前的集大成者SPHINCS+算法已被NIST列为后量子标准算法。

从名字上看，SPHINCS-ɑ算法和SPHINCS+算法很像，实际上SPHINCS-ɑ算法的设计首先使用组合数学中的序理论（order theory）证明了一个重要的结论——当使用常和（constant-sum）编码方案时（Bos和Chaum，Crypto 1992），WOTS+一次性签名不仅在所有高效（多项式时间）编码下，而且是在所有存在的编码下是尺寸最优的。此外，他们也在一定程度上论证了Winternitz OTS的链式结构是所有基于树的OTS设计中的最优结构（如下图）。那我们的读者可能有点摸不着头脑，WOTS+一次性签名是什么？实际上它是当前的基于哈希签名（如SPHINCS+算法）会重复调用的基础组件，这一算法的性能在很大程度上影响SPHINCS+算法的整体性能。作为结论的一个补充，作者还顺带指出了在ASIACRYPT 1996上被证明尺寸最优的基于DAG的OTS设计中的一个安全缺陷。

图1：论证“链状一次签名是所有树结构一次签名中的最优结构”的转化推理过程

对算法的性能评估表明，SPHINCS-ɑ在签名时间和签名尺寸方面都比SPHINCS+算法有一定程度的提升。

表3: SPHINCS+算法与SPHINCS-ɑ算法的性能对比

当然也要指出的是，由于SPHINCS+算法的验签时间比签名生成的时间低一个数量级，因此SPHINCS-ɑ算法目前并没有将更小的验签时间作为优化方向。在部分参数选择下，SPHINCS-ɑ的验签时间上相比SPHINCS+有所减慢。

---

论文 1. Hongrui Cui, Hanlin Liu, Di Yan, Kang Yang, Yu Yu, Kaiyi Zhang(2024). ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head. Public-Key Cryptography – PKC 2024. (available at https://ia.cr/2024/040)
论文 2. Kaiyi Zhang, Hongrui Cui, Yu Yu (2023). Revisiting the Constant-Sum Winternitz One-Time Signature with Applications to SPHNICS+ and XMSS. Advances in Cryptology – CRYPTO 2023. (available at https://ia.cr/2023/850)

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2024-01-15 大破量子危机