APN functions obtained via polynomial expansion in small dimensions

From Boolean
Revision as of 09:55, 21 September 2021 by Nikolay (talk | contribs)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

The following tables list APN functions obtained via polynomial expansion over GF(2^n) with n = 8,9. The functions are partitioned into classes according to the differential spectra of their orthoderivatives, and a single representatives is given from each class. In all cases, [math]\displaystyle{ \alpha }[/math] is a primitive element of the corresponding finite field. The label in the "Equivalent to" column indicates which known APN instance the given one is equivalent to (in the sense of having the same differential spectrum of the orthoderivative). Labels "SW" refer to Edel & Pott's switching classes; "B" refers to Beierle & Leander's quadratic APN functions; "Y" refers to the quadratic APN matrix method of Yuyin Yu; and "I" refers to the generalized isotopic shifts of Budaghyan et al. The numbers in all cases refer to the functions listed in the corresponding works in order of appearance; e.g. "I 11" refers to the eleventh function for n = 9 listed in the isotopic shift paper.

Note that function 8.7 has a differential spectrum of the orthoderivative distinct from that of all known APN functions, and is therefore completely new.

More details can be found in the thesis "Experimental construction of optimal cryptographic functions by expansion" by Maren Hestad Aleksandersen. The complete experimental data is available here.

ID Representative Equivalent to Orthoderivative diff. spec.
8.1 [math]\displaystyle{ \alpha^{170}x^{192} + \alpha^{85}x^{132} + x^6 + x^3 }[/math] SW 19 [math]\displaystyle{ 0^{37872}, 2^{22788}, 4^{4068}, 6^{492}, 8^{60} }[/math]
8.2 [math]\displaystyle{ x^{66} + \alpha^{85}x^{33} + x^{18} + x^9 + x^3 }[/math] SW 11 [math]\displaystyle{ 0^{38040}, 2^{22461}, 4^{4218}, 6^{513}, 8^{36}, 10^{12} }[/math]
8.3 [math]\displaystyle{ x^{66} + \alpha^{85}x^{33} + \alpha^{17}x^9 + \alpha^{102}x^6 + x^3 }[/math] SW 13 [math]\displaystyle{ 0^{38076}, 2^{22311}, 4^{4374}, 6^{495}, 8^{24} }[/math]
8.4 [math]\displaystyle{ \alpha^{85}x^{132} + \alpha^{85}x^{72} + x^9 + x^6 + x^3 }[/math] SW 12 [math]\displaystyle{ 0^{38160}, 2^{22104}, 4^{4536}, 6^{456}, 8^{24} }[/math]
8.5 [math]\displaystyle{ x^{66} + x^{12} + \alpha^{85}x^6 + x^3 }[/math] SW 6 [math]\displaystyle{ 0^{38160}, 2^{22164}, 4^{4428}, 6^{492}, 8^{36} }[/math]
8.6 [math]\displaystyle{ x^{129} + \alpha^{85}x^{24} + x^{12} + x^9 + x^3 }[/math] SW 8 [math]\displaystyle{ 0^{38184}, 2^{22179}, 4^{4338}, 6^{531}, 8^{48} }[/math]
8.7 [math]\displaystyle{ \alpha^{170}x^{132} + \alpha^{85}x^{66} + \alpha^{85}x^{18} + x^3 }[/math] new [math]\displaystyle{ 0^{38196}, 2^{22008}, 4^{4608}, 6^{456}, 8^{12} }[/math]
8.8 [math]\displaystyle{ \alpha^{85}x^{132} + \alpha^{85}x^{72} + x^{36} + x^{24} + x^3 }[/math] SW 9 [math]\displaystyle{ 0^{38256}, 2^{22116}, 4^{4230}, 6^{648}, 8^{30} }[/math]
8.9 [math]\displaystyle{ \alpha^{85}x^{192} + x^{72} + x^{33} + x^{24} + x^9 + \alpha^{153}x^6 }[/math] SW 17 [math]\displaystyle{ 0^{38388}, 2^{21723}, 4^{4626}, 6^{507}, 8^{36} }[/math]
8.10 [math]\displaystyle{ \alpha^{221}x^{96} + \alpha^{221}x^{33} + x^{12} + x^9 + x^6 + \alpha^{187}*x^3 }[/math] SW 10 [math]\displaystyle{ 0^{38439}, 2^{21618}, 4^{4671}, 6^{528}, 8^{24} }[/math]
8.11 [math]\displaystyle{ \alpha^{238}x^{144} + x^{132} + \alpha^{51}x^{96} + \alpha^{119}x^{48} + x^{33} + x^9 }[/math] SW 16 [math]\displaystyle{ 0^{38457}, 2^{21552}, 4^{4743}, 6^{510}, 8^{18} }[/math]
8.12 [math]\displaystyle{ \alpha^{204}x^{160} + \alpha^{51}x^{48} + \alpha^{102}x^{12} + \alpha^{204}x^{10} + x^9 }[/math] SW 22 [math]\displaystyle{ 0^{38844}, 2^{20974}, 4^{4764}, 6^{654}, 8^{44} }[/math]
8.13 [math]\displaystyle{ \alpha^{160}x^{132} + \alpha^{10}x^{72} + x^{48} + \alpha x^{34} + \alpha^3x^{33} + \alpha^{48}x^{18} + x^{17} + x^3 }[/math] B 31 [math]\displaystyle{ 0^{39150}, 2^{20463}, 4^{4920}, 6^{675}, 8^{54}, 10^{12}, 12^6 }[/math]
8.14 [math]\displaystyle{ x^{144} + \alpha^{85}x^{96} + \alpha^{170}x^{80} + \alpha^{85}x^{65} + \alpha^{85}x^{17} + x^9 + x^5 }[/math] B 12668 [math]\displaystyle{ 0^{39408}, 2^{20072}, 4^{4922}, 6^{798}, 8^{70}, 10^{10} }[/math]
8.15 [math]\displaystyle{ x^{66} + \alpha^{170}x^{40} + x^{18} + \alpha^{85}x^5 + x^3 }[/math] Y 4346 [math]\displaystyle{ 0^{39408}, 2^{20218}, 4^{4692}, 6^{838}, 8^{104}, 10^{12}, 12^8 }[/math]
8.16 [math]\displaystyle{ x^{160} + x^{132} + x^{80} + x^{68} + x^6 + x^3 }[/math] SW 20 [math]\displaystyle{ 0^{39692}, 2^{19752}, 4^{4756}, 6^{978}, 8^{72}, 10^{26}, 12^4 }[/math]


ID Representative Equivalent to Orthoderivative diff. spec.
9.1 [math]\displaystyle{ \alpha^{365}x^{257} + x^{96} + x^{68} + \alpha^{219}x^{33} + x^5 }[/math] I 4 [math]\displaystyle{ 0^{158529}, 2^{80829}, 4^{18144}, 6^{3283}, 8^{469}, 10^{294}, 12^{84} }[/math]
9.2 [math]\displaystyle{ \alpha^{438}x^{129} + x^{66} + \alpha^{219}x^{10} + x^3 }[/math] I 8 [math]\displaystyle{ 0^{159418}, 2^{79275}, 4^{18690}, 6^{3213}, 8^{742}, 10^{252}, 12^{21}, 16^{21} }[/math]
9.3 [math]\displaystyle{ x^{136} + x^{24} + x^{17} + \alpha^{73}x^{10} + x^3 }[/math] I 3 [math]\displaystyle{ 0^{159684}, 2^{78687}, 4^{19089}, 6^{3136}, 8^{777}, 10^{147}, 12^{84}, 14^{28} }[/math]
9.4 [math]\displaystyle{ x^{68} + \alpha^{73}x^{40} + x^{33} + x^5 }[/math] I 10 [math]\displaystyle{ 0^{159684}, 2^{79590}, 4^{17871}, 6^{3283}, 8^{700}, 10^{273}, 12^{147}, 14^{84} }[/math]
9.5 [math]\displaystyle{ \alpha^{73}x^{136} + \alpha^{146}x^{66} + \alpha^{219}x^{10} + x^3 }[/math] I 16 [math]\displaystyle{ 0^{159908}, 2^{79086}, 4^{18081}, 6^{3353}, 8^{721}, 10^{336}, 12^{105}, 14^{21}, 16^{21} }[/math]
9.6 [math]\displaystyle{ x^{264} + \alpha^{73}x^{96} + \alpha^{219}x^{68} + x^5 }[/math] I 11 [math]\displaystyle{ 0^{160020}, 2^{79023}, 4^{17997}, 6^{3213}, 8^{868}, 10^{378}, 12^{133} }[/math]
9.7 [math]\displaystyle{ \alpha^{219}x^{136} + x^{10} + x^3 }[/math] I 12 [math]\displaystyle{ 0^{160657}, 2^{77910}, 4^{18312}, 6^{3360}, 8^{952}, 10^{273}, 12^{147}, 14^{21} }[/math]
9.8 [math]\displaystyle{ x^{192} + x^{66} + x^{17} + \alpha^{73}x^{10} + x^3 }[/math] I 14 [math]\displaystyle{ 0^{162183}, 2^{76482}, 4^{17388}, 6^{3871}, 8^{1162}, 10^{252}, 12^{126}, 14^{126}, 16^{21}, 22^{21} }[/math]
9.9 [math]\displaystyle{ \alpha^{73}x^{192} + x^{136} + \alpha^{365}x^{129} + x^{17} + x^3 }[/math] I 5 [math]\displaystyle{ 0^{162708}, 2^{77175}, 4^{15498}, 6^{4270}, 8^{1260}, 10^{252}, 12^{168}, 14^{84}, 16^{126}, 18^{42}, 22^{42}, 26^7 }[/math]
9.10 [math]\displaystyle{ \alpha^{73}x^{129} + \alpha^{292}x^{66} + x^{10} + x^3 }[/math] I 9 [math]\displaystyle{ 0^{163009}, 2^{75537}, 4^{17283}, 6^{4116}, 8^{1071}, 10^{168}, 12^{231}, 14^{28}, 16^{84}, 18^{63}, 20^{42} }[/math]
9.11 [math]\displaystyle{ x^{80} + \alpha^{146}x^{66} + \alpha^{73}x^{24} + x^{17} }[/math] I 13 [math]\displaystyle{ 0^{163366}, 2^{75117}, 4^{17010}, 6^{4536}, 8^{966}, 10^{252}, 12^{63}, 14^{154}, 16^{63}, 18^{84}, 22^{21} }[/math]
9.12 [math]\displaystyle{ x^{129} + \alpha^{73}x^{66} + x^{17} + x^{10} + \alpha^{365}x^3 }[/math] I 6 [math]\displaystyle{ 0^{163996}, 2^{74802}, 4^{16380}, 6^{4368}, 8^{1449}, 10^{231}, 12^{126}, 14^{84}, 16^{42}, 18^{84}, 20^{42}, 22^{21}, 32^7 }[/math]
9.13 [math]\displaystyle{ \alpha^{73}x^{136} + \alpha^{219}x^{66} + \alpha^{438}x^{10} + x^3 }[/math] I 15 [math]\displaystyle{ 0^{168994}, 2^{68712}, 4^{15141}, 6^{6279}, 8^{1659}, 10^{336}, 12^{21}, 14^{21}, 16^{105}, 18^{147}, 20^{189}, 24^{21}, 26^7 }[/math]
9.14 [math]\displaystyle{ \alpha^{438}x^{129} + x^{66} + \alpha^{219}x^{17} + x^3 }[/math] I 2 [math]\displaystyle{ 0^{169428}, 2^{68040}, 4^{15561}, 6^{6034}, 8^{1533}, 10^{420}, 12^{126}, 14^{21}, 16^{84}, 18^{189}, 20^{126}, 22^{63}, 26^7 }[/math]
9.15 [math]\displaystyle{ \alpha^{365}x^{80} + \alpha^{292}x^{24} + \alpha^{219}x^{17} + x^3 }[/math] I 17 [math]\displaystyle{ 0^{170079}, 2^{66297}, 4^{16737}, 6^{6160}, 8^{1407}, 10^{420}, 12^{21}, 14^{42}, 16^{63}, 18^{210}, 20^{133}, 22^{63} }[/math]
9.16 [math]\displaystyle{ x^{257} + \alpha^{438}x^{68} + \alpha^{219}x^{12} + x^5 }[/math] I 7 [math]\displaystyle{ 0^{171430}, 2^{64617}, 4^{16842}, 6^{5733}, 8^{1932}, 10^{483}, 12^{105}, 14^{21}, 16^{147}, 18^{105}, 20^{154}, 22^{21}, 24^{42} }[/math]
9.17 [math]\displaystyle{ x^{80} + \alpha^{73}x^{66} + x^{17} + \alpha^{73}x^{10} + x^3 }[/math] B 31 [math]\displaystyle{ 0^{160440}, 2^{78834}, 4^{17514}, 6^{3388}, 8^{777}, 10^{483}, 12^{126}, 14^{49}, 16^{21} }[/math]
9.18 [math]\displaystyle{ \alpha^{365}x^{136} + x^{129} + \alpha^{73}x^{80} + x^{24} + x^{17} + x^3 }[/math] B 34 [math]\displaystyle{ 0^{164199}, 2^{76734}, 4^{13524}, 6^{4312}, 8^{2205}, 12^{147}, 16^{294}, 18^{147}, 20^{49}, 22^{21} }[/math]
9.19 [math]\displaystyle{ \alpha^{73}x^{320} + x^{96} + \alpha^{219}x^{68} + x^{40} + x^{33} + x^5 }[/math] B 35 [math]\displaystyle{ 0^{172557}, 2^{68355}, 4^{12201}, 6^{3871}, 8^{1638}, 10^{735}, 12^{1470}, 14^{49}, 16^{147}, 18^{441}, 20^{147}, 42^{21} }[/math]