American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020102

On the diffusion of the Improved Generalized Feistel

Tsonka Baicheva , and  Svetlana Topalova

Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, P.O.Box 323, 5000 Veliko Tarnovo, Bulgaria

* Corresponding author: Tsonka Baicheva

Received  October 2019 Revised  February 2020 Published  October 2020

Fund Project: The research of the first author was partially supported by the Bulgarian National Science Fund under Contract 12/8, 15.12.2017 and of the second author by the Bulgarian National Science Fund under Contract KP-06-N32/2-2019

We consider the Improved Generalized Feistel Structure (IGFS) suggested by Suzaki and Minematsu (LNCS, 2010). It is a generalization of the classical Feistel cipher. The message is divided into $ k $ subblocks, a Feistel transformation is applied to each pair of successive subblocks, and then a permutation of the subblocks follows. This permutation affects the diffusion property of the cipher. IGFS with relatively big $ k $ and good diffusion are of particular interest for light weight applications.

Suzaki and Minematsu (LNCS, 2010) study the case when one and the same permutation is applied at each round, while we consider IGFS with possibly different permutations at the different rounds. In this case we present permutation sequences yielding IGFS with the best known by now diffusion for all even $ k\le 2048 $. For $ k\le 16 $ they are found by a computer-aided search, while for $ 18\le k\le 2048 $ we first consider several recursive constructions of a permutation sequence for $ k $ subblocks from two permutation sequences for $ k_a< k $ and $ k_b< k $ subblocks respectively. Using computer, we apply these constructions to obtain permutation sequences with good diffusion for each even $ k\le 2048 $. Finally we obtain infinite families of permutation sequences for $ k>2048 $.

Keywords: Improved Generalized Feistel Structure, diffusion.
Citation: Tsonka Baicheva, Svetlana Topalova. On the diffusion of the Improved Generalized Feistel. Advances in Mathematics of Communications, doi: 10.3934/amc.2020102
References:
[1]

T. Baicheva and S. Topalova, On the diffusion property of the Improved Generalized Feistel with different permutations for each round, in Algebraic Informatics, CAI 2019 (eds. M. Ćirić, M. Droste and J.É. Pin), Lecture Notes in Computer Science, 11545 (2019), 38–49. doi: 10.1007/978-3-030-21363-3_4.  Google Scholar

[2]

T. Berger, M. Minier and G. Thomas, Extended generalized Feistel networks using matrix representation, Selected Areas in Cryptography–SAC 2013, Lecture Notes in Comput. Sci., Springer, Heidelberg, 8282 (2014), 289–305. doi: 10.1007/978-3-662-43414-7_15.  Google Scholar

[3]

T. Berger, J. Francq, M. Minier and G. Thomas, Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput, IEEE Transactions on Computers, 65 (2016), 2074-2089.  doi: 10.1109/TC.2015.2468218.  Google Scholar

[4]

D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B. Koo, C. Lee, D. Chang, J. Lee, K. Jeong, H. Kim, J. Kim and S. Chee, HIGHT: A new block cipher suitable for low-resource device, Lecture Notes in Computer Science - CHES, 4249 (2006), 46-59.  doi: 10.1007/11894063_4.  Google Scholar

[5]

K. Nyberg, Generalized Feistel networks, in Advances in Cryptology - ASIACRYPT '96 (eds. K. Kim and T. Matsumoto), Lecture Notes in Computer Science, 1163 (1996), 90–104. doi: 10.1007/BFb0034838.  Google Scholar

[6]

R. L. Rivest, M. J. B. Robshaw, R. Sidney and Y. L. Yin, The RC6 block cipher, August 1998. Available from: http://people.csail.mit.edu/rivest/pubs/RRSY98.pdf. Google Scholar

[7]

C. E. Shannon, Communication theory of secrecy systems, Bell System Technical Journal, 28 (1949), 656-715.  doi: 10.1002/j.1538-7305.1949.tb00928.x.  Google Scholar

[8]

T. Shirai, K. Shibutani, T. Akishita, S. Moriai and T. Iwata, The 128-bit block cipher CLEFIA (Extended abstract), Lecture Notes in Computer Science–FSE, 4593 (2007), 181-195.   Google Scholar

[9]

T. Suzaki and K. Minematsu, Improving the generalized Feistel, Lecture Notes in Computer Science–FSE, 6147 (2010), 19-39.  doi: 10.1007/978-3-642-13858-4_2.  Google Scholar

[10]

L. Zhang and W. Wu, Analysis of permutation choices for enhanced generalised Feistel structure with SP-type round function, IET Information Security, 11 (2017), 121-128.  doi: 10.1049/iet-ifs.2015.0433.  Google Scholar

[11]

Y. Zheng, T. Matsumoto and H. Imai, On the construction of block ciphers provably secure and not relying on any unproved hypothesis, Advances in Cryptology - CRYPTO'89, Lecture Notes in Computer Science, 435 (1990), 461–480. doi: 10.1007/0-387-34805-0_42.  Google Scholar

[12]

Y. Wang and W. Wu, New criterion for diffusion property and applications to improved GFS and EGFN, Designs Codes and Cryptography, 81 (2016), 393-412.  doi: 10.1007/s10623-015-0161-8.  Google Scholar

show all references

References:
[1]

T. Baicheva and S. Topalova, On the diffusion property of the Improved Generalized Feistel with different permutations for each round, in Algebraic Informatics, CAI 2019 (eds. M. Ćirić, M. Droste and J.É. Pin), Lecture Notes in Computer Science, 11545 (2019), 38–49. doi: 10.1007/978-3-030-21363-3_4.  Google Scholar

[2]

T. Berger, M. Minier and G. Thomas, Extended generalized Feistel networks using matrix representation, Selected Areas in Cryptography–SAC 2013, Lecture Notes in Comput. Sci., Springer, Heidelberg, 8282 (2014), 289–305. doi: 10.1007/978-3-662-43414-7_15.  Google Scholar

[3]

T. Berger, J. Francq, M. Minier and G. Thomas, Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput, IEEE Transactions on Computers, 65 (2016), 2074-2089.  doi: 10.1109/TC.2015.2468218.  Google Scholar

[4]

D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B. Koo, C. Lee, D. Chang, J. Lee, K. Jeong, H. Kim, J. Kim and S. Chee, HIGHT: A new block cipher suitable for low-resource device, Lecture Notes in Computer Science - CHES, 4249 (2006), 46-59.  doi: 10.1007/11894063_4.  Google Scholar

[5]

K. Nyberg, Generalized Feistel networks, in Advances in Cryptology - ASIACRYPT '96 (eds. K. Kim and T. Matsumoto), Lecture Notes in Computer Science, 1163 (1996), 90–104. doi: 10.1007/BFb0034838.  Google Scholar

[6]

R. L. Rivest, M. J. B. Robshaw, R. Sidney and Y. L. Yin, The RC6 block cipher, August 1998. Available from: http://people.csail.mit.edu/rivest/pubs/RRSY98.pdf. Google Scholar

[7]

C. E. Shannon, Communication theory of secrecy systems, Bell System Technical Journal, 28 (1949), 656-715.  doi: 10.1002/j.1538-7305.1949.tb00928.x.  Google Scholar

[8]

T. Shirai, K. Shibutani, T. Akishita, S. Moriai and T. Iwata, The 128-bit block cipher CLEFIA (Extended abstract), Lecture Notes in Computer Science–FSE, 4593 (2007), 181-195.   Google Scholar

[9]

T. Suzaki and K. Minematsu, Improving the generalized Feistel, Lecture Notes in Computer Science–FSE, 6147 (2010), 19-39.  doi: 10.1007/978-3-642-13858-4_2.  Google Scholar

[10]

L. Zhang and W. Wu, Analysis of permutation choices for enhanced generalised Feistel structure with SP-type round function, IET Information Security, 11 (2017), 121-128.  doi: 10.1049/iet-ifs.2015.0433.  Google Scholar

[11]

Y. Zheng, T. Matsumoto and H. Imai, On the construction of block ciphers provably secure and not relying on any unproved hypothesis, Advances in Cryptology - CRYPTO'89, Lecture Notes in Computer Science, 435 (1990), 461–480. doi: 10.1007/0-387-34805-0_42.  Google Scholar

[12]

Y. Wang and W. Wu, New criterion for diffusion property and applications to improved GFS and EGFN, Designs Codes and Cryptography, 81 (2016), 393-412.  doi: 10.1007/s10623-015-0161-8.  Google Scholar

Table 1.  IGFS with $ k\le 128 $ subblocks
$ k $ $ R_d $ $ R_D $ C Remark $ R_{SM} $
$ * $ 2 2 2 c - 2
$ * $ 4 4 4 c - 4
$ * $ 6 5 5 c - 5
$ * $ 8 6 6 c - 6
$ * $ 10 6 6 c - 7
$ * $ 12 7 7 c - 8
$ * $ 14 7 7 c - 8
$ * $ 16 7 7 c - 8
$ * $ 18 8 8 2 2.3.3 -
$ * $ 20 8 8 1 2.10 -
22 9 8 5 10+12 -
24 9 8 1 2.12 -
26 10 8 3 12+14 -
$ * $ 28 9 9 1 2.14 -
$ * $ 30 9 9 2 2.3.5 -
$ * $ 32 9 9 1 2.16 10
34 10 9 4 16+18 -
36 10 9 1 2.18 -
38 11 9 3 18+20 -
40 10 9 1 2.20 -
42 10 9 2 2.3.7 -
44 11 10 1 2.22 -
46 12 10 3 22+24 -
$ * $ 48 10 10 2 2.3.8 -
$ * $ 50 10 10 2 2.5.5 -
52 12 10 1 2.26 -
54 11 10 2 2.3.9 -
56 11 10 1 2.28 -
58 12 10 3 28+30 -
60 11 10 1 2.30 -
62 12 10 3 30+32 -
64 11 10 1 2.32 12
66 12 10 2 2.3.11 -
68 12 10 1 2.34 -
* 70 11 11 2 2.5.7 -
72 12 11 1 2.36 -
74 13 11 4 36+38 -
76 13 11 1 2.38 -
78 13 11 2 2.3.13 -
* 80 11 11 2 2.5.8 -
82 13 11 3 40+42 -
84 12 11 1 2.42 -
86 13 11 5 42+44 -
88 13 11 1 2.44 -
90 12 11 2 2.3.15 -
92 14 11 1 2.46 -
94 14 11 6 46+48 -
96 12 11 1 2.48 -
98 12 11 2 2.7.7 -
100 12 11 1 2.50 -
102 13 11 2 2.3.17 -
104 14 11 1 2.52 -
106 15 11 3 52+54 -
108 13 11 1 2.54 -
110 13 11 2 2.5.11 -
* 112 12 12 2 2.7.8 -
114 14 12 2 2.3.19 -
116 14 12 1 2.58 -
118 14 12 6 58+60 -
120 13 12 1 2.60 -
122 14 12 4 60+62 -
124 14 12 1 2.62 -
126 13 12 2 2.3.21 -
* 128 12 12 2 2.8.8 14
Table Options

Download as excel

$ k $ $ R_d $ $ R_D $ C Remark $ R_{SM} $
$ * $ 2 2 2 c - 2
$ * $ 4 4 4 c - 4
$ * $ 6 5 5 c - 5
$ * $ 8 6 6 c - 6
$ * $ 10 6 6 c - 7
$ * $ 12 7 7 c - 8
$ * $ 14 7 7 c - 8
$ * $ 16 7 7 c - 8
$ * $ 18 8 8 2 2.3.3 -
$ * $ 20 8 8 1 2.10 -
22 9 8 5 10+12 -
24 9 8 1 2.12 -
26 10 8 3 12+14 -
$ * $ 28 9 9 1 2.14 -
$ * $ 30 9 9 2 2.3.5 -
$ * $ 32 9 9 1 2.16 10
34 10 9 4 16+18 -
36 10 9 1 2.18 -
38 11 9 3 18+20 -
40 10 9 1 2.20 -
42 10 9 2 2.3.7 -
44 11 10 1 2.22 -
46 12 10 3 22+24 -
$ * $ 48 10 10 2 2.3.8 -
$ * $ 50 10 10 2 2.5.5 -
52 12 10 1 2.26 -
54 11 10 2 2.3.9 -
56 11 10 1 2.28 -
58 12 10 3 28+30 -
60 11 10 1 2.30 -
62 12 10 3 30+32 -
64 11 10 1 2.32 12
66 12 10 2 2.3.11 -
68 12 10 1 2.34 -
* 70 11 11 2 2.5.7 -
72 12 11 1 2.36 -
74 13 11 4 36+38 -
76 13 11 1 2.38 -
78 13 11 2 2.3.13 -
* 80 11 11 2 2.5.8 -
82 13 11 3 40+42 -
84 12 11 1 2.42 -
86 13 11 5 42+44 -
88 13 11 1 2.44 -
90 12 11 2 2.3.15 -
92 14 11 1 2.46 -
94 14 11 6 46+48 -
96 12 11 1 2.48 -
98 12 11 2 2.7.7 -
100 12 11 1 2.50 -
102 13 11 2 2.3.17 -
104 14 11 1 2.52 -
106 15 11 3 52+54 -
108 13 11 1 2.54 -
110 13 11 2 2.5.11 -
* 112 12 12 2 2.7.8 -
114 14 12 2 2.3.19 -
116 14 12 1 2.58 -
118 14 12 6 58+60 -
120 13 12 1 2.60 -
122 14 12 4 60+62 -
124 14 12 1 2.62 -
126 13 12 2 2.3.21 -
* 128 12 12 2 2.8.8 14
Table 2.  IGFS with $ 128<k\le 2048 $ subblocks and diffusion round $ R_d = R_D+1 $
$ k $ $ R_d $ $ R_D $ C Remark $ R_{SM} $
140 13 12 1 2.70 -
144 13 12 2 2.3.24 -
150 13 12 2 2.3.25 -
160 13 12 1 2.80 -
180 14 13 1 2.90 -
192 14 13 1 2.96 -
196 14 13 1 2.98 -
200 14 13 1 2.100 -
210 14 13 2 2.3.35 -
224 14 13 1 2.112 -
240 14 13 2 2.3.40 -
250 14 13 2 2.5.25 -
256 14 13 1 2.128 16
294 15 14 2 2.3.49 -
300 15 14 1 2.150 -
320 15 14 1 2.160 -
336 15 14 2 2.3.56 -
350 15 14 2 2.5.35 -
384 15 14 2 2.3.64 -
400 15 14 2 2.5.40 -
480 16 15 1 2.240 -
490 16 15 2 2.5.49 -
500 16 15 1 2.250 -
512 16 15 1 2.256 18
560 16 15 2 2.5.56 -
640 16 15 2 2.5.64 -
768 17 16 1 2.384 -
784 17 16 2 2.7.56 -
800 17 16 1 2.400 -
896 17 16 2 2.7.64 -
1024 17 16 2 2.8.64 20
1250 18 17 2 2.5.125 -
1280 18 17 1 2.640 -
2000 19 18 2 2.5.200 -
2048 19 18 1 2.1024 22
Table Options

Download as excel

$ k $ $ R_d $ $ R_D $ C Remark $ R_{SM} $
140 13 12 1 2.70 -
144 13 12 2 2.3.24 -
150 13 12 2 2.3.25 -
160 13 12 1 2.80 -
180 14 13 1 2.90 -
192 14 13 1 2.96 -
196 14 13 1 2.98 -
200 14 13 1 2.100 -
210 14 13 2 2.3.35 -
224 14 13 1 2.112 -
240 14 13 2 2.3.40 -
250 14 13 2 2.5.25 -
256 14 13 1 2.128 16
294 15 14 2 2.3.49 -
300 15 14 1 2.150 -
320 15 14 1 2.160 -
336 15 14 2 2.3.56 -
350 15 14 2 2.5.35 -
384 15 14 2 2.3.64 -
400 15 14 2 2.5.40 -
480 16 15 1 2.240 -
490 16 15 2 2.5.49 -
500 16 15 1 2.250 -
512 16 15 1 2.256 18
560 16 15 2 2.5.56 -
640 16 15 2 2.5.64 -
768 17 16 1 2.384 -
784 17 16 2 2.7.56 -
800 17 16 1 2.400 -
896 17 16 2 2.7.64 -
1024 17 16 2 2.8.64 20
1250 18 17 2 2.5.125 -
1280 18 17 1 2.640 -
2000 19 18 2 2.5.200 -
2048 19 18 1 2.1024 22
[1]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319
[2]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345
[3]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461
[4]

Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060
[5]

Bingyan Liu, Xiongbing Ye, Xianzhou Dong, Lei Ni. Branching improved Deep Q Networks for solving pursuit-evasion strategy solution of spacecraft. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021016
[6]

Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129
[7]

Adrian Viorel, Cristian D. Alecsa, Titus O. Pinţa. Asymptotic analysis of a structure-preserving integrator for damped Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020407
[8]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[9]

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345
[10]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346
[11]

Jie Shen, Nan Zheng. Efficient and accurate sav schemes for the generalized Zakharov systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 645-666. doi: 10.3934/dcdsb.2020262
[12]

Gongbao Li, Tao Yang. Improved Sobolev inequalities involving weighted Morrey norms and the existence of nontrivial solutions to doubly critical elliptic systems involving fractional Laplacian and Hardy terms. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020469
[13]

Xin-Guang Yang, Lu Li, Xingjie Yan, Ling Ding. The structure and stability of pullback attractors for 3D Brinkman-Forchheimer equation with delay. Electronic Research Archive, 2020, 28 (4) : 1395-1418. doi: 10.3934/era.2020074
[14]

Feimin Zhong, Jinxing Xie, Yuwei Shen. Bargaining in a multi-echelon supply chain with power structure: KS solution vs. Nash solution. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020172
[15]

Pavel Eichler, Radek Fučík, Robert Straka. Computational study of immersed boundary - lattice Boltzmann method for fluid-structure interaction. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 819-833. doi: 10.3934/dcdss.2020349
[16]

Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128
[17]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171
[18]

Do Lan. Regularity and stability analysis for semilinear generalized Rayleigh-Stokes equations. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021002
[19]

Anna Anop, Robert Denk, Aleksandr Murach. Elliptic problems with rough boundary data in generalized Sobolev spaces. Communications on Pure & Applied Analysis, 2021, 20 (2) : 697-735. doi: 10.3934/cpaa.2020286
[20]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363

2019 Impact Factor: 0.734

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences