Monday, 9 May 2016

Post Quantum Crypto Scheme Demo Online

Following on from a number of post apocalyptic articles I'd read as to how quantum computers would spell the end of security on the web, I wrote back in March about how there are many candidates for public key encryption systems that appear to be resistant to quantum attacks, specifically Shor's algorithm.  One of the candidates I listed was from McEliece.

The original paper in 1978 was only two pages long:

And, it was rather forgotten as a public key crypto scheme as others found favour: everyone has heard of RSA but few of McEliece.

I was delighted then when in the past few days Prof Bill Buchanan at Napier University put up an online demonstration, and very nice explanation, of the McEliece scheme.  I'm not aware of another similar system, so if you're interested in such schemes I recommend visiting the site as it will teach you not just how the algorithm works but it has code showing how in can be implemented.  I think you'll see that it could very well be one of those schemes that we see protecting us in the foreseeable future.

One response I'd already had to my previous posts about post quantum cryptography reminds of a common misconception I think it worth commenting upon.  Many have said that although schemes such as those I've previously listed are resistant to Shor's algorithm, the "quantum speedup" afforded by quantum computers means that all of our crypto schemes will be at risk.  It's not quite that simple.

Whilst quantum computers allow dramatic improvements with specific algorithms, such as the Quantum Fourier Transform which lies at the heart of Shor's algorithm, the same is not true of other algorithms.  There are families of quantum implementations which do benefit.  Probably the best known are those similar to Grover's algorithm.  In some ways it's remarkable that Shor's algorithm does show the speed up in quantum computers - it certainly shouldn't be taken as a general rule.

It is not a case of simply plugging in a conventional algorithm to a quantum computer and waiting for the massive speedup that one sees in these well known algorithms.  Instead, you need to find quantum specific algorithms.  That's not to say that schemes such as the current candidates for post quantum crypto can't be attacked by a quantum algorithm, but it does mean that much more research is required to under stand what algorithms can be used to attack these schemes that in turn can be implemented in a quantum computer.

Of course, step 1 is really understanding the post quantum candidates and from there we will start to identify ways in which quantum based attacks might succeed.  And, for McEliece I can think of no better place to now start that Prof Napier's new demonstrator.