Low-Stack HAETAE for Memory-Constrained Microcontrollers

在只有 8kB 到 16kB SRAM 可用的微型控制器上運行後量子密碼學演算法，過去幾乎是不可能的任務。參考實作的 HAETAE 數位簽章方案在產生簽章時，堆疊記憶體消耗高達 141 kB，遠超出物聯網設備的硬體極限。最新由 Gustavo Banegas 領軍的密碼學研究團隊透過演算法解構與串流技術，成功將簽章堆疊從 141 kB 壓縮至 5.8 kB，降幅高達 95%，讓次世代資安標準成功登陸極度受限的邊緣硬體。

微控制器 8kB 靜態隨機存取記憶體的硬體極限

HAETAE 是一種基於模組晶格（module-lattice）的數位簽章方案，也是後量子密碼學（PQC，用於抵抗量子運算破解的加密技術）領域的重要技術分支。隨著量子電腦的運算能力日益強大，傳統基於 RSA 或橢圓曲線密碼學的加密標準預計將在未來幾年內受到嚴重威脅。為了確保長期的資訊安全，全球學術界與產業界正在積極推動 PQC 演算法的硬體部署。然而，將這類先進演算法移植到物聯網設備時，硬體資源立刻成為最大的物理瓶頸。許多部署於智慧工廠、感測器網路中的邊緣運算設備，往往僅配備 8 kB 到 16 kB 的 SRAM（靜態隨機存取記憶體）。

對於這類極度受限的微型設備而言，峰值堆疊使用量往往是決定演算法能否運行的絕對限制條件。HAETAE 的演算法特性本身帶有極大的記憶體壓力，其核心機制包含了複雜的超球體採樣器、維度龐大的暫態多項式向量，以及長度不固定的簽章酬載（例如提示陣列與高位元陣列）。當演算法在記憶體中展開時，這些變數會迅速填滿有限的可用空間。

在原始的參考實作中，HAETAE 在產生數位簽章時需要消耗高達 71 kB 到 141 kB 的堆疊記憶體。這對多數入門級微控制器來說是完全無法負擔的龐然大物。不僅是簽章生成，就連相對單純的金鑰生成與驗證過程，其記憶體足跡也遠超出現有硬體的規格極限。要讓 HAETAE 在這類設備上真正實用化，工程團隊必須在數學運算結構與底層硬體架構之間進行深度的重構與優化。

拒絕感知與提前中斷機制省下 95% 堆疊空間

為了解決 HAETAE 在記憶體消耗上的致命傷，研究團隊針對演算法的執行流程進行了外科手術般的解構，並引入了兩項關鍵的架構級優化。第一項是拒絕感知路徑分解。在傳統的密碼學實作中，數據編碼與數學運算往往是交織在一起的。這意味著無論最終的採樣結果是否符合安全條件並被系統接受，系統都會預先分配大量的記憶體區塊來暫存這些可能最終變成無效的數據。新的設計將編碼步驟完全隔離，演算法僅在數據確認通過接受門檻後才正式啟動編碼程序，藉此阻斷了大量不必要的記憶體佔用。

第二項核心技術則是元件級別提前拒絕。在晶格密碼學的簽章過程中，演算法經常需要計算向量的範數，並將其與特定的安全邊界數值進行比較，以確保簽章的隨機性與安全性。過去標準的做法是必須將完整的範數計算完畢後，再進行統一的判定。而團隊開發的新技術具備實時監控能力，在計算過程中一旦發現部分範數的數值已經超過了允許的安全邊界，就會立即觸發短路機制，強制中斷後續的回應計算程序。

這兩項技術的無縫結合，徹底避免了無效數學運算對堆疊記憶體的無謂消耗。根據實測數據，這些底層優化將 HAETAE 簽章生成的堆疊記憶體需求從原本的 71 kB - 141 kB 大幅壓縮至僅需 5.8 kB - 6.0 kB。同時，金鑰生成的峰值堆疊也成功降至 4.7 kB - 5.7 kB，驗證階段則降至 4.7 kB - 4.8 kB。這項技術突破代表演算法在涵蓋 HAETAE 所有安全等級的前提下，已能穩定運行於低階設備。

導入 rANS 逆向串流編碼消除變動長度緩衝區

除了流程阻斷機制，第三項核心突破在於資料編碼方式的徹底重構。在 HAETAE 簽章演算法中，包含了變動長度的提示與高位元陣列。在傳統的工程作法中，系統必須預先在 SRAM 中配置完整的暫存緩衝區，才能安全地處理這些長度無法預知的資料。這種必須保留安全餘裕的設計，直接導致了堆疊記憶體使用的暴增。

為了解決這個硬體痛點，研究團隊導入了使用 rANS（區間非對稱數字系統，一種高效率的熵編碼法）的逆向串流編碼技術。研究團隊透過逆向串流的架構設計，讓微控制器的處理器能在不需要配置完整大型緩衝區的情況下，直接對數據流進行即時編碼處理。

此外，團隊並未止步於編碼環節，他們還將這項技術與串流矩陣生成模組、具備串流高斯後端的雙向超球體採樣器，以及列串流驗證技術進行了全棧式的深度整合。透過將龐大且佔用記憶體的矩陣操作，精巧地拆解為微型處理器可依序消化的連續資料流，微控制器再也不需要一次性將所有多項式載入極度稀缺的記憶體中。這套串流設計哲學，從根本上解決了系統容量不足的核心問題。

實測：微控制器驗證速度較 ML-DSA 快 3.34 倍

為了驗證這些軟體優化技術在真實世界的實用性，研究團隊在一套採用 ARM Cortex-M4 處理器架構的 Nucleo-L4R5ZI 開發板上，進行了純 C 語言的編譯與實作。測試過程嚴格涵蓋了 HAETAE 的三個安全等級標準。由於不同安全等級在公鑰領域的定義差異以及底層拒絕結構的不同，不同等級的演算法也具備各自專屬的優化路徑。

研究團隊將優化結果與開源的基準項目 pqm4（主要針對 HAETAE-2 與 3），以及近期學術界發布的另一套記憶體優化版本進行了效能對比。量測數據顯示，在 HAETAE-2、3、5 三個安全等級中，金鑰生成程序的記憶體堆疊分別銳減了 75%、86% 與 8%；簽章生成階段分別減少了 92%、95% 與 24%；而驗證階段則減少了 85%、91% 與 22%。這是一次全方位的硬體資源瘦身。

在運算效能的權衡方面，受限於極端的記憶體資料壓縮與不斷切換的串流機制，金鑰與簽章生成的時間成本最多分別增加了 1.8 倍與 3.4 倍。然而，令人意外的是，驗證程序的運算效能卻逆勢提升，最高達到了 18% 的運算速度增長。值得注意的是，所有安全等級的驗證程序，如今都能完美控制在 8 kB 的系統記憶體之內。更重要的是，在同等的加密安全級別下，其硬體驗證速度比美國國家標準暨技術研究院現行的標準演算法 ML-DSA m4fstack 還要快上 2.34 倍到 3.34 倍。

演算法解構與串流技術讓後量子密碼學跨越微型硬體門檻，為物聯網資安建立實務標準。