\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

On the diffusion of the Improved Generalized Feistel

  • * Corresponding author: Tsonka Baicheva

    * Corresponding author: Tsonka Baicheva 

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 Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • 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 $.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
  • [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. BergerJ. FrancqM. 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. HongJ. SungS. HongJ. LimS. LeeB. KooC. LeeD. ChangJ. LeeK. JeongH. KimJ. 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. ShiraiK. ShibutaniT. AkishitaS. 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.
  • 加载中

Tables(2)

SHARE

Article Metrics

HTML views(1983) PDF downloads(393) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return