Cryptanalytical Quantum computing circa 1980; building on 1950s theory


One of the interesting things about modern (2013-era) quantum computing mechanism is that it is NOT so different in its conceptual basis to the concepts used experimentally from the 1950s. But shush! …lest folks figure that quantum cryptanalysis has been around “practical” form rather long than folks might realize!

Of course, just as Colossus was a cryptoanlaytical processor rather than a general purpose  computer that followed up the theoretical Turing computing of a decade earlier, assume that quantum crypt-analytical computers of the 1980-era  were not general purpose (and fault-tolerant) computing devices. Rather, they did just one thing – just like Colossus, in the electronic era: they proved a theoretical possibility at high expense.

Back in 1950s crypto circles, folks were very much still thinking about 1930s length functions in topological spaces – searching out those special groups that allow secret or hard to compute “trapdoor” graphs whose difficulty in solution by computation denies an attacker the ability to compute the length function – necessary for solving hard puzzles.

Looking at recent theory, we can look back at what were was probably considered secret cryptanalytical theory – back then.

From the notions associated with the analysis of cayley graphs we get to the heart of the security property known as graph expansion. In the quantum computing world of 1950 and 1980 alike, folks were interested in a related property – the minimum energy state for a quantum superposition. The two concepts are related, when considering optimization functions that link combinatoric properties to algebraic properties.

image

http://www.win.tue.nl/diamant/symposium05/abstracts/quisquater.pdf

When computing mean sets of graphs, under the random walk presumption that underlies mult-particle modeling (such as the bits in a plaintext), we are used to calculating the volume of probability space occupied by the average clique of neighbors. Then, we are interesting in the expansion property – that only for certain cliques of relative size less than alpha.N can we be certain that the expansion ratio from mean-set members to adjacent neighbors is greater than beta.K. Of course, k is related to the minimum weight – the latter being an upper bound on alpha.N.

image

http://www.win.tue.nl/diamant/symposium05/abstracts/quisquater.pdf

If we now see things in terms of the 2 generator terms of A and B (above), we are interested in “that series of basis change” modeled by a particular sequence of generators applied to a start state. Of course, we remember seeing this back in 1954 (or earlier) from Turing, who modeled the cyclic powers in terms of a sequence of enigma rotors, which of whose wirings represented a generator. A sequence of rotors modeled h(M) – such that the sum of the powers would be zero (and thus model the 7-point geometry or hamming code on the hypercube).

image

http://www.win.tue.nl/diamant/symposium05/abstracts/quisquater.pdf

We have to remember that at the end of the day, all cryptanalysis is a search problem.  Thus one is always interested in the computing or alternatively “finding” the minimum energy state of a superposition system – realizing that if one JUST has the right basis sequence one can compute more effectively. This clique search for mean-sets is the “trap door” for certain groups,  of course – likely to apply to DES of course (if only one thinks different). One tends of thinks of Braid groups as the foundational group able producing expressions hard to calculate in a standard computational model, but easy to calculate (if one can figure just the right basis [sequence] in a reasonable time).

Is interesting that to see what Turing understood that Quisquater evidently does not – that for a non-Abelian group, a given sequence of generators (each term being Ci where I runs from 1 to n distance/edges) can be re-modeled in terms of density evolution.  Turing understood that finding the mean-set was equivalent to finding the minimum energy state of a superposition – or the average sampling function for sufficient trials that induce a cauchy sequence.

Looking at the Stanford group (which has long been a NSA math front  for pure theoretical topics):

image

http://lucatrevisan.wordpress.com/2011/01/16/cs359g-lecture-1-overview/

The material http://theory.stanford.edu/~trevisan/cs359g/lecture05.pdf is essentially the same material as Turing discussed in his On Permutations manuscript. What’s more, the well written summary clearly lays out the thinking steps. Turing’s example helps too, being so tied up with early mixers – that also related to quantum mechanics and the “chemistry” of uranium fission, etc.

Advertisements

About home_pw@msn.com

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