See CiteSeerX — On the Supports of the Walsh Transforms of Boolean Functions

Lets understand better algebraic normal form, as Turing thought of it in a world of the “enigma” basis (vs binary). First, lets see carlet and co characterize normal form:


We recall from the work on DES sbox analysis how the value of the WHT, for a given linear combination projection  applied to the output bits of the sbox, how the value developed into a correlation constraint, akin to the Tunny-era proportional bulge.

Now, lets set the scene by recalling just how the Tunny alphabet was organized (and why). Lets recall, and the form of the table (column 1 is a 16 ones followed by 16 zeros, column 2 is a set of 8 runs, column 5 is a set of 4 runs, etc. We can look at any one column as a subgroup (e.g. H1 from Turing), which allows cosets to be developed from “that column”. If looking at the coset of the first column associated with the zero value run, one has specified a more limited search (to the bottom half of the table). This is either the 16-count or the 2-count of Colossus era (im not sure which!) Now, to the cryptographers eye one looks for symmetry (which for a couple of rows, in what is probably the 2-count, comes down to seeing what the difference is between the two numbers, whether it has the right sign/magnitude for its placement on the vertical, for the non-linear detector to be indicating that one has the right wheel setting).

Now we can look again the form of the ANF. The multi-variable function f(x, …) is a superposition of character functions, each with an amplitude. Look at each character function as a row in the classic truth table for a binary boolean function such as “and”. Next, swap from thinking about binary and qubits to: qudits and…Friedman squares. The later are, of course generated by the stepping action of an enigma-style rotor. Think of the Friedman square and its many rows as a kind of truth table, where each row was known as a “rod”.

In the  stepping world, the plaintext values of x input to f() are conjugated (in the amount of the amount of stepping that the next wheel has undertake, relative to the previous wheel/diagonal’s labeling scheme).

We can now read the purpose of ‘u’ in the definition as being each and every possible enigma wheel stepping – which enumerates the rods in some ordering. each row/rod still has to capture the truth of the proposition. But in qudit thinking, the value is represented by the amplitude for the particular character function. For only one row will the amplitude be non-zero, that which associated with the value of the input character.

ok. that makes a lot of sense – it’s discrete qudits … in 1940s thinking. By the time this enigma-table thinking ends up in Colossus we see the refinements, and the focus on 5 qubits (since Colossus is working with Tunny, which is a binary algebra). In Colossus one is interested up to 5 layers of spectral data (one per count-type, whose count imposes a constrained search space limited to the evolutions within the coset derived from the subgroup) – where such are the amplitudes of the ANF rows some superposition of which captures the “enigma-algebra” for a particular setting.




Computer Programmer who often does network administration with focus on security servers. Very strong in Microsoft Azure cloud!
Link | This entry was posted in coding theory. Bookmark the permalink.