Repository navigation
Expand file tree
/
Copy pathbasics.html
More file actions
104 lines (97 loc) · 10.1 KB
/
Copy pathbasics.html
File metadata and controls
104 lines (97 loc) · 10.1 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
103
104
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Boolean Functions: The Basics — Boolean Functions for Cryptography</title>
<meta name="description" content="A worked introduction to cryptographic Boolean functions: truth table, ANF, degree, Walsh–Hadamard transform, nonlinearity, bent functions, autocorrelation and affine equivalence.">
<meta name="author" content="Joanne Fuller">
<link rel="canonical" href="https://booleanfunction.github.io/basics.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 active" href="basics.html" aria-current="page">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">Research</summary><div class="navmenu"><a href="constructions.html">Constructions & search</a><a href="sboxes.html">S-boxes & AES</a><a href="records.html">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>Boolean Functions: The Basics</h1>
<p>This page builds up the main cryptographic measures of a Boolean function step by step, using
one small example throughout: the <strong>majority function</strong> on three inputs, which
outputs 1 when at least two of its inputs are 1. Every number here is computed directly from
the definitions.</p>
<h2>1. Truth table</h2>
<p>A Boolean function of $n$ inputs is a map $f: \{0,1\}^n \to \{0,1\}$. The most direct
description is its <strong>truth table</strong>: the output for each of the $2^n$ inputs. We
number the inputs $x = (x_1, x_2, x_3)$ by $i = x_1 + 2x_2 + 4x_3$. Reading the outputs as bits
$f(0), f(1), \ldots$ (least significant first) gives the hexadecimal form used on this site:
majority is <code>0xe8</code>.</p>
<div class="table-scroll"><table><thead><tr><th class="num">i</th><th>x = (x₁,x₂,x₃)</th><th class="num">f(x)</th><th class="num">ANF coefficient</th></tr></thead><tbody><tr><td class="num">0</td><td>(0,0,0)</td><td class="num">0</td><td class="num">0</td></tr><tr><td class="num">1</td><td>(1,0,0)</td><td class="num">0</td><td class="num">0</td></tr><tr><td class="num">2</td><td>(0,1,0)</td><td class="num">0</td><td class="num">0</td></tr><tr><td class="num">3</td><td>(1,1,0)</td><td class="num">1</td><td class="num">1</td></tr><tr><td class="num">4</td><td>(0,0,1)</td><td class="num">0</td><td class="num">0</td></tr><tr><td class="num">5</td><td>(1,0,1)</td><td class="num">1</td><td class="num">1</td></tr><tr><td class="num">6</td><td>(0,1,1)</td><td class="num">1</td><td class="num">1</td></tr><tr><td class="num">7</td><td>(1,1,1)</td><td class="num">1</td><td class="num">0</td></tr></tbody></table></div>
<p>The <strong>Hamming weight</strong> is the number of 1s: here 4 of 8, so the function is
<strong>balanced</strong> (equally many 0s and 1s), which is essential for most cryptographic uses:
an unbalanced output leaks a statistical bias.</p>
<h2>2. Algebraic normal form and degree</h2>
<p>Every Boolean function can be written uniquely as an XOR of AND-terms, its <strong>algebraic
normal form</strong> (ANF). The coefficients (last column above) come from the truth table by the
binary Möbius transform. For majority:</p>
<p>$$f(x) = x_1x_2 \oplus x_1x_3 \oplus x_2x_3.$$</p>
<p>The <strong>algebraic degree</strong> (or order) is the size of the largest term: here
<strong>2</strong>. Degree 1 functions are <em>affine</em> (linear plus a constant) and offer
no security; higher degree resists algebraic attacks.</p>
<h2>3. Walsh–Hadamard transform</h2>
<p>The Walsh–Hadamard transform measures how strongly $f$ correlates with each linear function
$\omega \cdot x$:</p>
<p>$$\hat F(\omega) = \sum_{x} (-1)^{f(x) \oplus \omega \cdot x}.$$</p>
<p>A value of 0 means no correlation; $\pm 2^n$ means $f$ equals that linear function (or its
complement).</p>
<div class="table-scroll"><table><thead><tr><th>ω</th><th>linear function ω·x</th><th class="num">F̂(ω)</th></tr></thead><tbody><tr><td>(0,0,0)</td><td>$0$</td><td class="num">0</td></tr><tr><td>(1,0,0)</td><td>$x_1$</td><td class="num">4</td></tr><tr><td>(0,1,0)</td><td>$x_2$</td><td class="num">4</td></tr><tr><td>(1,1,0)</td><td>$x_1 \oplus x_2$</td><td class="num">0</td></tr><tr><td>(0,0,1)</td><td>$x_3$</td><td class="num">4</td></tr><tr><td>(1,0,1)</td><td>$x_1 \oplus x_3$</td><td class="num">0</td></tr><tr><td>(0,1,1)</td><td>$x_2 \oplus x_3$</td><td class="num">0</td></tr><tr><td>(1,1,1)</td><td>$x_1 \oplus x_2 \oplus x_3$</td><td class="num">-4</td></tr></tbody></table></div>
<h2>4. Nonlinearity</h2>
<p>The <strong>nonlinearity</strong> is the Hamming distance from $f$ to the nearest affine function,
and it comes straight from the largest Walsh value:</p>
<p>$$\mathrm{NL}(f) = 2^{n-1} - \tfrac12 \max_\omega |\hat F(\omega)| = 4 - \tfrac12 \cdot 4 = 2.$$</p>
<p>High nonlinearity defends against <em>linear cryptanalysis</em>, which exploits correlation with
linear functions. For $n = 3$, 2 is the largest nonlinearity possible, so majority is as good
as a 3-input function gets.</p>
<p>For even $n$ the maximum, $2^{n-1} - 2^{n/2-1}$, is reached by <strong>bent functions</strong>, whose
Walsh values all have the same magnitude $2^{n/2}$. The classic example for $n = 4$ is
$x_1x_2 \oplus x_3x_4$ (<code>0x7888</code>): every $|\hat F(\omega)| = 4$, and its
nonlinearity is 6. Bent functions are never balanced, which is why balanced functions
of high nonlinearity are a central research problem (see <a href="records.html">Records</a>).</p>
<h2>5. Autocorrelation</h2>
<p>The <strong>autocorrelation</strong> measures how $f$ changes when the input is shifted by $s$:</p>
<p>$$\hat r(s) = \sum_x (-1)^{f(x) \oplus f(x \oplus s)}.$$</p>
<div class="table-scroll"><table><thead><tr><th>shift s</th><th class="num">r̂(s)</th></tr></thead><tbody><tr><td>(0,0,0)</td><td class="num">8</td></tr><tr><td>(1,0,0)</td><td class="num">0</td></tr><tr><td>(0,1,0)</td><td class="num">0</td></tr><tr><td>(1,1,0)</td><td class="num">0</td></tr><tr><td>(0,0,1)</td><td class="num">0</td></tr><tr><td>(1,0,1)</td><td class="num">0</td></tr><tr><td>(0,1,1)</td><td class="num">0</td></tr><tr><td>(1,1,1)</td><td class="num">-8</td></tr></tbody></table></div>
<p>$\hat r(0) = 2^n$ always. Large values for $s \ne 0$ indicate predictable behaviour under
input differences, the weakness exploited by <em>differential cryptanalysis</em>. The largest
magnitude over $s \ne 0$ is the <strong>absolute indicator</strong> (the <em>acmax</em> used in this
site's tables); for majority it is 8, the worst possible. Flipping
all three inputs always flips the output ($\hat r(1,1,1) = -8$), a so-called <em>linear
structure</em>. So majority is optimal for nonlinearity but weak here: good functions must balance
several criteria at once, which is what makes their design hard.</p>
<h2>6. Affine equivalence</h2>
<p>Changing variables affinely, adding an affine function, or complementing the output,
$g(x) = f(Dx \oplus a) \oplus b \cdot x \oplus c$, preserves nonlinearity, degree (above 1) and the
absolute Walsh and autocorrelation distributions. So functions fall into <strong>equivalence
classes</strong> that share these properties. For $n = 3$ there are only three classes, and
majority belongs to class 3, the class of maximum nonlinearity. Instead of studying all
$2^{2^n}$ functions, one representative per class suffices: see the
<a href="equivalence-classes.html">equivalence class tables</a>, and
<a href="class-sizes.html">how big each class is</a>.</p>
<p>Note that Hamming weight is <em>not</em> preserved (adding $b \cdot x$ changes it), so a class can
contain both balanced and unbalanced functions.</p>
<h2>Where next</h2>
<ul>
<li><a href="efficient-implementation.html">Efficient Implementation</a>: computing these
transforms fast, with word packing.</li>
<li><a href="connectivity.html">The Theorem of Connectivity</a>: how the classes link
together.</li>
<li><a href="learning.html">Learning</a>: books and courses for going further.</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>