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

Claude Carlet; Stjepan Picek

doi:10.3934/amc.2021064

Article Contents

2023, Volume 17, Issue 6: 1507-1525. Doi: 10.3934/amc.2021064

This issue Previous Article Aperiodic/periodic complementary sequence pairs over quaternions Next Article Constructions of asymptotically optimal codebooks with respect to Welch bound and Levenshtein bound

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

Claude Carlet^1, and
Stjepan Picek^2, ,

1.
Department of informatics, University of Bergen, Norway and LAGA, University of Paris 8, France
2.
Delft University of Technology, The Netherlands and LAGA, University of Paris 8, France

^* Corresponding author: Stjepan Picek
^* Corresponding author: Stjepan Picek

Received: June 2021

Revised: October 2021

Early access: December 15, 2021

Published online: December 15, 2021

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

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Article Metrics

HTML views(5942) PDF downloads(633) Cited by(0)

[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.

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

Abstract

References

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

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

Abstract

References

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content