Falcon簽名

Falcon簽名是由美國國家標準與技術研究院（NIST）標準化的一種後量子數字簽名方案，其安全性基於格理論中的計算難題。該方案具有公鑰和簽名長度較短的特點，其簽名長度約為1,296位元組。

該簽名方案在量子安全區塊鏈中用於替代傳統ECDSA，構建抗量子攻擊的交易驗證層。同時，其輕量化最佳化版本也被套用於物聯網設備的身份認證方法中。在算法實現層面，研究者通過改進快速傅立葉採樣等方法，致力於降低其線上簽名階段的時間複雜度或記憶體占用。

技術原理與算法設計

Falcon簽名是美國國家標準與技術研究院（NIST）標準化的後量子數字簽名方案之一，其安全性基於格理論中的NTRU格難題。其核心算法是快速傅立葉採樣算法，該算法是Babai最近平面算法的一個變體。在離線階段，算法需要建立Falcon樹，其存儲複雜度為O(n log n)；線上簽名階段通過遞歸調用輸出短向量，時間複雜度為O(n log n)。通過將Falcon樹預處理為採樣矩陣等最佳化手段，可將線上階段的時間複雜度降至O(n)。

在密鑰生成階段，節點生成Falcon密鑰對：私鑰為通過高斯採樣生成的短向量，通常存儲於硬體安全模組（HSM）中；公鑰為格的基矩陣。簽名生成時，通過哈希函式將交易數據映射至格空間，利用私鑰和快速傅立葉採樣算法生成緊湊的簽名，簽名長度約為1，296位元組，滿足NIST安全級別3。簽名驗證時，驗證節點使用公鑰驗證簽名在格空間中的合法性。

作為基於NTRU格的簽名方案，Falcon具有公鑰和簽名長度較短的優勢，但算法設計複雜，實現難度較高。在資源受限環境中，可通過私鑰稀疏化壓縮、將快速傅立葉變換（FFT）從遞歸計算改為疊代式、利用處理器SIMD指令並行加速計算、採用定點數最佳化高斯採樣等方法，顯著降低其記憶體占用和計算延遲。經過最佳化，在特定微控制器上運行Falcon簽名算法所需的動態記憶體可降低至參考實現的37%，簽名生成時間可達334.7毫秒，驗證時間可達6.16毫秒。

技術特點與優勢

Falcon簽名基於格理論難題，可抵禦Shor算法等量子計算攻擊，達到NIST安全級別3(抗攻擊強度≥2^128)。作為後量子簽名方案，Falcon可替代傳統ECDSA等方案。

Falcon的簽名長度和公鑰長度都較短，有利於降低通信與存儲開銷。簽名生成與驗證速度較快，通過算法最佳化可滿足高吞吐量場景。

Falcon的算法設計複雜，特別是密鑰生成和快速傅立葉採樣算法實現難度較高。

套用領域

微算法科技在其量子安全區塊鏈中，將Falcon簽名作為後量子簽名層，採用NIST標準化的Falcon簽名方案替代傳統ECDSA，並與PQ-DPoL共識機制結合，實現交易的雙重簽名防禦體系。該套用旨在保障如數字貨幣等場景的交易安全，抵禦量子計算攻擊。

成都理工大學發明了一種基於輕量級Falcon簽名的物聯網身份認證方法。該方法針對資源受限的物聯網設備，通過密鑰稀疏化壓縮、疊代式FFT最佳化等技術實現輕量級Falcon簽名方案，用於設備身份認證與數據完整性保護。該方案通過最佳化適配僅有2kb RAM的微控制器，同時具備抗量子攻擊的安全性。

最佳化與實現進展

在算法效率最佳化方面，有研究對Falcon簽名方案中的關鍵步驟——快速傅立葉採樣算法進行了改進。通過將離線階段建立的Falcon樹預處理為採樣矩陣，再利用該矩陣對目標向量進行採樣，可將線上簽名階段的時間複雜度從O(n log n)降至O(n)。

針對物聯網等資源受限場景，Falcon簽名的實現技術也取得了重要進展。通過採用私鑰稀疏化壓縮、將快速傅立葉變換（FFT）的遞歸計算改為疊代式以降低記憶體占用、利用ARM Cortex-M等處理器的SIMD指令集並行加速蝶形操作與高斯採樣等最佳化手段，能夠在僅有2KB RAM的微控制器上實現Falcon-512簽名算法。