计算机工程 ›› 2019, Vol. 45 ›› Issue (1): 109-114.doi: 10.19678/j.issn.1000-3428.0049277

• 安全技术 • 上一篇    下一篇

SWIFFT算法效率分析

李梦东1,2,邵玉芳2,孙玉情2,李杰1   

  1. 1.北京电子科技学院 信息安全系,北京 100070; 2.西安电子科技大学 通信工程学院,西安 710071
  • 收稿日期:2017-11-13 出版日期:2019-01-15 发布日期:2019-01-15
  • 作者简介:李梦东(1964—),男,教授,主研方向为信息安全、密码算法;邵玉芳、孙玉情、李杰,硕士研究生
  • 基金项目:

    国家重点研发计划项目(2016YFB0800304)

Efficiency Analysis of SWIFFT Algorithm

LI Mengdong 1,2,SHAO Yufang 2,SUN Yuqing 2,LI Jie 1   

  1. 1.Department of Information Security,Beijing Electronic Science and Technology Institute,Beijing 100070,China; 2.Institute of Communication Engineering,Xidian University,Xi’an 710071,China
  • Received:2017-11-13 Online:2019-01-15 Published:2019-01-15

摘要:

以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

中图分类号: