摘要：

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

关键词: 杂凑函数, SWIFFT压缩函数, R-SIS问题, 快速傅里叶变换, 效率分析

Abstract:

The SWIFFTX Hash algorithm with the SWIFFT algorithm as an important component is failed to enter the second round of the SHA-3 campaign due to efficiency issues.In order to explore ways to improve the efficiency of the SWIFFTX Hash algorithm,this paper analyzes the implementation process of the SWIFFT algorithm.By drawing a Fast Fourier Transform(FFT) flow chart,it estimates the addition/subtraction and multiplication of the SWIFFT algorithm.In addition,it proposes a way to calculate the intermediate parameter ω.Analysis results show that:when the storage space is small,the 16-point FFT is more efficient to implement the SWIFFT algorithm;when the storage space is sufficient,the 8-point FFT is more efficient.

Key words: Hash function, SWIFFT compression function, R-SIS problem, Fast Fourier Transform(FFT), efficiency analysis

中图分类号: 

• TP309