On the diffusion of the Improved Generalized Feistel

Tsonka Baicheva; Svetlana Topalova

doi:10.3934/amc.2020102

Article Contents

2022, Volume 16, Issue 1: 95-114. Doi: 10.3934/amc.2020102

This issue Previous Article Binary sequences derived from differences of consecutive quadratic residues Next Article A geometric characterization of minimal codes and their asymptotic performance

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
^* Corresponding author: Tsonka Baicheva

Received: October 2019

Revised: February 2020

Early access: October 2020

Published: February 2022

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

Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

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:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.