expander graphs, eigenvalue basis, DES subkeying, closure

Accept the theory that the generation and scheduling of the subkeys in DES is a carefully orchestrated process. What might be the motivating design principle behind it?

Well, we already hinted at the idea that one should one view the particular DES method as an embodiment of the general process. The method happens to look rather like a couple of Tunny wheels that step and at each rotation show up their wheel patterns as if they were rows in a circulant matrix. Should the patterns have appropriate content, then one creates a sigma-algebra out of the eigenvalues of that matrix.

Lets look now at a more general process focussing on the sigma algebra whose terms are eigenvalues.

IN the world of expander graphs in random (vs quantum) walks, a base graph generates further computational graphs. In much the same way that a spin algebra creates products whose value is a member of the closed set (of spin operators), the product of two graphs produces a new graph that is also within the closed set (of “operator graphs”). Retaining the closure property, in a non-abelian world, is the key property. It is that which allows the spectral character to relate to the normal representation and form up a conditional meta-operator whose outputs are themselves conditional-operator values. One has a transform that generates transforms, that is – using the principles that leverage automorphisms doing name re-labeling to the generation of permutation groups (that …. permute bits).

Now we know from Turing how to use a 2-d, 7-point geometry to represent the right kind of sigma-algebra – the sort that represents spin algebras; and we know how to go search out those permutation groups expressible using rotor wiring that can implement said simple lie group formulations. Of course, it looks like a triangle with a circle in the middle. Now act like the Egyptians and make a 3d, 3-face pyramid out of this ‘base geometry’: take two 2-d triangles (“with their circles in the middle”) and place them one upon another. rotate the lower in 3dspace, hinged on one size (at two connecting nodes). Use the implied edge that completes the pyramid – as the projection “point”; in much the same way that one uses a projection origin for a hypercube to generate the 2-d, 7-point geometry. Of course, the cube and its projection are algebraic duals, whether 2d or 3d!

In this way, we can see our 3-d, 3-sided pyramid and the now 3-d “bloch” sphere formed out of the 3 circles much as Turing did with his 2-d, 3-sided triangle (with circle within). And their roles are the same, with the surface of the sphere representing mutual dependencies – in the sense of linear algebra. Whereas permutation groups implement the 2d form of the project geometry, we might ask: what embodiment could implement the 3d form?

The theory of expander graphs provides the answer. The operator-graphs give non-commutative expressions that derive additional operator-graphs, and assure the closure of expressions involving automorphism-inducing graph adjacency linear operators, graphs adjacency linear operators for the coverings of said graphs, and a certain meta operator. The well-formedness of such expressions is determined from it aligning with a walk on the covering graph of the semi-direct product of the base graphs. The semi=direct architecture between covering and covered graphs provides for the “conditional” generating capacity – an automorphism generator function, giving one in turn a generalized coin flipping operator suitable for tensoring with the *quantum* walk operator represented by the feistel network.

One is assured, by the very definition of an expander graph, that the spectral gaps between eigenvalues – now acting as a spectral basis for the computational model – always tend away from zero, giving one a positive distance, always. We have a L2 space and convergence, that is.

Fascinating to see the bigger picture – and to also related it all back to Tunny wheel patterns stepping along rotors, as they turn for each character of plaintext!


About home_pw

Computer Programmer who often does network administration with focus on security servers. Sometimes plays at slot machine programming.
This entry was posted in DES. Bookmark the permalink.