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

From Boolean Functions
Jump to: navigation, search
(Created page with "<table> <tr> <th>ID</th> <th>Representative</th> <th>Equivalent to</th> <th>Orthoderivative diff. spec.</th> </tr> <tr> <td>8.1</td> <td><math>\alpha^{170}x^{192} + \alpha^{85...")
 
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
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>\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 [https://universityofbergen-my.sharepoint.com/:u:/g/personal/nikolay_kaleyski_uib_no/EXx9rPgHdE1EhcyitEkbJ00Bs8PEhRMk3Ewu7m4XH3zjgA?e=x3gRQV available here].
 +
 
<table>
 
<table>
 
<tr>
 
<tr>
Line 100: Line 106:
 
<td>SW 20</td>
 
<td>SW 20</td>
 
<td><math>0^{39692}, 2^{19752}, 4^{4756}, 6^{978}, 8^{72}, 10^{26}, 12^4</math></td>
 
<td><math>0^{39692}, 2^{19752}, 4^{4756}, 6^{978}, 8^{72}, 10^{26}, 12^4</math></td>
 +
</tr>
 +
</table>
 +
 +
<br />
 +
 +
<table>
 +
<th>ID</th>
 +
<th>Representative</th>
 +
<th>Equivalent to</th>
 +
<th>Orthoderivative diff. spec.</th>
 +
</tr>
 +
<tr>
 +
<td>9.1</td>
 +
<td><math>\alpha^{365}x^{257} + x^{96} + x^{68} + \alpha^{219}x^{33} + x^5</math></td>
 +
<td>I 4</td>
 +
<td><math>0^{158529}, 2^{80829}, 4^{18144}, 6^{3283}, 8^{469}, 10^{294}, 12^{84}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.2</td>
 +
<td><math>\alpha^{438}x^{129} + x^{66} + \alpha^{219}x^{10} + x^3</math></td>
 +
<td>I 8</td>
 +
<td><math>0^{159418}, 2^{79275}, 4^{18690}, 6^{3213}, 8^{742}, 10^{252}, 12^{21}, 16^{21}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.3</td>
 +
<td><math>x^{136} + x^{24} + x^{17} + \alpha^{73}x^{10} + x^3</math></td>
 +
<td>I 3</td>
 +
<td><math>0^{159684}, 2^{78687}, 4^{19089}, 6^{3136}, 8^{777}, 10^{147}, 12^{84}, 14^{28}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.4</td>
 +
<td><math>x^{68} + \alpha^{73}x^{40} + x^{33} + x^5</math></td>
 +
<td>I 10</td>
 +
<td><math>0^{159684}, 2^{79590}, 4^{17871}, 6^{3283}, 8^{700}, 10^{273}, 12^{147}, 14^{84}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.5</td>
 +
<td><math>\alpha^{73}x^{136} + \alpha^{146}x^{66} + \alpha^{219}x^{10} + x^3</math></td>
 +
<td>I 16</td>
 +
<td><math>0^{159908}, 2^{79086}, 4^{18081}, 6^{3353}, 8^{721}, 10^{336}, 12^{105}, 14^{21}, 16^{21}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.6</td>
 +
<td><math>x^{264} + \alpha^{73}x^{96} + \alpha^{219}x^{68} + x^5</math></td>
 +
<td>I 11</td>
 +
<td><math>0^{160020}, 2^{79023}, 4^{17997}, 6^{3213}, 8^{868}, 10^{378}, 12^{133}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.7</td>
 +
<td><math>\alpha^{219}x^{136} + x^{10} + x^3</math></td>
 +
<td>I 12</td>
 +
<td><math>0^{160657}, 2^{77910}, 4^{18312}, 6^{3360}, 8^{952}, 10^{273}, 12^{147}, 14^{21}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.8</td>
 +
<td><math>x^{192} + x^{66} + x^{17} + \alpha^{73}x^{10} + x^3</math></td>
 +
<td>I 14</td>
 +
<td><math>0^{162183}, 2^{76482}, 4^{17388}, 6^{3871}, 8^{1162}, 10^{252}, 12^{126}, 14^{126}, 16^{21}, 22^{21}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.9</td>
 +
<td><math>\alpha^{73}x^{192} + x^{136} + \alpha^{365}x^{129} + x^{17} + x^3</math></td>
 +
<td>I 5</td>
 +
<td><math>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></td>
 +
</tr>
 +
<tr>
 +
<td>9.10</td>
 +
<td><math>\alpha^{73}x^{129} + \alpha^{292}x^{66} + x^{10} + x^3</math></td>
 +
<td>I 9</td>
 +
<td><math>0^{163009}, 2^{75537}, 4^{17283}, 6^{4116}, 8^{1071}, 10^{168}, 12^{231}, 14^{28}, 16^{84}, 18^{63}, 20^{42}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.11</td>
 +
<td><math>x^{80} + \alpha^{146}x^{66} + \alpha^{73}x^{24} + x^{17}</math></td>
 +
<td>I 13</td>
 +
<td><math>0^{163366}, 2^{75117}, 4^{17010}, 6^{4536}, 8^{966}, 10^{252}, 12^{63}, 14^{154}, 16^{63}, 18^{84}, 22^{21}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.12</td>
 +
<td><math>x^{129} + \alpha^{73}x^{66} + x^{17} + x^{10} + \alpha^{365}x^3</math></td>
 +
<td>I 6</td>
 +
<td><math>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></td>
 +
</tr>
 +
<tr>
 +
<td>9.13</td>
 +
<td><math>\alpha^{73}x^{136} + \alpha^{219}x^{66} + \alpha^{438}x^{10} + x^3</math></td>
 +
<td>I 15</td>
 +
<td><math>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></td>
 +
</tr>
 +
<tr>
 +
<td>9.14</td>
 +
<td><math>\alpha^{438}x^{129} + x^{66} + \alpha^{219}x^{17} + x^3</math></td>
 +
<td>I 2</td>
 +
<td><math>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></td>
 +
</tr>
 +
<tr>
 +
<td>9.15</td>
 +
<td><math>\alpha^{365}x^{80} + \alpha^{292}x^{24} + \alpha^{219}x^{17} + x^3</math></td>
 +
<td>I 17</td>
 +
<td><math>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></td>
 +
</tr>
 +
<tr>
 +
<td>9.16</td>
 +
<td><math>x^{257} + \alpha^{438}x^{68} + \alpha^{219}x^{12} + x^5</math></td>
 +
<td>I 7</td>
 +
<td><math>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></td>
 +
</tr>
 +
<tr>
 +
<td>9.17</td>
 +
<td><math>x^{80} + \alpha^{73}x^{66} + x^{17} + \alpha^{73}x^{10} + x^3</math></td>
 +
<td>B 31</td>
 +
<td><math>0^{160440}, 2^{78834}, 4^{17514}, 6^{3388}, 8^{777}, 10^{483}, 12^{126}, 14^{49}, 16^{21}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.18</td>
 +
<td><math>\alpha^{365}x^{136} + x^{129} + \alpha^{73}x^{80} + x^{24} + x^{17} + x^3</math></td>
 +
<td>B 34</td>
 +
<td><math>0^{164199}, 2^{76734}, 4^{13524}, 6^{4312}, 8^{2205}, 12^{147}, 16^{294}, 18^{147}, 20^{49}, 22^{21}</math></td>
 +
</tr>
 +
<tr>
 +
<td>9.19</td>
 +
<td><math>\alpha^{73}x^{320} + x^{96} + \alpha^{219}x^{68} + x^{40} + x^{33} + x^5</math></td>
 +
<td>B 35</td>
 +
<td><math>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></td>
 
</tr>
 
</tr>
 
</table>
 
</table>

Latest revision as of 10:55, 21 September 2021

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, 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 SW 19
8.2 SW 11
8.3 SW 13
8.4 SW 12
8.5 SW 6
8.6 SW 8
8.7 new
8.8 SW 9
8.9 SW 17
8.10 SW 10
8.11 SW 16
8.12 SW 22
8.13 B 31
8.14 B 12668
8.15 Y 4346
8.16 SW 20


ID Representative Equivalent to Orthoderivative diff. spec.
9.1 I 4
9.2 I 8
9.3 I 3
9.4 I 10
9.5 I 16
9.6 I 11
9.7 I 12
9.8 I 14
9.9 I 5
9.10 I 9
9.11 I 13
9.12 I 6
9.13 I 15
9.14 I 2
9.15 I 17
9.16 I 7
9.17 B 31
9.18 B 34
9.19 B 35