G.O.S.S.I.P 阅读推荐 2023-07-19 NIST开启新一轮后量子数字签名竞赛

美国国家标准与技术研究院（NIST）于近日公布了新一轮后量子数字签名竞赛的名单。在此之前，NIST已经开展了数年后量子密码标准化工作，并已经批准了四个算法（包含一个公钥加密Kyber和三个数字签名Dilithium, Falcon, SPHINCS+），其中三个是基于带结构的格，一个是基于哈希。NIST期望在这一轮的征集中寻找不基于结构格的数字签名，如果基于结构格，其性能应当比此前批准的算法有显著提升。

下图列出了通过NIST形式审核的所有的40个提交（图片原作者为Daniel Apon，有修改）。其被分为了基于编码的(Code-based),基于同源的(Isogeny-based),基于格的(Lattice-based),基于MPC-in-the-head的(MPCitH)，基于多变量的(Multivariate)，基于对称的(Symmetric-based)和其他(Other)

在短短的数十小时内，已经有几个方案被攻击

接下来依照分类简单介绍一下

基于编码的算法 (Code-based)

在上一次征集中，仅有两个基于编码的签名算法，并且它们都没有进入第二轮。这说明上次征集时基于编码的签名尚不成熟。经过数年发展，此次有5个算法投稿。其中LESS和Wave较为有名，Enhanced pqsigRM是参与过上一次征集pqsigRM的改进。近期提出的FuLeeca声称它的性能超越Falcon。笔者不熟悉MEDS。

基于同源的算法 (Isogeny-based)

基于同源的数字签名有着非常小的公钥和签名大小，但是入选NIST公钥第四轮，基于同源的公钥算法SIKE被完全攻破，似乎使得研究人员对其丧失了信心。本次仅有SQIsign一个算法。

基于格的算法 (Lattice-based)

格密码可以说是最火热的后量子密码技术路线。在本次提交中，EagleSign, HAETAE, Raccoon 依然是带结构的格，HuFu和SQUIRRELS是无结构的格。HAWK另辟蹊径，其基于格同构问题而非LWE及其变种。EHT算法笔者不熟悉。

基于MPC-in-the-head的算法 (MPCitH)

在上一轮竞赛中，MPC-in-the-head技术路线还被分类为Symmetric-based，且仅有Picnic一个算法，此次它已经得到了一个单独的分类。MPC-in-the-head是一种零知识证明，可以将零知识证明和单向函数组合在一起构造签名。基于单向函数可以将其继续分类如下，CROSS, RYDE, SDitH是Syndrome Decoding及其变种，MIRA和MiRitH基于MinRank。MQOM基于多变量，PERK基于PKP问题。

基于多变量的算法 (Multivariate)

多变量是本次提交种类最多的，上次竞赛中的Rainbow和GeMSS都进入了第三轮但也被攻击。但和同源不同，许多研究人员似乎对多变量仍有信心。笔者不熟悉多变量因此不再赘述。

基于对称的算法 (Symmetric-based)

基于对称的签名是指全部使用对称加密和哈希函数构造签名，因此这一类被认为是最可靠的。其中AIMer和FASET仍然是一种MPC-in-the-head技术路线，只是AIMer的单向函数是AIM而FASET的单向函数是AES。而Ascon-Sign和SPHINCS-alpha是已批准的SPHINCS+的变种。前者替换哈希函数为近期NIST批准的轻量级密码Ascon，后者对SPHINCS+的编码做出了一定改进。