SWIFFT算法效率分析

作者：李梦东; 邵玉芳; 孙玉情; 李杰

来源：计算机工程, 2019, 45(01): 109-114.

DOI：10.19678/j.issn.1000-3428.0049277

• 杂凑函数
• SWIFFT压缩函数
• R-SIS问题
• 快速傅里叶变换
• 效率分析

以SWIFFT算法为重要组成部分的SWIFFTX杂凑算法因实现效率问题未能进入SHA-3第二轮竞选。为此,研究提高SWIFFTX杂凑算法效率的方法,分析SWIFFT算法的实现过程。通过绘制快速傅里叶变换(FFT)流向图,估算实现SWIFFT算法的加/减、乘法运算量。此外,还提出一种计算中间参数ω的方法。分析结果表明:当存储空间较少时,选用16点FFT实现SWIFFT算法效率更高;当存储空间充足时,选用8点FFT实现SWIFFT算法效率更高。

• 单位
  北京电子科技学院; 西安电子科技大学