後量子密碼算法之FALCON算法解讀

1994年，Peter Shor設計了一個算法，在量子計算機上運行該算法可以在多項式時間內解決大整數因子分解問題和離散對數問題。這對諸如RSA和ECC等基於這兩類困難問題的經典公鑰密碼系統來說是一個巨大的威脅。所幸當時量子計算機尚未問世；然而，隨着量子技術的發展，這個威脅正日益逼近。為了應對量子威脅，在2016年，NIST發起了後量子密碼（PQC）標準的提案徵集。FALCON是提交到NIST PQC徵集的一個簽名算法。2022年，NIST宣布了四個候選提案入選標準化方案，其中之一就是FALCON。NIST稱，FALCON入選的原因是Dilithium（PQC簽名方案，已被NIST標準化）的簽名比較長，在需要較短簽名的場合FALCON可以派上用場。NIST稱，FALCON標準草案將在2024年底發布，最終草案版本將在2025年發布。

什麼是FALCON?

FLACON代表“基於NTRU格和快速傅里葉的緊緻簽名”。它是一種可以抵抗量子攻擊的數字簽名算法。它可以用來檢測數據所受到的非授權修改，驗證簽名者的身份。FALCON生成的簽名可作為證據，證明簽名確由聲稱的簽名者簽署。這種特性被稱為“抗抵賴性”，即簽名者無法事後否認簽名行為。

FALCON算法的工作原理

FALCON是由Gentry、PeiKert和Vaikuntanathan（GPV）描述的理論框架的一個實例化，這個理論框架描述了一種構造基於格的hash-and-sign範式的簽名方案。這個框架需要有兩個元素：一類格密碼和一個陷門採樣器。FALCON選擇了NTRU格和快速傅里葉採樣。簡言之，FALCON簽名方案可以描述如下：

FALCON = GPV框架 + NTRU格 + 快速傅里葉採樣

FALCON有哪些優勢

與其他的抗量子簽名算法相比，FALCON的特點是緊緻，靈活，驗簽速度快。

首先，FALCON的主要設計原則是緊緻，使得公鑰長度和簽名長度之和達到最小。在安全級別“I級”中，FALCON的公鑰長度是897字節，比Dilithium的公鑰長度短415字節。而在簽名長度方面，FALCON算法的簽名長度為666字節，比Dilithium算法的簽名長度短1754字節。其次, FALCON算法很靈活。一方面，它可以轉換為IBE（Identity-Based Encryption）方案，這個方案在性能上比基於雙線性對的IBE方案要快幾個數量級。另一方面，FALCON也可轉換為環簽名方案。另外，FALCON在驗簽方面的性能比Dilithium表現得更優秀。

FALCON的參數

FALCON指定了兩個參數集，分別對應於NIST規定的安全級別I和安全級別V。具體參數見下表：

FALCON可以用在哪些場景

FALCON已經被集成到很多軟件密碼庫中，比如OQS（Open Quantum Safe）。OQS是一個以支持密碼算法抗量子化為目標的工程，已經被集成到廣泛使用的OpenSSL庫。得益於FALCON算法的靈活性，它可以用在下列等場景：

關於握奇

巧合的是，當Peter shor提出shor算法的同年，1994年，握奇公司成立，開始基於公開密鑰密碼體系開發信息安全解決方案。憑藉在密碼算法、數字安全和安全芯片操作系統領域的深厚積累，握奇的產品方案為全球數十億用戶提供身份認證和交易安全的保障。我們緊跟後量子密碼算法的發展，積極布局，密切關註標准研究發展趨勢，確保未來的產品設計能夠應對量子計算時代的安全挑戰，為客戶提供前沿的抗量子算法支持，以構建強大的數字安全防護體系。