量子計算領域的最新進展，使得很多人對古典密碼學的前景感到擔憂，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是一種多變量簽名方案，它的分層結構以不平衡石油-醋栗（UOV）簽名方案為基礎。 Rainbow層所施加的額外結構使該方案面臨更多的密碼分析技術，但提高了該方案的效率。 Rainbow提供了快速的簽名和驗證以及非常短的簽名，但具有非常大的公鑰。
Rainbow是一種多變量簽名方案，它的分層結構以不平衡石油-醋栗（UOV）簽名方案為基礎。 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
