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

On the exponents of APN power functions and Sidon sets, sum-free sets, and Dickson polynomials

  • * Corresponding author: Stjepan Picek

    * Corresponding author: Stjepan Picek

The research of the first author is partially supported by the Trond Mohn Foundation

Abstract / Introduction Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by
  • We derive necessary conditions related to the notions, in additive combinatorics, of Sidon sets and sum-free sets, on those exponents $ d\in {\mathbb Z}/(2^n-1){\mathbb Z} $, which are such that $ F(x) = x^d $ is an APN function over $ {\mathbb F}_{2^n} $ (which is an important cryptographic property). We study to what extent these new conditions may speed up the search for new APN exponents $ d $. We summarize all the necessary conditions that an exponent must satisfy for having a chance of being an APN, including the new conditions presented in this work. Next, we give results up to $ n = 48 $, providing the number of exponents satisfying all the conditions for a function to be APN.

    We also show a new connection between APN exponents and Dickson polynomials: $ F(x) = x^d $ is APN if and only if the reciprocal polynomial of the Dickson polynomial of index $ d $ is an injective function from $ \{y\in {\Bbb F}_{2^n}^*; tr_n(y) = 0\} $ to $ {\Bbb F}_{2^n}\setminus \{1\} $. This also leads to a new and simple connection between Reversed Dickson polynomials and reciprocals of Dickson polynomials in characteristic 2 (which generalizes to every characteristic thanks to a small modification): the squared Reversed Dickson polynomial of some index and the reciprocal of the Dickson polynomial of the same index are equal.

    Mathematics Subject Classification: Primary: 11T71, 43A46; Secondary: 12E20.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Known APN exponents on $ {\Bbb F}_{2^n} $ up to equivalence and inversion.

    Functions Exponents $ d $ Conditions
    Gold $ 2^i+1 $ $ \gcd(i,n)=1 $
    Kasami $ 2^{2i}-2^i+1 $ $ \gcd(i,n)=1 $
    Welch $ 2^t +3 $ $ n=2t+1 $
    Niho $ 2^t+2^\frac{t}{2}-1 $, $ t $ even $ n=2t+1 $
    $ 2^t+2^\frac{3t+1}{2}-1 $, $ t $ odd
    Inverse $ 2^{2t}-1 $ $ n=2t+1 $
    Dobbertin $ 2^{4t}+2^{3t}+2^{2t}+2^{t}-1 $ $ n=5t $
     | Show Table
    DownLoad: CSV

    Table 2.  $ \gcd(d-2^j,2^n-1) = 1 $ for every $ j = 0,\dots ,n-1 $. Note that for Gold and Kasami exponents, we use the notation $ (n;i) $ to show all the values $ i $ such that $ \gcd(i,n) = 1 $ for a specific $ n $ that result in the APN exponent $ d $ fulfilling the condition $ \gcd(d-2^j,2^n-1) = 1 $ for every $ j = 0,\dots ,n-1 $

    Class name Value
    $ (n;i) \ such \ that \, i\leq n/2 $
    Gold $ (3;1), (5;1,2), (6;1), (7;1,2,3), (9;1,2,4), (11;2,4,5) $
    $ (13;1,2,3,4,5,6), (14;1,3,5), (15;1,2,4,7), (17;1,2,3,4,5,6,7,8), $
    $ (19;1,2,3,4,5,6,7,8,9), (21;1,2,4,5,8,10), (22;5,7,9), $
    $ (23;2,5,7,8,9,10), (25;1,2,3,4,6,7,8,9,11,12), (26;1,3,5,7,9,11) $
    $ (27;1,2,4,5,7,8,10,11,13), (29;1,2,3,4,5,6,7,8,9,10,11,12,14) $
    $ (31;1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) $
    Kasami $ (3;1), (5;1,2), (6;1), (7;1,2,3), (9;1,2,4), (11;3,4), (13;1,2,3,4,5,6) $
    $ (14;1,3), (15;1,2,4,7), (17;1,2,3,4,5,6,7,8), (19;1,2,3,4,5,6,7,8,9), $
    $ (21;1,4,5,8,10), (22;3,7), (23;2,3,6,8,9,11), (25;1,2,3,4,6,7,8,9,11,12), $
    $ (26;1,3,5,7,9,11), (27;1,2,4,5,7,8,10,11,13), $
    $ (29;1,2,3,5,6,7,8,9,10,11,12,13,14), $
    $ (31;1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) $
    $ n $
    Welch $ 3, 5, 7, 9, 13, 15, 17, 19, 23, 25, 27, 31 $
    Niho $ 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 $
    Dobbertin $ 5, 15, 25 $
    Inverse $ 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 $
     | Show Table
    DownLoad: CSV

    Table 3.  Divisors of $ 2^n-1 $ which are Sidon-sum-free, part I

    n Specification Values
    3 S/SF/SSF 1
    4 S 1, 3, 5
    SF 1, 5
    SSF 1, 5
    5 S/SF/SSF 1
    6 S 1, 3, 9
    SF 1
    SSF 1
    7 S/SF/SSF 1
    8 S 1, 3, 5, 17
    SF 1, 5, 17
    SSF 1, 5, 17
    9 S/SF/SSF 1
    10 S 1, 3, 11, 33
    SF 1, 11
    SSF 1, 11
    11 S 1, 23
    SF 1, 23, 89
    SSF 1, 23
    12 S 1, 3, 5, 9, 13, 39, 65
    SF 1, 5, 13, 65
    SSF 1, 5, 13, 65
    13 S/SF/SSF 1
    14 S 1, 3, 43,129
    SF 1, 43
    SSF 1, 43
    15 S 1,151
    SF 1,151
    SSF 1,151
    16 S 1, 3, 5, 17,257
    SF 1, 5, 17,257, 1 285
    SSF 1, 5, 17,257
    17 S/SF/SSF 1
    18 S 1, 3, 9, 19, 27, 57,171,513
    SF 1, 19
    SSF 1, 19
     | Show Table
    DownLoad: CSV

    Table 4.  Divisors of $ 2^n-1 $ which are Sidon-sum-free, part Ⅱ

    n Specification Values
    19 S/SF/SSF 1
    20 S 1, 3, 5, 11, 25, 33, 41, 55,123,205,275, 1 025
    SF 1, 5, 11, 25, 41, 55,205,275,451, 1 025, 2 255,
    SSF 1, 5, 11, 25, 41, 55,205,275, 1 025
    21 S 1,337
    SF 1,337
    SSF 1,337
    22 S 1, 3, 23, 69,683, 2 049
    SF 1, 23, 89,683, 15 709
    SSF 1, 23,683
    23 S 1, 47
    SF 1, 47
    SSF 1, 47
    24 S 1, 3, 5, 9, 13, 17, 39, 65,221,241,723, 1 205, 4 097
    SF 1, 5, 13, 17, 65,221,241, 1 205, 4 097
    SSF 1, 5, 13, 17, 65,221,241, 1 205, 4 097
    25 S 1,601, 1 801
    SF 1,601, 1 801
    SSF 1,601, 1801
    26 S 1, 3, 2 731, 8 193
    SF 1, 2 731
    SSF 1, 2 731
    27 S/SF/SSF 1
    28 S 1, 3, 5, 29, 43, 87,113,129,145,215,339,565, 1 247, 3 277, 16 385
    SF 1, 5, 29, 43,113,145,215,565, 1 247, 3 277, 4 859, 6 235, 16 385, 24 295
    SSF 1, 5, 29, 43,113,145,215,565, 1 247, 3 277, 16 385
    29 S 1,233, 1 103, 2 089
    SF 1,233, 1 103, 2 089,256 999
    SSF 1,233, 1 103, 2 089
    30 S 1, 3, 9, 11, 33, 99,151,331,453,993, 1 359, 1 661, 2 979,
    3 641, 4 983, 10 923, 32 769
    SF 1, 11,151,331, 1 661, 3 641
    SSF 1, 11,151,331, 1 661, 3 641
    31 S/SF/SSF 1
     | Show Table
    DownLoad: CSV

    Table 5.  $ 32 \leq n \leq 48 $. Number of possibly new APN exponents, the total number of values to consider for a certain $ n $ equals $ 2^n-2 $. $ Cyclotomic \ rep. $ denotes the number of possible APN exponents after keeping only a single representative of a cyclotomic class. $ Subfield $ denotes the number of possible APN exponents after removing values $ d $ such that $ \gcd(d,2^r-1) $ is not an APN exponent in $ \Bbb F_{2^r} $. $ SSF $ denotes the number of possible APN exponents after removing values $ d $ such that (1) $ \gcd(d-2^j, 2^n-1) $ are not SSF values and (2) there exists a divisor $ \lambda $ of $ 2^n-1 $ such that $ {\lambda+1\choose 2}> 2^n-1 $ and there exists $ j = 1,\dots ,n-1 $ such that $ \lambda $ divides $ d-2^j $

    n $ \gcd(d, 2^n-1) $ Not known APN Cyclotomic rep. Subfield SSF
    32 1 073 741 824 1 073 741 344 33 554 417 229 361 229 328
    33 6 963 536 448 6 963 535 029 105 508 114 6 893 976 6 893 596
    34 5 726 448 300 5 726 447 790 168 424 935 764 560 764 560
    35 32 524 632 000 32 524 630 145 464 637 581 236620975 236 620 012
    36 8 707 129 344 8 707 128 948 241 864 693 58 309 58 279
    37 136 822 635 072 136 822 632 297 1 848 954 492 1 848 954 492 1 848 954 380
    38 91 625 269 932 91 625 269 286 2 411 191 297 3 407 842 3 407 842
    39 465 193 834 560 465 193 832 571 5 964 023 502 127 800 480 127 759 412
    40 236 851 200 000 236 851 199 360 5 921 279 984 1 480 304 1 480 210
    41 2 198 858 730 832 2 198 858 727 429 26 815 350 336 26 815 350 336 26 815 343 652
    42 809 240 108 544 809 240 108 082 19 267 621 621 140 857 140 849
    43 8 774 777 333 880 8 774 777 330 139 102 032 294 540 102 032 294 540 102 032 289 465
    44 4 417 116 143 616 4 417 116 142 780 100 389 003 245 15 054 317 15 054 285
    45 28 548 223 200 000 28 548 223 197 615 317 202 480 005 2 004 543 425 2 004 537 282
    46 22 957 042 116 160 22 957 042 115 194 499 066 132 939 65 710 726 65 710 708
    47 9 339 802 874 699 9 339 802 872 926 1 449 575 966 170 1 449 575 966 170 1 449 575 962 833
    48 36 528 696 852 480 36 528 696 851 760 761 014 517 745 1 096 689 1 096 684
     | Show Table
    DownLoad: CSV

    Table 6.  $ 3 \leq n \leq 31 $. Number of possibly new APN exponents, the total number of values to consider for a certain $ n $ equals $ 2^n-2 $ as we do not need to consider the values 0 and $ 2^n-1 $. $ Cyclotomic \ rep. $ denotes the number of possible APN exponents after keeping only a single representative of a cyclotomic class. $ Subfield $ denotes the number of possible APN exponents after removing values $ d $ such that $ \gcd(d,2^r-1) $ is not an APN exponent in $ \Bbb F_{2^r} $. $ SSF $ denotes the number of possible APN exponents after removing values $ d $ such that (1) $ \gcd(d-2^j, 2^n-1) $ are not SSF values and (2) there exists a divisor $ \lambda $ of $ 2^n-1 $ such that $ {\lambda+1\choose 2}> 2^n-1 $ and there exists $ j = 1,\dots ,n-1 $ such that $ \lambda $ divides $ d-2^j $

    n $ \gcd(d, 2^n-1) $ Not known APN Cyclotomic rep. Subfield SSF
    3 6 3 1 1 0
    4 4 0 0 0 0
    5 30 5 1 1 0
    6 12 6 1 0 0
    7 126 49 4 4 3
    8 64 40 5 5 4
    9 432 315 19 6 4
    10 300 260 26 21 21
    11 1 936 1 683 78 78 66
    12 576 540 45 21 21
    13 8 190 7 839 302 302 301
    14 5 292 5 222 373 226 226
    15 27 000 26 685 893 365 365
    16 16 384 16 272 1 017 377 370
    17 131 070 130 475 3 838 3 838 3 837
    18 46 656 46 566 2 587 697 697
    19 524 286 523 545 13 778 13 778 13 777
    20 240 000 239 840 11 992 1 592 1 512
    21 1 778 112 1 777 545 42 326 12 923 12 923
    22 1 320 352 1 320 154 60 007 7 834 7 824
    23 8 210 080 8 208 999 178 458 178 458 178 434
    24 2 211 840 2 211 672 92 153 2 153 2 135
    25 32 400 000 32 398 875 647 981 539 979 539 966
    26 22 358 700 22 358 414 859 939 36 844 36 844
    27 113 467 392 113 466 339 2 101 232 569 069 569 010
    28 66 382 848 66 382 540 2 370 805 31 349 31 127
    29 533 826 432 533 824 721 9 203 878 9 203 878 9 202 166
    30 178 200 000 178 199 760 5 939 992 11 212 11 212
    31 2 147 483 646 2 147 481 693 34 636 802 34 636 802 34 636 801
     | Show Table
    DownLoad: CSV
  • [1] L. Babai and V. T. Sós, Sidon sets in groups and induced subgraphs of cayley graphs, European J. Combin., 6 (1985), 101-114.  doi: 10.1016/S0195-6698(85)80001-9.
    [2] T. Beth and C. Ding, On almost perfect nonlinear permutations, Advances in Cryptology–EUROCRYPT '93 (Lofthus, 1993), 765 (1993), 65-76.  doi: 10.1007/3-540-48285-7_7.
    [3] C. CarletBoolean Functions for Cryptography and Coding Theory, Cambridge University Press, 2021.  doi: 10.1017/9781108606806.
    [4] C. Carlet and S. Mesnager, On those multiplicative subgroups of ${\mathbb F}_{2^n}^*$ which are Sidon sets and/or sum-free sets, Journal of Algebraic Combinatorics, 2020.
    [5] S. D. Cohen and R. W. Matthews, A class of exceptional polynomials, Trans. Amer. Math. Soc., 345 (1994), 897-909.  doi: 10.1090/S0002-9947-1994-1272675-0.
    [6] B. Green and I. Z. Ruzsa, Sum-free sets in abelian groups, Isr. J. Math., 147 (2005), 157-188.  doi: 10.1007/BF02785363.
    [7] X. Hou, Private communication, June 2017.
    [8] X. HouG. L. MullenJ. A. Sellers and J. Yucas, Reversed Dickson polynomials over finite fields, Finite Fields Appl., 15 (2009), 748-773.  doi: 10.1016/j.ffa.2009.06.004.
    [9] G. Kyureghyan, Special mappings of finite fields, Finite Fields and Their Applications, Radon Ser. Comput. Appl. Math., 11 (2013), 117-144. 
    [10] K. Nyberg, Differentially uniform mappings for cryptography, Advances in Cryptology–EUROCRYPT'93 (Lofthus, 1993), 765 (1993), 55-64.  doi: 10.1007/3-540-48285-7_6.
    [11] K. Nyberg and L. R. Knudsen, Provable security against differential cryptanalysis, Advances in Cryptology–CRYPTO '92 (Santa Barbara, CA, 1992, 740 (1992), 566-574.  doi: 10.1007/3-540-48071-4_41.
    [12] T. Tao and V. Vu, Sum-free sets in groups: A survey, J. Comb., 8 (2017), 541-552.  doi: 10.4310/JOC.2017.v8.n3.a7.
  • 加载中

Tables(6)

SHARE

Article Metrics

HTML views(3965) PDF downloads(628) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return