量子计算领域的最新进展，使得很多人对古典密码学的前景感到担忧，12月4日中国科学家成功验证的光量子计算机——九章，已经构建了76个光子（量子比特）的量子计算原型机，这距离破解古典密码学需要达到的数千可用量子位级别，似乎不再是那么遥不可及。（以速度来看，求解数学算法高斯玻色取样的速度只需200秒，而目前的超级计算机要用6亿年。通常认为，50个量子比特是证明量子计算机有望超越传统计算机的关键门槛）。
如果量子计算在未来取得突破性进展，根据一些人的估算，到2031年，RSA和ECC（椭圆加密）算法被破解的概率大约为50%，而比特币、以太坊等区块链正是运用了古典密码学，虽然比特币使用了双SHA256算法，使其较银行、支付宝等使用的保密系统多了一道防线，但它依然存在着多种攻击向量，似乎量子计算正在成为区块链的达摩克利斯之剑，世界从此会变成怎样？量子计算机将会得到区块链的秘密吗？事实上，即便有了量子计算机，许多经典的保密算法仍将是有效的，更何况量子保密技术也在蓬勃发展。区块链行业的一些研究者，也在不断研究相关的抗量子加密算法，早在2017年，NIST就开始了后量子密码学标准化进程，希望在2022年之前准备好抗量子破解的密码学（quantum-resistant cryptography），当时共有69种候选算法同时满足最低验收标准和提交要求。因其评价标准和选择过程十分严格，直到2020年7月22日，才公布第三轮入围名单和候补候选人，大家一直最看好的数字签名，由瑞士ABCMint数学算法基金会推动的抗量子签名方案，后量子加密基金会支持的抗量子算法之一，最短签名长度的签名抗量子签名方案——彩虹签名Rainbow，毫无疑问的进入NIST第三轮数字签名名单中。
美国国家标准与技术研究院（National Institute of Standards and Technology，NIST在国际上享有很高的声誉。NIST有四位研究者因其物理学上的成就获得了诺贝尔奖：威廉·丹尼尔·菲利普斯（1997年），埃里克·康奈尔（2001年），约翰·霍尔（2005年）和戴维·瓦恩兰（2012年），是美国政府实验室里获奖者最多的。其中Rainbow是最小签名长度的签名，Falcon和Dilithium签名长度很长很长；正选的三个Dilithium可能被破解的概率最大，Falcon是NTRU架构，NTRU有点像漏锅，被破解好些次，都能补好，但总出问题，Falcon是被最多人在研究围攻想破解的。Rainbow的最大优势是历史最长，几乎公认没办法破解，以及签名最短。Rainbow是NP-Hard问题，很难找到漏洞。所以，Rainbow应该是未来很长时间的唯一数字货币可以采用的抗量子签名。
以下是Rainbow、CRYSTALS-DILITHIUM、FALCON介绍，因为Rainbow在各项对比中最为突出，将在下面重点介绍一下Rainbow。Rainbow是一种多变量签名方案，它的分层结构以不平衡石油-醋栗（UOV）签名方案为基础。Rainbow层所施加的额外结构使该方案面临更多的密码分析技术，但提高了该方案的效率。Rainbow提供了快速的签名和验证以及非常短的签名，但具有非常大的公钥。选择Rainbow增加了入围签名方案的多样性；但是，由于密钥尺寸非常大，Rainbow不适合作为通用签名算法来替代目前出现在FIPS 186-4中的算法。特别是，大公钥使得证书链非常大。然而，有些应用并不需要经常发送密钥。对于这样的应用，Rainbow提供了小而快的签名。唯一具有类似性能特征的其他先进候选签名，GeMSS，具有大得多的密钥，似乎很难在非常低端的设备上实现。由于这些原因，Rainbow被选为决赛选手。NIST研究人员注意到，与Rainbow方案相关的一些攻击途径的性能和理论复杂性之间存在差距。在第二轮比赛中，已经发表了对这些著名攻击的一些更紧密的理论分析（以及新的算法）。特别是为了达到宣称的安全水平，对所有参数集进行参数调整是必要的。不过，如果采用更保守的参数选择，应该可以用最小的性能成本达到宣称的安全水平。在Rainbow准备好进行标准化之前，必须调整其参数，以确保其达到宣称的安全目标。此外，NIST更倾向于采用免版税许可的算法，以鼓励广泛采用。
# CRYSTALS-DILITHIUM #
DILITHIUM的安全性依赖于MLWE和模块短整数解问题（MSIS）的硬度，并遵循Fiat-Shamir与中止技术。DILITHIUM通过均匀分布对所有参数集和样本使用相同的模数和环，这使得它的实现比主要竞争对手FALCON更简单。总的来说，DILITHIUM在密钥和签名大小上，以及在密钥生成、签名和验证算法的效率上，都有很强的、均衡的性能。DILITHIUM在实际实验中表现良好。第二轮，DILITHIUM增加了非确定性生成签名的选项，并增加了基于使用AES而非SHAKE的实现，以说明硬件指令的未来优势。此外，还发表了关于QROM中安全性的新研究，适用于DILITHIUM。NIST鼓励DILITHIUM团队增加一个5类参数集。在理解具体的安全性方面还需要更多的研究，因为DILITHIUM的CoreSVP安全强度参数集是所有仍在进行中的网格方案中最低的。NIST选择DILITHIUM作为最终入围者，并预计DILITHIUM或FALCON将在第三轮结束时被标准化为主要的后量子签名方案。# FALCON #
FALCON是一种基于网格的签名方案，利用 散列和签名 范式。安全性是基于NTRU网格上的SIS（短整数解）问题的难度，在随机奥数模型（ROM）和QROM中都给出了安全证明，并进行了严格的还原。FALCON的实现比DILITHIUM更复杂，需要树状数据结构、大量的浮点运算以及从几个离散高斯分布中随机采样。FALCON的优点之一是它提供了所有第二轮数字签名方案中最小的带宽（公钥大小和签名大小）。FALCON在签名和验证方面也很高效，尽管密钥生成较慢。FALCON可以很容易地投入到现有的协议和应用中，并提供非常好的整体性能。在第二轮开始时，FALCON删除了他们的第3类参数集，这简化了他们的规范和实现，因为他们使用了不同的模数和环选择。第二轮期间的另一个主要更新是在NIST第二届PQC标准化会议后不久发布的恒定时间实现。在第三轮中，NIST鼓励对FALCON的实现进行更多的审查，以确定使用浮点运算是否比其他方案更容易出现实现错误，或者为侧通道攻击提供了途径。此外，如果能提供采样器的测试向量，也许可以让它对随机种子进行确定性测试，这样就可以使用已知答案测试（KATs）来验证实现。与其他几个候选者一样，FALCON的第1类参数的CoreSVP安全强度相对较低，因此还需要进一步研究。
附录：彩虹签名第三轮入围原文链接：https://groups.google.com/a/list.nist.gov/forum/m/#!topic/pqc-forum/0ieuPB-b8eg
Group
