Repository navigation
Expand file tree
/
Copy pathefficient-implementation.html
More file actions
85 lines (78 loc) · 6.99 KB
/
Copy pathefficient-implementation.html
File metadata and controls
85 lines (78 loc) · 6.99 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
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Efficient Implementation — Boolean Functions for Cryptography</title>
<meta name="description" content="Word-packing and Walsh–Hadamard/ANF/autocorrelation transform techniques for Boolean function research.">
<meta name="author" content="Joanne Fuller">
<link rel="canonical" href="https://booleanfunction.github.io/efficient-implementation.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">Records & open problems</a><a href="efficient-implementation.html" aria-current="page">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>Efficient Implementation</h1>
<h2>Why implementation matters</h2>
<p>Fundamental to any area of research is the ability to reproduce reported experiments, both
for verification and for advancement. Boolean function research is unusual in how much it
depends on raw computation: classifying functions, searching for good ones and computing
their properties can involve <strong>many billions of steps</strong>. Yet the cryptographic
literature has historically said little about <em>how</em> to implement these computations
efficiently, leaving each researcher to reinvent the machinery.</p>
<p>This page summarises the implementation techniques that made the exhaustive $n = 6$
classification feasible. The guiding principle is to minimise not just the <em>number</em> of
operations but the number of <em>expensive</em> operations — conditionals, multiplication,
division, modular reduction — in favour of cheap bitwise operations (XOR, AND, SHIFT).</p>
<h2>Packing truth tables into words</h2>
<p>The natural representation of a Boolean function is a full array of $2^n$ integers, one per
input. It is simple, but wasteful: a truth table or ANF needs only <strong>one bit</strong>
per entry, so a full integer array uses 32× more memory than necessary.</p>
<p>The alternative packs the output values into the full machine word. A function of $n$
variables then needs an array of</p>
<p>$$N = 2^{n} / 32 = 2^{\,n-5}$$</p>
<p>32-bit words (for $n \ge 5$) — a memory saving of roughly <strong>97%</strong>. Bit $i$ of
the truth table lives at bit $i \bmod 32$ of word $\lfloor i / 32 \rfloor$:</p>
<pre><code>/* set bit i to 1 */ array[i >> 5] |= (1 << (i & 31));
/* get bit i */ ( array[i >> 5] >> (i & 31) ) & 1;</code></pre>
<p>The shift <code>i >> 5</code> replaces a division and <code>i & 31</code> replaces
a modular reduction — both examples of <em>strength reduction</em>. Crucially, packing also
lets many transforms process <strong>32 outputs at once</strong>. Computing a Hamming weight,
for instance, needs only $2^{\,n-5}$ word-level popcounts instead of $2^{n}$ single-bit
lookups.</p>
<h2>Key transforms</h2>
<p>Three transforms underpin almost all property computations. Each was implemented to operate
directly on the packed words, using precomputed lookup tables for the byte-level sub-results.</p>
<h3>Algebraic Normal Form</h3>
<p>The ANF gives the unique multilinear polynomial representation of a function over
$\mathrm{GF}(2)$ (the functions of degree at most $r$ are exactly the Reed–Muller code
$\mathrm{RM}(r,n)$), and from it the <strong>algebraic order</strong> and <strong>algebraic
weight</strong>. The transform is a Möbius transform over the Boolean lattice; with
byte-indexed lookup tables the four bytes of each 32-bit word can be transformed together,
then combined.</p>
<h3>Walsh–Hadamard Transform</h3>
<p>The WHT is the workhorse of nonlinearity analysis: the nonlinearity follows directly from
the maximum absolute Walsh coefficient,</p>
<p>$$\mathrm{NL}(f) = 2^{\,n-1} - \tfrac{1}{2}\,\max_{a}\,\lvert W_f(a)\rvert .$$</p>
<p>A precomputed table of the WHT of every 8-bit sub-function turns the transform into a small
number of table lookups and additions per word.</p>
<h3>Autocorrelation</h3>
<p>By the <strong>Wiener–Khinchin theorem</strong> the autocorrelation is the inverse WHT of
the power spectrum ($W_f^2$). The optimised autocorrelation routine therefore reuses the WHT
implementation directly, computing the squared spectrum and transforming back.</p>
<h2>In the modern library</h2>
<p>These same ideas carry over to 64-bit words, where an $n = 6$ function fits in a single
machine word and the per-function cost roughly halves again. A modern reimplementation of
these transforms — with the packing scheme above — is in active development and validates its
results against the classification data published on this site.</p>
</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>