Functions | Exponents |
Conditions |
Gold | ||
Kasami | ||
Welch | ||
Niho | ||
Inverse | ||
Dobbertin |
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.
Citation: |
Table 1.
Known APN exponents on
Functions | Exponents |
Conditions |
Gold | ||
Kasami | ||
Welch | ||
Niho | ||
Inverse | ||
Dobbertin |
Table 2.
Class name | Value |
Gold | |
Kasami | |
Welch | |
Niho | |
Dobbertin | |
Inverse |
Table 3.
Divisors of
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 |
Table 4.
Divisors of
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 |
Table 5.
n | 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 |
Table 6.
n | 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 |
[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. Carlet, Boolean 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. Hou, G. L. Mullen, J. 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.![]() ![]() ![]() |