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

什么是FALCON?

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

FALCON算法的工作原理

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

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

FALCON有哪些優(yōu)勢(shì)

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

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

FALCON的參數(shù)

FALCON指定了兩個(gè)參數(shù)集，分別對(duì)應(yīng)于NIST規(guī)定的安全級(jí)別I和安全級(jí)別V。具體參數(shù)見(jiàn)下表：

FALCON可以用在哪些場(chǎng)景

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

關(guān)于握奇

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