SWIFFT算法效率分析
|
摘要
以SWIFFT算法为重要组成部分的SWIFFTX杂凑算法因实现效率问题未能进入SHA-3第二轮竞选。为此,研究提高SWIFFTX杂凑算法效率的方法,分析SWIFFT算法的实现过程。通过绘制快速傅里叶变换(FFT)流向图,估算实现SWIFFT算法的加/减、乘法运算量。此外,还提出一种计算中间参数ω的方法。分析结果表明:当存储空间较少时,选用16点FFT实现SWIFFT算法效率更高;当存储空间充足时,选用8点FFT实现SWIFFT算法效率更高。
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) flowchart,it estimates the addition/subtraction and multiplication of the SWIFFT algorithm. In addition,it proposes a way to calculate the intermediate parameter ω. Analysis results showthat: 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.
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) flowchart,it estimates the addition/subtraction and multiplication of the SWIFFT algorithm. In addition,it proposes a way to calculate the intermediate parameter ω. Analysis results showthat: 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.
引文
[1]冯超逸,赵一鸣.基于理想格的可证明安全数字签名方案[J].计算机工程,2017,43(5):103-107.
[2]BRAKERSKI Z,VAIKUNTANATHAN V.Efficient fully homomorphic encryption from(standard)LWE[J].Foundations of Computer Science,2011(2):97-106.
[3]刘亚敏,李祥学,刘晗林.基于格的后量子密钥交换研究[J].密码学报,2017,4(5):485-497.
[4]来齐齐,杨波,禹勇,等.基于格的哈希证明系统的构造综述[J].密码学报,2017,4(5):474-484.
[5]张江.格上可编程杂凑函数的新构造[J].密码学报,2016,3(5):419-432.
[6]AJTAI M.Generating hard instances of lattice problems[C]//Proceedings of the 28th ACM Symposium on Theory of Computing.New York,USA:ACM Press,1996:99-108.
[7]MICCIANCIO D.Generalized compact knapsacks,cyclic lattices,and efficient one-w ay functions from w orst-case complexity assumptions[J].Computational Complexity,2007,16(4):365-411.
[8]PEIKERT C,ROSEN A.Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices[M]//HALEVI S,RABIN T.Theory of Cryptography.Berlin,Germany:Springer,2006:145-166.
[9]LYUBASHEVSKY V,MICCIANCIO D.Generalized compact knapsacks are collision resistant[M]//BUGLIESI M,PRENEEL B,SASSONE V,et al.Automata,Languages and Programming.Berlin,Germany:Springer,2006:144-155.
[10]LYUBASHEVSKY V,MICCIANCIO D,PEIKERT C,et al.SWIFFT:a modest proposal for FFT hashing[C]//Proceedings of FSE’08.Berlin,Germany:Springer,2008:54-72.
[11]ARBITMAN Y,DOGON G,LYUBASHEVSKY V,et al.SWIFFTX:a proposal for the SHA-3 standard[EB/OL].[2017-10-10].http://101.96.10.63/www.eecs.harvard.edu/~alon/PAPARS/lattices/swifftx.pdf.
[12]孙琦,郑德勋,沈仲琦.快速数论变换[M].北京:科学出版社,2015.
[13]BUCHMANN J,LINDNER R.Secure parameters for SWIFFT[C]//Proceedings of International Conference on Cryptology in India.Berlin,Germany:Springer,2009:1-17.
[14]柯召,孙琦.数论讲义[M].北京:高等教育出版社,1999.
[15]GYORFI T,CRET O,HANROT G,et al.Highthroughput hardw are architecture for the SWIFFT/SWIFFTX hash functions[C]//Proceedings of IACRCryptology.Washington D.C.,USA:IEEE Press,2012:343.
[16]许章,杨晓元,张薇.标准模型下具有IND-CCA2安全的混合加密方案[J].计算机应用研究,2016,33(4):1124-1127.
[2]BRAKERSKI Z,VAIKUNTANATHAN V.Efficient fully homomorphic encryption from(standard)LWE[J].Foundations of Computer Science,2011(2):97-106.
[3]刘亚敏,李祥学,刘晗林.基于格的后量子密钥交换研究[J].密码学报,2017,4(5):485-497.
[4]来齐齐,杨波,禹勇,等.基于格的哈希证明系统的构造综述[J].密码学报,2017,4(5):474-484.
[5]张江.格上可编程杂凑函数的新构造[J].密码学报,2016,3(5):419-432.
[6]AJTAI M.Generating hard instances of lattice problems[C]//Proceedings of the 28th ACM Symposium on Theory of Computing.New York,USA:ACM Press,1996:99-108.
[7]MICCIANCIO D.Generalized compact knapsacks,cyclic lattices,and efficient one-w ay functions from w orst-case complexity assumptions[J].Computational Complexity,2007,16(4):365-411.
[8]PEIKERT C,ROSEN A.Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices[M]//HALEVI S,RABIN T.Theory of Cryptography.Berlin,Germany:Springer,2006:145-166.
[9]LYUBASHEVSKY V,MICCIANCIO D.Generalized compact knapsacks are collision resistant[M]//BUGLIESI M,PRENEEL B,SASSONE V,et al.Automata,Languages and Programming.Berlin,Germany:Springer,2006:144-155.
[10]LYUBASHEVSKY V,MICCIANCIO D,PEIKERT C,et al.SWIFFT:a modest proposal for FFT hashing[C]//Proceedings of FSE’08.Berlin,Germany:Springer,2008:54-72.
[11]ARBITMAN Y,DOGON G,LYUBASHEVSKY V,et al.SWIFFTX:a proposal for the SHA-3 standard[EB/OL].[2017-10-10].http://101.96.10.63/www.eecs.harvard.edu/~alon/PAPARS/lattices/swifftx.pdf.
[12]孙琦,郑德勋,沈仲琦.快速数论变换[M].北京:科学出版社,2015.
[13]BUCHMANN J,LINDNER R.Secure parameters for SWIFFT[C]//Proceedings of International Conference on Cryptology in India.Berlin,Germany:Springer,2009:1-17.
[14]柯召,孙琦.数论讲义[M].北京:高等教育出版社,1999.
[15]GYORFI T,CRET O,HANROT G,et al.Highthroughput hardw are architecture for the SWIFFT/SWIFFTX hash functions[C]//Proceedings of IACRCryptology.Washington D.C.,USA:IEEE Press,2012:343.
[16]许章,杨晓元,张薇.标准模型下具有IND-CCA2安全的混合加密方案[J].计算机应用研究,2016,33(4):1124-1127.