Falcon是通過NIST第一輪篩選的唯一的基于NTRU格的簽名方案.相較于其它的簽名設(shè)計,Falcon的公鑰長度和簽名長度都較短,可有效降低通信的復(fù)雜度.它的劣勢在于算法設(shè)計復(fù)雜,特別是其中的密鑰生成算法和快速傅里葉采樣算法難以理解且需要精細實現(xiàn).本文分析了在內(nèi)存資源受限的設(shè)備中實現(xiàn)Falcon簽名方案的可行性,經(jīng)過優(yōu)化后,運行Falcon簽名算法需要的動態(tài)內(nèi)存降低到參考實現(xiàn)的37%.采用本文提出的實現(xiàn)方法,則簽名需要334.7 ms,簽名驗證需要6.16 ms. 

【文章來源】：微電子學(xué)與計算機. 2020,37(09)北大核心

【文章頁數(shù)】：7 頁

【部分圖文】：

高度為9的Falcon二叉樹

在三元情形下,即n=768時,快速傅里葉采樣算法和計算Falcon 三元樹的算法可參考文獻[3],由于篇幅限制,不在此給出具體算法.此時,Falcon 三元樹共有9層,可表示為長度為8 448的數(shù)組,數(shù)組中的每個元素又表示為64比特的雙精度浮點數(shù),如圖2所示.與Falcon二叉樹不同的是,Falcon三元樹的第2層的根節(jié)點有三個子節(jié)點.

回顧算法5可知,調(diào)用Falcon二叉樹T的順序為T的右子樹-T的根節(jié)點-T的左子樹.由于算法5是遞歸實現(xiàn)的,從而調(diào)用T的右子樹時遵從由最底層開始,右葉子節(jié)點-父節(jié)點-左葉子節(jié)點的順序.例如,n=512時,如圖3所示,T的右子樹的處理順序為: [l 4096 ,l 5119 ]-[l 2816 ～l 3071 ]-[ l 3072 ～l 4095 ] .進一步,處理T的右子樹時從第9層開始,調(diào)用葉子節(jié)點的順序為 l 5119 -[ l 5116 ～l 5117 ]-l 5118 -[ l 5108 ～l 5111 ]-l 5115 -[ l 5112 ～l 5113 ]-l 5114 ?- [ l 2816 ,l 3071 ]?.如果可以在需要調(diào)用某個葉子節(jié)點時在線生成它的值,則不用總是保存完整的T,從而節(jié)省算法運行時需要的RAM開銷.


本文編號：3112350