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

Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations

  • *Corresponding author: Selçuk Kavut

    *Corresponding author: Selçuk Kavut 

This work is supported financially by Balıkesir University under grant BAP 2015/23

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • We first give a brief survey of the results on highly nonlinear single-output Boolean functions and bijective S-boxes that are symmetric under some permutations. After that, we perform a heuristic search for the symmetric (and involution) S-boxes which are bijective in dimension 8 and identify corresponding permutations yielding rich classes in terms of cryptographically desirable properties.

    Mathematics Subject Classification: 11T71, 94A60.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  A summary of the highest nonlinearities for odd $ n\ge 9 $

    Number of variables ($ n $) 9 11 13 15
    Bounds
    Bent concatenation bound 240 992 4032 16256
    ($ 2^{n-1}-2^\frac{n-1}{2} $)
    Upper bound 244 1000 4050 16292
    ($ 2\left\lfloor 2^{n-2}-2^{\frac{n}{2}-2}\right\rfloor $)
    Unbalanced nonlinearities
    [18] $ - $ $ - $ $ - $ 16276
    [13] 242 996 4040 $ - $
    Balanced nonlinearities
    [15] $ - $ $ - $ 4036 $ - $
    [20] $ - $ $ - $ $ - $ 16272
     | Show Table
    DownLoad: CSV

    Table 2.  Best achieved cryptographic properties [nonlinearity, differential uniformity, algebraic degree]

    $ \# $ Representative
    permutation
    Space
    size
    Best result
    (for involution S-boxes)
    Best result
    1 $ (7,6,2,1,8,5,4,3) $ $ 2^{147.93} $ $ [84,44,7] $ $ [84,44,7] $
    2 $ (2,3,1,7,4,5,6,8) $ $ 2^{191.48} $ $ [84,52,7] $ $ [84,52,7] $
    3 $ (6,7,5,8,4,3,1,2)^a $ $ 2^{208.29} $ $ \bf{[106,6,7]} $ $ \bf{[106,6,7]}, \bf{[108,8,6]} $
    4 $ (4,3,2,5,8,1,7,6) $ $ 2^{227.35} $ $ [0, -, -] $ $ [0, -, -] $
    5 $ (4,5,3,2,8,1,6,7) $ $ 2^{243.74} $ $ \bf {[106,6,7]} $ $ \bf {[106,6,7]} $
    6 $ (8,3,4,6,7,1,5,2) $ $ 2^{277.78} $ $ [104,6,7] $ $ [104,6,7], {\bf{[106,8,7]}} $
    7 $ (8,6,3,5,2,1,7,4) $ $ 2^{283.02} $ $ [104,10,7] $ $ \it {[104,8,7]} $
    8 $ (4,6,7,5,1,2,3,8) $ $ 2^{357.97} $ $ [84,44,7] $ $ [84,44,7] $
    9 $ (2,6,3,4,5,8,1,7) $ $ 2^{358.65} $ $ [100,10,7] $ $ [100,10,7],\it{[104,20,7]} $
    10 $ (7,3,6,1,8,2,4,5) $ $ 2^{359.22} $ $ [0, -, -] $ $ [0, -, -] $
    11 $ (7,6,1,2,3,8,5,4)^b $ $ 2^{412.21} $ $ [104,6,7] $ $ [104,6,7], {\bf{[106,8,7]}} $
    12 $ (2,7,4,3,5,6,1,8) $ $ 2^{431.91} $ $ [0, -, -] $ $ [0, -, -] $
    13 $ (6,4,8,2,1,7,5,3) $ $ 2^{440.19} $ $ [84,22,7] $ $ [84,22,7] $
    14 $ (1,3,6,7,2,5,4,8) $ $ 2^{446.24} $ $ [84,22,7] $ $ [84,22,7] $
    15 $ (1,5,6,4,3,2,7,8) $ $ 2^{476.86} $ $ [84,52,7] $ $ [84,52,7] $
    16 $ (4,3,8,5,1,6,7,2) $ $ 2^{565.87} $ $ [104,6,7] $ $ [104,6,7] $
    17 $ (1,6,3,4,2,5,7,8) $ $ 2^{693.43} $ $ [84,44,7] $ $ [84,44,7] $
    18 $ (7,6,5,8,3,2,1,4)^c $ $ 2^{824.73} $ $ [104,6,7] $ $ [104,6,7] $
    19 $ (1,5,8,4,2,7,6,3) $ $ 2^{835.24} $ $ [104,8,7] $ $ [104,8,7] $
    20 $ (1,2,7,4,5,8,3,6) $ $ 2^{890.27} $ $ [84,22,7] $ $ [84,22,7] $
    21 $ (8,2,3,4,5,6,7,1) $ $ 2^{1076.16} $ $ [0, -, -] $ $ [0, -, -] $
    22 $ (1,2,3,4,5,6,7,8)^d $ $ 2^{1684} $ $ [102,6,7] $ $ \it{[104,6,7]} $
    $ ^a: $ Linear equivalet to RSSBs
    $ ^b: $ Linear equivalent to 2-RSSBs
    $ ^c: $ Linear equivalent to 4-RSSBs
    $ ^d: $ The search space of all bijective S-boxes
     | Show Table
    DownLoad: CSV
  • [1] M. Bartholomew-Biggs, Chapter 5: The steepest descent method, in Nonlinear Optimization with Financial Applications. Springer US, (2005), 51–64.
    [2] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.
    [3] K. A. BrowningJ. F. DillonM. T. McQuistan and A. J. Wolfe, An APN permutation in dimension six, Contemporary Mathematics, 518 (2010), 33-42.  doi: 10.1090/conm/518/10194.
    [4] C. Ding, G. Xiao and W. Shan, The Stability Theory of Stream Ciphers, Lecture Notes in Computer Science, 561. Springer-Verlag, Berlin Heidelberg, 1991. doi: 10.1007/3-540-54973-0.
    [5] H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, Lecture Notes in Computer Science, 1008 (1994), 61-74.  doi: 10.1007/3-540-60590-8_5.
    [6] E. Filiol and C. Fontaine, Highly nonlinear balanced Boolean functions with a good correlation-immunity, Lecture Notes in Computer Science, 1403 (1998), 475-488.  doi: 10.1007/BFb0054147.
    [7] C. Fontaine, On some cosets of the first-order Reed-Muller code with high minimum weight, IEEE Transactions on Information Theory, 45 (1999), 1237-1243.  doi: 10.1109/18.761276.
    [8] X.-D. Hou, On the norm and covering radius of first-order Reed-Muller codes, IEEE Transactions on Information Theory, 43 (1997), 1025-1027.  doi: 10.1109/18.568715.
    [9] S. Kavut, Results on rotation-symmetric S-boxes, Information Sciences, 201 (2012), 93-113.  doi: 10.1016/j.ins.2012.02.030.
    [10] S. Kavut and Sevdenur Baloǧlu, Results on symmetric S-boxes constructed by concatenation of RSSBs, Cryptography and Communications, 11 (2019), 641–660, http://dx.doi.org/10.1007/s12095-018-0318-1. doi: 10.1007/s12095-018-0318-1.
    [11] S. KavutS. MaitraS. Sarkar and M. D. Yücel, Enumeration of 9-variable rotation symmetric Boolean functions having nonlinearity $>240$, Lecture Notes in Computer Science, 4329 (2006), 266-279.  doi: 10.1007/11941378_19.
    [12] S. KavutS. Maitra and M. D. Yücel, Search for Boolean functions with excellent profiles in the rotation symmetric class, IEEE Transactions on Information Theory, 53 (2007), 1743-1751.  doi: 10.1109/TIT.2007.894696.
    [13] S. Kavut and M. D. Yücel, 9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class, Information and Computation, 208 (2010), 341-350.  doi: 10.1016/j.ic.2009.12.002.
    [14] S. Maitra, Balanced Boolean function on 13-variables having nonlinearity strictly greater than the bent concatenation bound, Boolean Functions in Cryptology and Information Security, 173–182, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., 18, IOS, Amsterdam, 2008. Available from: https://eprint.iacr.org/2007/309.pdf.
    [15] S. Maitra, S. Kavut and M. D. Yücel, Balanced Boolean function on 13-variables having nonlinearity greater than the bent concatenation bound, Proceedings of Boolean Functions: Cryptography and Applications, (2008), 109–118.
    [16] M. Matsui, Linear cryptanalysis method for DES cipher, Lecture Notes in Computer Science, 765 (1993), 386-397.  doi: 10.1007/3-540-48285-7_33.
    [17] K. Nyberg, Differentially uniform mappings for cryptography, Lecture Notes in Computer Science, 765 (1994), 55-64.  doi: 10.1007/3-540-48285-7_6.
    [18] N. J. Patterson and D. H. Wiedemann, The covering radius of the $(2^15, 16)$ Reed-Muller code is at least 16276, IEEE Transactions on Information Theory, 29 (1983), 354-356.  doi: 10.1109/TIT.1983.1056679.
    [19] V. RijmenP. S. L. M. Barreto and D. L. Gazzoni Filho, Rotation symmetry in algebraically generated cryptographic substitution tables, Information Processing Letters, 106 (2008), 246-250.  doi: 10.1016/j.ipl.2007.09.012.
    [20] S. Sarkar and S. Maitra, Idempotents in the neighbourhood of Patterson-Wiedemann functions having Walsh spectra zeros, Designs, Codes and Cryptography, 49 (2008), 95-103.  doi: 10.1007/s10623-008-9181-y.
    [21] P. Stǎnicǎ and S. Maitra, Rotation symmetric Boolean functions - count and cryptographic properties, Discrete Applied Mathematics, 156 (2008), 1567-1580.  doi: 10.1016/j.dam.2007.04.029.
    [22] P. StǎnicǎS. Maitra and J. Clark, Results on rotation symmetric bent and correlation immune Boolean functions, Fast Software Encryption Workshop - FSE 2004, Lecture Notes in Computer Science, 3017 (2004), 161-177. 
  • 加载中

Tables(2)

SHARE

Article Metrics

HTML views(917) PDF downloads(822) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return