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

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

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

【部分圖文】：

高度為9的Falcon二叉樹

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

回顧算法5可知,調(diào)用Falcon二叉樹T的順序?yàn)門的右子樹-T的根節(jié)點(diǎn)-T的左子樹.由于算法5是遞歸實(shí)現(xiàn)的,從而調(diào)用T的右子樹時(shí)遵從由最底層開始,右葉子節(jié)點(diǎn)-父節(jié)點(diǎn)-左葉子節(jié)點(diǎn)的順序.例如,n=512時(shí),如圖3所示,T的右子樹的處理順序?yàn)? [l 4096 ,l 5119 ]-[l 2816 ～l 3071 ]-[ l 3072 ～l 4095 ] .進(jìn)一步,處理T的右子樹時(shí)從第9層開始,調(diào)用葉子節(jié)點(diǎn)的順序?yàn)?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)用某個(gè)葉子節(jié)點(diǎn)時(shí)在線生成它的值,則不用總是保存完整的T,從而節(jié)省算法運(yùn)行時(shí)需要的RAM開銷.


本文編號(hào)：3112350