Falcon签名方案中格高斯采样算法的快速实现技术  

Fast Implementation of Lattice Gaussian Sampling Algorithm in Falcon Signature Scheme

作　　者：王师宇 高海英[1] 宋杨 WANG Shi-Yu;GAO Hai-Ying;SONG Yang(Information Engineering University,Zhengzhou 450001,China)

机构地区：[1]信息工程大学,郑州450001

出　　处：《密码学报(中英文)》2025年第1期133-147,共15页Journal of Cryptologic Research

基　　金：国家自然科学基金(61902428)。

摘　　要：Falcon签名方案是NIST公布的后量子数字签名标准之一.Falcon签名方案的关键步骤是快速傅里叶采样算法,该算法是Babai最近平面算法的一个变体.具体实现时,在离线阶段建立Falcon树,存储复杂度是O(n log n);在线签名阶段采用函数的递归调用方法输出短向量,时间复杂度O(n log n).为了降低在线签名阶段的时间复杂度,本文对快速傅里叶采样算法的实现方法进行改进,首先将Falcon树预处理为采样矩阵,再利用矩阵对经过排列变换的目标向量进行采样,最后输出与原算法相同的结果,改进算法的在线阶段时间复杂度降至O(n),从而提高了Falcon签名方案在线阶段的实现效率.The Falcon signature scheme is a post-quantum digital signature standardization that has been published by the National Institute of Standards and Technology(NIST).The key step of Falcon signature scheme is the fast Fourier sampling algorithm,which is a variant of Babai’s nearest plane algorithm.In the specific implementation,the Falcon tree is established in the offline stage,and the storage complexity is O(n log n).In the online signature stage,the recursive call method of functions is used to output short vectors,exhibiting a time complexity of O(n log n).In order to reduce the time complexity of the online signature stage,this study improved the implementation method of the fast Fourier sampling algorithm.Firstly,preprocess the Falcon tree into a sampling matrix,then use the matrix to sample the target vector after permutation transformation,and finally output the same result as the original algorithm.The time complexity of the online phase of the improved algorithm has been reduced to O(n),thereby enhancing the implementation efficiency of the online phase of the Falcon signature scheme.

关 键 词：NTRU格 Falcon签名方案 快速傅里叶采样 最近平面算法 

分 类 号：TN918.4[电子电信—通信与信息系统]