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]

Jean Dolbeault, Maria J. Esteban, Michał Kowalczyk, Michael Loss. Improved interpolation inequalities on the sphere. Discrete & Continuous Dynamical Systems - S, 2014, 7 (4) : 695-724. doi: 10.3934/dcdss.2014.7.695
[2]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195
[3]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25
[4]

Ethan Akin, Julia Saccamano. Generalized intransitive dice II: Partition constructions. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021005
[5]

Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024
[6]

Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[7]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109
[8]

Luigi C. Berselli, Jishan Fan. Logarithmic and improved regularity criteria for the 3D nematic liquid crystals models, Boussinesq system, and MHD equations in a bounded domain. Communications on Pure & Applied Analysis, 2015, 14 (2) : 637-655. doi: 10.3934/cpaa.2015.14.637
[9]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027
[10]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182
[11]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[12]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189
[13]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258
[14]

Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223
[15]

Dan Wei, Shangjiang Guo. Qualitative analysis of a Lotka-Volterra competition-diffusion-advection system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2599-2623. doi: 10.3934/dcdsb.2020197
[16]

Nabahats Dib-Baghdadli, Rabah Labbas, Tewfik Mahdjoub, Ahmed Medeghri. On some reaction-diffusion equations generated by non-domiciliated triatominae, vectors of Chagas disease. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021004
[17]

Meiqiao Ai, Zhimin Zhang, Wenguang Yu. First passage problems of refracted jump diffusion processes and their applications in valuing equity-linked death benefits. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021039
[18]

Vo Anh Khoa, Thi Kim Thoa Thieu, Ekeoma Rowland Ijioma. On a pore-scale stationary diffusion equation: Scaling effects and correctors for the homogenization limit. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2451-2477. doi: 10.3934/dcdsb.2020190

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (35)
  • HTML views (180)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences