APN functions obtained via polynomial expansion in small dimensions: Difference between revisions

From Boolean
Jump to navigation Jump to search
No edit summary
No edit summary
 
(2 intermediate revisions by 2 users not shown)
Line 3: Line 3:
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.
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.
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 [https://universityofbergen-my.sharepoint.com/:u:/g/personal/nikolay_kaleyski_uib_no/EXx9rPgHdE1EhcyitEkbJ00Bs8PEhRMk3Ewu7m4XH3zjgA?e=x3gRQV available here]. The same data sorted by the differential spectrum of the orthoderivative is [https://universityofbergen-my.sharepoint.com/:f:/g/personal/nadiia_ichanska_uib_no/EvdnMAKGTOxEueB9OHodGTYBka22hklkydwXwUzPGTNlZw?e=zFfJBq available here].


<table>
<table>
Line 67: Line 67:
<tr>
<tr>
<td>8.10</td>
<td>8.10</td>
<td><math>\alpha^{221}x^{96} + \alpha^{221}x^{33} + x^{12} + x^9 + x^6 + \alpha^{187}*x^3</math></td>
<td><math>\alpha^{221}x^{96} + \alpha^{221}x^{33} + x^{12} + x^9 + x^6 + \alpha^{187}x^3</math></td>
<td>SW 10</td>
<td>SW 10</td>
<td><math>0^{38439}, 2^{21618}, 4^{4671}, 6^{528}, 8^{24}</math></td>
<td><math>0^{38439}, 2^{21618}, 4^{4671}, 6^{528}, 8^{24}</math></td>

Latest revision as of 16:14, 19 August 2022

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. The same data sorted by the differential spectrum of the orthoderivative 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]