一种提高S盒非线性度的新算法

doi:10.3969/j.issn.1001-2400.2010.06.007

Abstract

Abstract:

An S-box is an important nonlinear component of block cipher algorithms.Using the idea of swapping two output vectors to increase nonlinearity of the S-Boxes, we propose a method for improving the nonlinearity by swapping three output vectors, namely, a new three-point hill-climbing algorithm.This method is simple and more efficient in implementation. Moreover, it could further improve the nonlinearity when William Millan's two-point hill-climbing could not. On the basis of this, an optimization algorithm based on the hill-climbing algorithm for improving the nonlinearity of the S-Boxes is presented, which overcomes the disadvantage of existing algorithms that cannot improve the nonlinearity further. Numerical results of testing for some small variables S-Boxes show the correctness and efficiency of the proposed algorithm.

Key words: S-Boxes, nonlinearity, Walsh transformation, hill-climbing algorithm

GAO Sheng;MA Wen-ping;GUO Na;YAN Ya-jun. Novel method for increasing the nonlinearity of S-Boxes[J].J4, 2010, 37(6): 1017-1021.

References

[1] Matsui M. Linear Cryptanalysis Method for DES Cipher[C]//Advances in Cryptology-EUROCRYPT'93, LNCS765. Berlin: Springer-Verlag, 1994: 386-397.
[2] Millan W. How to Improve the Nonlinearity of Bijective S-boxes[C]//ACISP'98, LNCS1438. Berlin: Springer-Verlag, 1998: 181-192.
[3] Millan W, Clark A, Dawson E. Smart Hill Climbing Finds Better Boolean Functions[C]//Proceedings of the First International Conference on Information and Communications Security, LNCS 1334. Berlin: Springer-Verlag, 1997: 149-158.
[4] Millan W, Burnett L, Carter G, et al. Evolutionary Heuristics for Finding Cryptographically Strong S-Boxes[C]//ICICS'99, LNCS1726. Berlin: Springer-Verlag, 1999: 263-274.
[5] 陈华, 吴文玲, 冯登国. 提高S盒非线性度的有效算法[J]. 计算机科学, 2005, 32(10): 68-70.
Chen Hua, Wu Wenling, Feng Dengguo. An Effective Algorithm to Increase the Nonlinearity of S-Boxes[J]. Computer Science, 2005,32(10): 68-70.
[6] 于亦舟, 欧海文. 一种改善双射S盒非线性度的方法[J]. 微计算机信息, 2007, 23(18): 29-30.
Yu Yizhou, Ou Haiwen. An Algorithm to Improve the Nonlinearity of Bijective S-Boxes[J]. Microcomputer Information, 2007, 23(18): 29-30.
[7] Chen H, Feng D G. An Effective Evolutionary Strategy for Bijective S-Boxes[C]//Proceeding of the IEEE Congress on Evolutionary Computation 2004(CEC'04). Portland: IEEE, 2004: 2120-2123.
[8] Nyberg K. Perfect Nonlinear S-Boxes[C]//Advances in Cryptology-EUROCRYPT'91, LNCS547. New York: Springer-Verlag, 1991: 378-386.
[9] Rothaus O S. On Bent Functions[J]. Journal of Combinatorial Theory(A), 1976(20): 300-305.
[10] Seberry J, Zhang X-M, Zheng Y. Relationships Among Nonlinearity Criteria[C]//Advances in Cryptology-EUROCRYPT'94, LNCS950. Berlin: Springer-Verlag, 1994: 376-388.
[11] 刘景伟,韦宝典,吕继强,等. AES S盒的密码特性分析[J]. 西安电子科技大学学报, 2004, 31(2): 256-259.
Liu Jingwei, Wei Baodian, Lü Jiqiang, et al. Analysis of the Cryptographic Properties of the AES S-box[J]. Journal of Xidian University, 2004, 31(2): 256-259.
[12] 韦宝典, 马文平, 王新梅. AES S盒的代数表达式[J]. 西安电子科技大学学报, 2003, 30(1): 29-32.
Wei Baodian, Ma Wenping, Wang Xinmei. The Algebraic Expression for the AES S Boxes[J].Journal of Xidian University, 2003, 30(1): 29-32.

Novel method for increasing the nonlinearity of S-Boxes

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 6

Metrics

Comments

Recommended 10

[1]	DONG Xinfeng,ZHANG Wenzheng,XU Chunxiang. 8 bits lightweight S-box with the Feistel structure [J]. Journal of Xidian University, 2021, 48(1): 69-75.
[2]	BAI Jing,SHI Yanyan,XUE Peiyun,GUO Qianyan. CFCC feature extraction for fusion of the power-law nonlinearity function and spectral subtraction [J]. Journal of Xidian University, 2019, 46(1): 86-92.
[3]	CUI Hua;ZHAO Xiang-mo;AI Bo. Separate BPNN-predistortion method for nonlinear HPA with memory [J]. J4, 2010, 37(3): 565-569.
[4]	SHANG Tao1;LI Feng1;WEN Ai-jun1;LIU Zeng-ji1;CHEN Jian-ping2. Numerical analysis of the two-pump fiber optical parametric amplifier based on the triangular photonic crystal fiber [J]. J4, 2008, 35(3): 383-387.
[5]	LIU Jing-wei;WEI Bao-dian;Lü Ji-qiang;WANG Xin-mei. Analysis of the cryptographic properties of the AES S-box [J]. J4, 2004, 31(2): 255-259.
[6]	ZHENG Lian-qing1;ZHANG Chuan-rong1;2;DONG Qing-kuan2;FU Xiao-tong2;XIAO Guo-zhen2. Study of nonlinearity bounds of Boolean functions [J]. J4, 2003, 30(2): 281-283.