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]

Xiao-Wen Chang, David Titley-Peloquin. An improved algorithm for generalized least squares estimation. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 451-461. doi: 10.3934/naco.2020044
[2]

Guangmei Shao, Wei Xue, Gaohang Yu, Xiao Zheng. Improved SVRG for finite sum structure optimization with application to binary classification. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2253-2266. doi: 10.3934/jimo.2019052
[3]

José A. Cañizo, Alexis Molino. Improved energy methods for nonlocal diffusion problems. Discrete & Continuous Dynamical Systems, 2018, 38 (3) : 1405-1425. doi: 10.3934/dcds.2018057
[4]

Jishan Fan, Yasuhide Fukumoto, Yong Zhou. Logarithmically improved regularity criteria for the generalized Navier-Stokes and related equations. Kinetic & Related Models, 2013, 6 (3) : 545-556. doi: 10.3934/krm.2013.6.545
[5]

Maxime Breden. Applications of improved duality lemmas to the discrete coagulation-fragmentation equations with diffusion. Kinetic & Related Models, 2018, 11 (2) : 279-301. doi: 10.3934/krm.2018014
[6]

Ihab Haidar, Alain Rapaport, Frédéric Gérard. Effects of spatial structure and diffusion on the performances of the chemostat. Mathematical Biosciences & Engineering, 2011, 8 (4) : 953-971. doi: 10.3934/mbe.2011.8.953
[7]

Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201
[8]

Hassan Belhadj, Samir Khallouq, Mohamed Rhoudaf. Parallelization of a finite volumes discretization for anisotropic diffusion problems using an improved Schur complement technique. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020260
[9]

Liang Zhang, Zhi-Cheng Wang. Threshold dynamics of a reaction-diffusion epidemic model with stage structure. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3797-3820. doi: 10.3934/dcdsb.2017191
[10]

Tianran Zhang. Traveling waves for a reaction-diffusion model with a cyclic structure. Discrete & Continuous Dynamical Systems - B, 2020, 25 (5) : 1859-1870. doi: 10.3934/dcdsb.2020006
[11]

Yueding Yuan, Zhiming Guo, Moxun Tang. A nonlocal diffusion population model with age structure and Dirichlet boundary condition. Communications on Pure & Applied Analysis, 2015, 14 (5) : 2095-2115. doi: 10.3934/cpaa.2015.14.2095
[12]

Liming Wang. A passivity-based stability criterion for reaction diffusion systems with interconnected structure. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 303-323. doi: 10.3934/dcdsb.2012.17.303
[13]

Stefan Possanner, Claudia Negulescu. Diffusion limit of a generalized matrix Boltzmann equation for spin-polarized transport. Kinetic & Related Models, 2011, 4 (4) : 1159-1191. doi: 10.3934/krm.2011.4.1159
[14]

Antoine Mellet, Jean-Michel Roquejoffre, Yannick Sire. Generalized fronts for one-dimensional reaction-diffusion equations. Discrete & Continuous Dynamical Systems, 2010, 26 (1) : 303-312. doi: 10.3934/dcds.2010.26.303
[15]

L. Cherfils, Y. Il'yasov. On the stationary solutions of generalized reaction diffusion equations with $p\& q$-Laplacian. Communications on Pure & Applied Analysis, 2005, 4 (1) : 9-22. doi: 10.3934/cpaa.2005.4.9
[16]

Yukio Kan-On. Bifurcation structures of positive stationary solutions for a Lotka-Volterra competition model with diffusion II: Global structure. Discrete & Continuous Dynamical Systems, 2006, 14 (1) : 135-148. doi: 10.3934/dcds.2006.14.135
[17]

Yukio Kan-On. Structure on the set of radially symmetric positive stationary solutions for a competition-diffusion system. Conference Publications, 2013, 2013 (special) : 427-436. doi: 10.3934/proc.2013.2013.427
[18]

Xiao Wu, Mingkang Ni. Solution of contrast structure type for a reaction-diffusion equation with discontinuous reactive term. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020341
[19]

Shuling Yan, Shangjiang Guo. Dynamics of a Lotka-Volterra competition-diffusion model with stage structure and spatial heterogeneity. Discrete & Continuous Dynamical Systems - B, 2018, 23 (4) : 1559-1579. doi: 10.3934/dcdsb.2018059
[20]

Alexey Cheskidov, Songsong Lu. The existence and the structure of uniform global attractors for nonautonomous Reaction-Diffusion systems without uniqueness. Discrete & Continuous Dynamical Systems - S, 2009, 2 (1) : 55-66. doi: 10.3934/dcdss.2009.2.55

2019 Impact Factor: 0.734

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences