一种适合资源受限设备的Falcon实现
发布时间：2021-04-01 00:35
Falcon是通过NIST第一轮筛选的唯一的基于NTRU格的签名方案.相较于其它的签名设计,Falcon的公钥长度和签名长度都较短,可有效降低通信的复杂度.它的劣势在于算法设计复杂,特别是其中的密钥生成算法和快速傅里叶采样算法难以理解且需要精细实现.本文分析了在内存资源受限的设备中实现Falcon签名方案的可行性,经过优化后,运行Falcon签名算法需要的动态内存降低到参考实现的37%.采用本文提出的实现方法,则签名需要334.7 ms,签名验证需要6.16 ms.
【文章来源】：微电子学与计算机. 2020,37(09)北大核心
【文章页数】：7 页
【部分图文】：
高度为9的Falcon二叉树
在三元情形下,即n=768时,快速傅里叶采样算法和计算Falcon 三元树的算法可参考文献[3],由于篇幅限制,不在此给出具体算法.此时,Falcon 三元树共有9层,可表示为长度为8 448的数组,数组中的每个元素又表示为64比特的双精度浮点数,如图2所示.与Falcon二叉树不同的是,Falcon三元树的第2层的根节点有三个子节点.
回顾算法5可知,调用Falcon二叉树T的顺序为T的右子树-T的根节点-T的左子树.由于算法5是递归实现的,从而调用T的右子树时遵从由最底层开始,右叶子节点-父节点-左叶子节点的顺序.例如,n=512时,如图3所示,T的右子树的处理顺序为: [l 4096 ,l 5119 ]-[l 2816 ～l 3071 ]-[ l 3072 ～l 4095 ] .进一步,处理T的右子树时从第9层开始,调用叶子节点的顺序为 l 5119 -[ l 5116 ～l 5117 ]-l 5118 -[ l 5108 ～l 5111 ]-l 5115 -[ l 5112 ～l 5113 ]-l 5114 ?- [ l 2816 ,l 3071 ]?.如果可以在需要调用某个叶子节点时在线生成它的值,则不用总是保存完整的T,从而节省算法运行时需要的RAM开销.
本文编号：3112350
【文章来源】：微电子学与计算机. 2020,37(09)北大核心
【文章页数】：7 页
【部分图文】：
高度为9的Falcon二叉树
在三元情形下,即n=768时,快速傅里叶采样算法和计算Falcon 三元树的算法可参考文献[3],由于篇幅限制,不在此给出具体算法.此时,Falcon 三元树共有9层,可表示为长度为8 448的数组,数组中的每个元素又表示为64比特的双精度浮点数,如图2所示.与Falcon二叉树不同的是,Falcon三元树的第2层的根节点有三个子节点.
回顾算法5可知,调用Falcon二叉树T的顺序为T的右子树-T的根节点-T的左子树.由于算法5是递归实现的,从而调用T的右子树时遵从由最底层开始,右叶子节点-父节点-左叶子节点的顺序.例如,n=512时,如图3所示,T的右子树的处理顺序为: [l 4096 ,l 5119 ]-[l 2816 ～l 3071 ]-[ l 3072 ～l 4095 ] .进一步,处理T的右子树时从第9层开始,调用叶子节点的顺序为 l 5119 -[ l 5116 ～l 5117 ]-l 5118 -[ l 5108 ～l 5111 ]-l 5115 -[ l 5112 ～l 5113 ]-l 5114 ?- [ l 2816 ,l 3071 ]?.如果可以在需要调用某个叶子节点时在线生成它的值,则不用总是保存完整的T,从而节省算法运行时需要的RAM开销.
本文编号：3112350
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3112350.html
