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

A class of weightwise almost perfectly balanced Boolean functions

  • *Corresponding author: Deepak Kumar Dalai

    *Corresponding author: Deepak Kumar Dalai 
Abstract / Introduction Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by
  • Constructing Boolean functions with good cryptographic properties over a subset of vectors with fixed Hamming weight $ E_{n,k} \subset {{\rm{I\!F}}}_2^n $ is significant in lightweight stream ciphers like FLIP [14]. In this article, we have given a construction for a class of $ n $-variable weightwise almost perfectly balanced (WAPB) Boolean functions from known support of an $ n_0 $-variable WAPB Boolean function where $ n_0 < n $. This is a generalization of constructing a weightwise perfectly balanced (WPB) Boolean function by Mesnager and Su [16]. We have studied some cryptographic properties like ANF, nonlinearity, weightwise nonlinearities, and algebraic immunity of the functions. The ANF of this function is obtained recursively, which would be a low-cost implementation in a lightweight stream cipher. Further, we have presented another class of WAPB Boolean functions by modifying the earlier function, and we studied some of its cryptographic properties. The nonlinearity and weightwise nonlinearities of the modified functions improve substantially.

    Mathematics Subject Classification: Primary: 94A60, 94D10, 06E30; Secondary: 68P25.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Listing of $\mathtt{nl}(f_n),\mathtt{nl}_k(f_n), \mathtt{GWNL}(f_n)$ for $9 \leq n \leq 15$

    n $ \mathtt{nl}$ $ \mathtt{nl}_2 $ $ \mathtt{nl}_3 $ $ \mathtt{nl}_4 $ $ \mathtt{nl}_5 $ $ \mathtt{nl}_6 $ $ \mathtt{nl}_7 $ $ \mathtt{nl}_8 $ $ \mathtt{nl}_9 $ $ \mathtt{nl}_{10} $ $ \mathtt{nl}_{11} $ $ \mathtt{nl}_{12} $ $ \mathtt{nl}_{13} $ $ \mathtt{nl}_{14} $ $ \mathtt{GWNL} $
    8 8 2 0 3 0 2 0 0 0 - - - - - 7
    9 16 2 2 3 3 2 2 0 0 - - - - - 16
    10 16 3 0 5 0 5 0 3 0 0 - - - - 16
    11 32 3 3 5 5 5 5 3 3 0 0 - - - 32
    12 32 3 0 7 0 10 0 8 0 3 0 0 - - 31
    13 64 3 3 7 7 10 10 8 8 3 3 0 0 - 62
    14 64 4 0 10 0 18 0 18 0 10 0 4 0 - 64
    15 128 4 4 10 10 18 18 18 18 10 10 4 4 0 128
    16 128 4 0 14 0 28 0 35 0 14 0 4 0 28 127
     | Show Table
    DownLoad: CSV

    Table 2.  Listing of $ \mathtt{nl}(F_n), \mathtt{nl}_k(F_n), \mathtt{GWNL}(F_n) $ for $ 9 \leq n \leq 16 $

    n $ \mathtt{nl} $ $ \mathtt{nl}_2 $ $ \mathtt{nl}_3 $ $ \mathtt{nl}_4 $ $ \mathtt{nl}_5 $ $ \mathtt{nl}_6 $ $ \mathtt{nl}_7 $ $ \mathtt{nl}_8 $ $ \mathtt{nl}_9 $ $ \mathtt{nl}_{10} $ $ \mathtt{nl}_{11} $ $ \mathtt{nl}_{12} $ $ \mathtt{nl}_{13} $ $ \mathtt{nl}_{14} $ $ \mathtt{GWNL} $
    8 82 7 13 14 14 7 0 0 0 - - - - - 55
    9 164 8 26 27 33 26 8 0 0 - - - - - 128
    10 356 10 28 47 66 49 32 10 0 0 - - - - 242
    11 712 11 44 79 113 171 93 43 11 0 0 - - - 565
    12 1504 12 45 127 234 210 244 127 50 12 0 0 - - 1061
    13 3008 13 63 177 361 582 594 371 178 79 13 0 0 - 2431
    14 6112 15 66 230 635 708 1016 709 575 230 72 15 0 - 4271
    15 12224 16 89 302 925 1510 2424 1725 1295 960 302 88 16 0 9652
    16 24338 17 91 378 1321 2001 3485 3002 3499 1995 1363 378 126 18 17464
     | Show Table
    DownLoad: CSV

    Table 3.  Comparison of $ \mathtt{nl}_k(F_n) $ with the upper bound(UB) presented in [1]

    $ n $ function $ \mathtt{nl} $ $ \mathtt{nl}_2 $ $ \mathtt{nl}_3 $ $ \mathtt{nl}_4 $ $ \mathtt{nl}_5 $ $ \mathtt{nl}_6 $ $ \mathtt{nl}_7 $ $ \mathtt{nl}_8 $ $ \mathtt{nl}_9 $ $ \mathtt{nl}_{10} $ $ \mathtt{nl}_{11} $ $ \mathtt{GWNL} $
    9 UB 244 15 37 57 57 37 15 - - - - 218
    $ F_9 $ 164 8 26 27 33 26 8 - - - - 128
    10 UB 496 19 54 97 118 97 54 19 - - - 498
    $ F_{10} $ 356 10 28 47 66 49 32 10 - - - 128
    11 UB 1000 23 76 155 220 220 155 76 23 - - 948
    $ F_{11} $ 712 11 44 79 113 171 93 43 11 - - 565
    12 UB 2016 28 102 236 381 446 381 236 102 28 - 1940
    $ F_{12} $ 1056 12 45 127 234 210 244 127 50 12 - 1061
    13 UB 4050 34 134 344 625 837 837 625 344 134 34 3948
    $ F_{13} $ 3008 13 63 177 361 582 594 371 178 79 13 2431
     | Show Table
    DownLoad: CSV

    Table 4.  Comparison of $ \mathtt{nl}_k $ of 6-variable WAPB constructions

    WPB/ WAPB Boolean functions $ \mathtt{nl}_2 $ $ \mathtt{nl}_3 $ $ \mathtt{nl}_4 $
    Upper Bound [1] 5 7 5
    [1] 2 4 2
    [20] 2 2 2
    [22,$ f_n $ Equation(8)] 1 4 1
    [9] 1 4 1
    $ F_n $ 3 4 3
     | Show Table
    DownLoad: CSV

    Table 5.  Comparison of $ \mathtt{nl}_k $ of 7-variable WAPB constructions

    WPB/WAPB Boolean functions $ \mathtt{nl}_2 $ $ \mathtt{nl}_3 $ $ \mathtt{nl}_4 $ $ \mathtt{nl}_5 $
    Upper Bound [1] 8 14 14 8
    [22,$ f_n $ Equation(8)] 1 5 5 1
    [9] 1 5 5 1
    $ F_n $ 5 11 7 5
     | Show Table
    DownLoad: CSV

    Table 6.  Comparison of $ \mathtt{nl}_k $ of 8-variable WPB constructions

    WPB/ WAPB functions $ \mathtt{nl}_2 $ $ \mathtt{nl}_3 $ $ \mathtt{nl}_4 $ $ \mathtt{nl}_5 $ $ \mathtt{nl}_6 $
    Upper Bound [1] 11 24 30 24 11
    [1] 2 12 19 12 6
    [12] 6, 9 0, 8, 14, 16, 19, 22, 23, 24, 19, 20, 21, 22 6, 9
    18, 20, 21, 22 25, 26, 27
    [11,$ g_{2^{q+2}} $ Equation(9)] 2 12 19 12 2
    [16,$ f_m $ Equation(13)] 2 0 3 0 2
    [16,$ g_m $ Equation(22)] 2 14 19 14 2
    [17,$ f_m $ Equation(2)] 2 8 8 8 2
    [17,$ f_m $ Equation(3)] 6 8 26 8 6
    [5,Table 1] 5, 3, 2, 2 10, 7, 12, 12 16, 15, 18, 19 12, 11, 12, 12 5, 3, 2, 6
    [5,Table 3] 5 16 20 17 5
    [21,$ g_m $ Equation(11)] 2 12 19 12 6
    [6] 6, 6, 7 19, 14, 15 21, 20, 18 11, 11, 14 3, 6, 6
    $ F_n $ 7 13 14 14 7
     | Show Table
    DownLoad: CSV
  • [1] C. Carlet, P. Méaux and Y. Rotella, Boolean functions with restricted input and their robustness; application to the FLIP cipher, IACR Trans. Symmetric Cryptol., 2017 (2017), 192-227. doi: 10.13154/TOSC.V2017.I3.192-227.
    [2] D. K. Dalai, K. C. Gupta and S. Maitra, Results on algebraic immunity for cryptographically significant Boolean functions, In Progress in Cryptology - INDOCRYPT 2004, 3348 (2004), 92-106. doi: 10.1007/978-3-540-30556-9_9.
    [3] S. Duval, V. Lallemand and Y. Rotella, Cryptanalysis of the FLIP family of stream ciphers, In Advances in Cryptology - CRYPTO 2016, 9814 (2016), 457-475. doi: 10.1007/978-3-662-53018-4_17.
    [4] A. Gini and P. Méaux, On the weightwise nonlinearity of weightwise perfectly balanced functions, Discrete Applied Mathematics, 322 (2022), 320-341.  doi: 10.1016/J.DAM.2022.08.017.
    [5] A. Gini and P. Méaux, Weightwise almost perfectly balanced functions: Secondary constructions for all n and better weightwise nonlinearities, In Progress in Cryptology - INDOCRYPT 2022, 13774 (2022), 492-514. doi: 10.1007/978-3-031-22912-1_22.
    [6] A. Gini and P. Méaux, On the algebraic immunity of weightwise perfectly balanced functions, In Progress in Cryptology - LATINCRYPT 2023, 14168 (2023), 3-23. doi: 10.1007/978-3-031-44469-2_1.
    [7] A. Gini and P. Méaux, Weightwise perfectly balanced functions and nonlinearity, In Codes, Cryptology and Information Security - C2SI 2023, 13874 (2023), 338-359. doi: 10.1007/978-3-031-33017-9_21.
    [8] H. W. Gould, Combinatorial Identities: A Standardized Set of Tables Listing 500 Binomial Coefficient Summations, Gould, 1972.
    [9] X. Guo and S. Su, Construction of weightwise almost perfectly balanced Boolean functions on an arbitrary number of variables, Discrete Applied Mathematics, 307 (2022), 102-114.  doi: 10.1016/J.DAM.2021.10.011.
    [10] X.-D. Hou, On the norm and covering radius of the first-order Reed-Muller codes, IEEE Transactions on Information Theory, 43 (1997), 1025-1027.  doi: 10.1109/18.568715.
    [11] J. Li and S. Su, Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity, Discrete Applied Mathematics, 279 (2020), 218-227.  doi: 10.1016/j.dam.2020.01.020.
    [12] J. Liu and S. Mesnager, Weightwise perfectly balanced functions with high weightwise nonlinearity profile, Designs, Codes and Cryptography, 87 (2019), 1797-1813.  doi: 10.1007/S10623-018-0579-X.
    [13] É. Lucas, Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques suivant un module premier, Bull. Soc. Math. France, 6 (1878), 49-54.  doi: 10.24033/bsmf.127.
    [14] P. Méaux, A. Journault, F.-X. Standaert and C. Carlet, Towards stream ciphers for efficient FHE with low-noise ciphertexts, In Advances in Cryptology - EUROCRYPT 2016, 9665 (2016), 311-343. doi: 10.1007/978-3-662-49890-3_13.
    [15] W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of boolean functions, In Advances in Cryptology - EUROCRYPT 2004, 3027 (2004), 474-491. doi: 10.1007/978-3-540-24676-3_28.
    [16] S. Mesnager and S. Su, On constructions of weightwise perfectly balanced Boolean functions, Cryptography and Communications, 13 (2021), 951-979.  doi: 10.1007/S12095-021-00481-3.
    [17] S. Mesnager, S. Su and J. Li, On concrete constructions of weightwise perfectly balanced functions with optimal algebraic immunity and high weightwise nonlinearity, In The 6th International Workshop on Boolean Functions and Applications, 2021.
    [18] S. MesnagerZ. Zhou and C. Ding, On the nonlinearity of Boolean functions with restricted input, Cryptography and Communications, 11 (2019), 63-76.  doi: 10.1007/s12095-018-0293-6.
    [19] S. Su, The lower bound of the weightwise nonlinearity profile of a class of weightwise perfectly balanced functions, Discrete Applied Mathematics, 297 (2021), 60-70.  doi: 10.1016/J.DAM.2021.02.033.
    [20] D. Tang and J. Liu, A family of weightwise (almost) perfectly balanced Boolean functions with optimal algebraic immunity, Cryptography and Communications, 11 (2019), 1185-1197.  doi: 10.1007/s12095-019-00374-6.
    [21] R. Zhang and S. Su, A new construction of weightwise perfectly balanced Boolean functions, Advances in Mathematics of Communications, 17 (2023), 757-770. 
    [22] L. Zhu and S. Su, A systematic method of constructing weightwise almost perfectly balanced Boolean functions on an arbitrary number of variables, Discrete Applied Mathematics, 314 (2022), 181-190.  doi: 10.1016/j.dam.2022.02.017.
  • 加载中

Tables(6)

SHARE

Article Metrics

HTML views(1005) PDF downloads(203) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return