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

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

什麼是FALCON?

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

FALCON算法的工作原理

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

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

FALCON有哪些優(yōu)勢

與其他的抗量子簽名算法相比，F(xiàn)ALCON的特點是緊緻，靈活，驗簽速度快。

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

FALCON的參數(shù)

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

FALCON可以用在哪些場景

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

關於握奇

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