American Institute of Mathematical Sciences

Advanced
February  2022, 16(1): 95-114. 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  February 2022 Early access  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, 2022, 16 (1) : 95-114. 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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. 

[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.

[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.

[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.

[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.

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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. 

[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.

[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.

[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.

[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.

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 and 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 and 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 and 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 and 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 and 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]

Guillaume Cantin, Alexandre Thorel. On a generalized diffusion problem: A complex network approach. Discrete and Continuous Dynamical Systems - B, 2022, 27 (4) : 2345-2365. doi: 10.3934/dcdsb.2021135
[9]

Hassan Belhadj, Samir Khallouq, Mohamed Rhoudaf. Parallelization of a finite volumes discretization for anisotropic diffusion problems using an improved Schur complement technique. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2075-2099. doi: 10.3934/dcdss.2020260
[10]

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

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

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

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

Hongfei Xu, Jinfeng Wang, Xuelian Xu. Dynamics and pattern formation in a cross-diffusion model with stage structure for predators. Discrete and Continuous Dynamical Systems - B, 2022, 27 (8) : 4473-4489. doi: 10.3934/dcdsb.2021237
[15]

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

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

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

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

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
[20]

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

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (368)
  • HTML views (562)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy