Repository navigation
Expand file tree
/
Copy pathrecords.html
More file actions
102 lines (95 loc) · 8.33 KB
/
Copy pathrecords.html
File metadata and controls
102 lines (95 loc) · 8.33 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Records: Best-Known Functions — Boolean Functions for Cryptography</title>
<meta name="description" content="Best-known cryptographic Boolean functions by criterion, with first-discovery references.">
<meta name="author" content="Joanne Fuller">
<link rel="canonical" href="https://booleanfunction.github.io/records.html">
<link rel="icon" href="favicon.svg">
<link rel="stylesheet" href="style.css?v=c9669768">
<script>window.MathJax={tex:{inlineMath:[['$','$'],['\\(','\\)']]}};</script>
<script async src="https://cdn.jsdelivr.net/npm/mathjax@3.2.2/es5/tex-mml-chtml.js"></script>
</head>
<body>
<header class="site-head"><a class="masthead-title" href="index.html">Boolean Functions for Cryptography</a><nav class="masthead-nav" aria-label="Main"><a class="navlink" href="index.html">Home</a><a class="navlink" href="basics.html">Basics</a><details class="navgroup"><summary class="navlink">Classes</summary><div class="navmenu"><a href="equivalence-classes.html">Equivalence classes & data</a><a href="class-sizes.html">Class sizes</a><a href="connectivity.html">Connectivity</a></div></details><details class="navgroup"><summary class="navlink active">Research</summary><div class="navmenu"><a href="constructions.html">Constructions & search</a><a href="sboxes.html">S-boxes & AES</a><a href="records.html" aria-current="page">Records & open problems</a><a href="efficient-implementation.html">Efficient implementation</a></div></details><details class="navgroup"><summary class="navlink">Tools</summary><div class="navmenu"><a href="explore.html">Class Graph Explorer</a><a href="analyse.html">Function Analyser</a></div></details><a class="navlink" href="publications.html">Publications</a><a class="navlink" href="learning.html">Learning</a></nav></header>
<script>document.addEventListener('click',function(e){document.querySelectorAll('details.navgroup[open]').forEach(function(d){if(!d.contains(e.target))d.removeAttribute('open');});});document.addEventListener('keydown',function(e){if(e.key==='Escape')document.querySelectorAll('details.navgroup[open]').forEach(function(d){d.removeAttribute('open');});});document.addEventListener('toggle',function(e){var t=e.target;if(t.matches&&t.matches('details.navgroup')&&t.open)document.querySelectorAll('details.navgroup[open]').forEach(function(d){if(d!==t)d.removeAttribute('open');});},true);</script>
<main class="container">
<h1>Records: Best-Known Functions</h1>
<p>Best-known cryptographic Boolean functions for given parameters, with the work that first
reported each result. Organised by <em>objective</em> — because the criteria trade off
(Siegenthaler's bound, the nonlinearity–algebraic-immunity tension, …), "best" is only meaningful
once the optimised property and the fixed constraints are specified.</p>
<div class="callout-note"><p><strong>Work in progress — corrections welcome.</strong> This is a
best-effort community record and may be incomplete or out of date. If you know a stronger result, a
missing entry, or a correction to a first attribution, please
<a href="https://www.linkedin.com/in/joanne-fuller-phd-04955b1a/" rel="me noopener">message me on LinkedIn</a>. Entries without a link cite the publication of record; <strong>★</strong> marks an open
target.</p></div>
<h2>Maximum nonlinearity</h2>
<p>For even $n$ the maximum over all functions is the bent value $2^{n-1}-2^{n/2-1}$. Balanced
functions cannot be bent, so their record is lower.</p>
<div class="table-scroll"><table>
<thead><tr><th class="num">n</th><th>all functions</th><th>balanced</th><th>first reference</th></tr></thead>
<tbody>
<tr><td class="num">4</td><td>6 (bent)</td><td>4</td><td>Rothaus (1976); exhaustive</td></tr>
<tr><td class="num">5</td><td>12</td><td>12</td><td>classical — covering radius of RM(1,5)</td></tr>
<tr><td class="num">6</td><td>28 (bent)</td><td>26</td><td>Rothaus (1976); balanced via the <a href="equivalence-classes.html">n=6 classification</a></td></tr>
<tr><td class="num">7</td><td>56</td><td>56</td><td>classical — covering radius of RM(1,7)</td></tr>
<tr><td class="num">8</td><td>120 (bent)</td><td>116 <span class="res-note">(best known)</span></td><td>Rothaus (1976); balanced: Stănică–Maitra–Clark (2004)</td></tr>
</tbody></table></div>
<p class="muted">Maximum nonlinearity for odd $n \ge 9$ is open (best-known values exceed the
bent-concatenation bound).</p>
<h2>Algebraic immunity</h2>
<p>The maximum possible algebraic immunity is $\lceil n/2 \rceil$ (Meier–Pasalic–Carlet, 2004).
The meaningful record is the best nonlinearity attainable <em>together with</em> optimal AI.</p>
<div class="table-scroll"><table>
<thead><tr><th class="num">n</th><th class="num">optimal AI</th><th>best balanced NL at optimal AI</th><th>status / reference</th></tr></thead>
<tbody>
<tr><td class="num">6</td><td class="num">3</td><td>26</td><td>balanced NL=26, AI=3 attained — <a href="equivalence-classes.html">n=6 classification</a></td></tr>
<tr><td class="num">8</td><td class="num">4</td><td>< 116</td><td><strong>★ OPEN — balanced NL=116 with AI=4 is not known</strong></td></tr>
</tbody></table></div>
<h2>Affine equivalence class counts</h2>
<div class="table-scroll"><table>
<thead><tr><th class="num">n</th><th class="num">affine classes</th><th class="num">with balanced functions</th><th>first reference</th></tr></thead>
<tbody>
<tr><td class="num">3</td><td class="num">3</td><td class="num">—</td><td>exhaustive (classical)</td></tr>
<tr><td class="num">4</td><td class="num">8</td><td class="num">—</td><td>exhaustive (classical)</td></tr>
<tr><td class="num">5</td><td class="num">48</td><td class="num">—</td><td>Berlekamp–Welch (1972)</td></tr>
<tr><td class="num">6</td><td class="num">150,357</td><td class="num">74,542</td><td><a href="https://www.ams.org/journals/mcom/1991-57-195/S0025-5718-1991-1079017-5/">Maiorana (1991)</a>; Fuller (2003); Braeken et al. (2005)</td></tr>
</tbody></table></div>
<p class="muted">A complete affine-equivalence classification for $n = 7$ is open.</p>
<h2>Bent functions (even $n$)</h2>
<div class="table-scroll"><table>
<thead><tr><th class="num">n</th><th class="num">bent NL</th><th>number of bent functions</th><th>reference</th></tr></thead>
<tbody>
<tr><td class="num">4</td><td class="num">6</td><td>896</td><td>classical</td></tr>
<tr><td class="num">6</td><td class="num">28</td><td>5,425,430,528</td><td>classical; 4 affine classes (<a href="equivalence-classes.html">this site</a>)</td></tr>
<tr><td class="num">8</td><td class="num">120</td><td>enumerated</td><td>Langevin & Leander (2008)</td></tr>
</tbody></table></div>
<h2>Second-order nonlinearity (covering radius of RM(2,n))</h2>
<div class="table-scroll"><table>
<thead><tr><th class="num">n</th><th class="num">max NL₂</th><th>reference</th></tr></thead>
<tbody>
<tr><td class="num">6</td><td class="num">18</td><td>Schatz (1981)</td></tr>
<tr><td class="num">7</td><td class="num">40</td><td><a href="https://arxiv.org/abs/1809.04864">Gao et al. (2019)</a></td></tr>
</tbody></table></div>
<h2>Multiplicative complexity ($n = 6$)</h2>
<p>Every 6-variable Boolean function can be implemented with at most <strong>6 AND gates</strong>;
the multiplicative complexity of all 150,357 affine classes is known
(<a href="https://eprint.iacr.org/2018/002">Çalık, Sönmez Türan & Peralta, 2018</a>).</p>
<h2>★ Open targets</h2>
<ul>
<li><strong>$n = 8$, balanced, NL = 116 <em>and</em> AI = 4.</strong> NL=116 balanced functions are
known (Stănică–Maitra–Clark, 2004) and AI = 4 is the optimum, but no function is known to achieve
both.</li>
<li>Maximum nonlinearity of functions for $n \ge 9$.</li>
<li>A complete affine-equivalence classification for $n = 7$.</li>
</ul>
</main>
<footer class="site-footer"><div class="foot-inner">
<span>© Dr Joanne Fuller · <a href="https://orcid.org/0000-0002-5221-3505" rel="me noopener">ORCID</a> · <a href="https://scholar.google.com/citations?user=aCp_g7IAAAAJ&hl=en" rel="me noopener">Google Scholar</a> · <a href="https://www.linkedin.com/in/joanne-fuller-phd-04955b1a/" rel="me noopener">LinkedIn</a></span>
<span>Content and data licensed <a href="https://creativecommons.org/licenses/by/4.0/" rel="license noopener">CC BY 4.0</a>: please <a href="equivalence-classes.html#cite">cite</a> when reusing</span>
</div></footer>
</body>
</html>