Monday, 14 March 2016

Post Quantum Encryption Is Evolving

Having recently written about post quantum encryption, and why it means that public key encryption will not die with the advent of quantum computers, I realise from many comments I received that I need to clarify something.  "Quantum resistant" does not mean "quantum proof".

One particular comment I received pointed out that although some elements of some implementations of lattice encryption were not subject to attacks using Shor's algorithm, Grover's algorithm might still apply.  In particular if you consider the BLISS Ring-LWE Signature Scheme , Grover's algorithm can be used to mount an attack against the random oracle element of the scheme (if you want t o play with the original implementation of BLISS it can be found here). You can see from the original implementation that that oracle is such that it is not collision resistant.  Hence conducting a preimage search would be a suitable for, of attack, and preimage searches (using such as Grover's algorithm) are just what quantum computers are good at. 

I totally agree.

However, as I pointed out when I previously discussed post quantum encryption, we need to be moving on with the research into, for example, lattice encryption schemes to find and correct just such shortcomings.  It's not widespread but it is happening.

Only today a paper landed on my desk which proposes a scheme that attends to some of the concerns about the early implementations of BLISS Ring-LWE Signature Scheme.  The proposed scheme shows how the hash-based random oracle can be modiļ¬ed to be more secure against quantum preimage attacks.  This particular scheme has the benefit of decreasing signature size at any given security level.

The new scheme has a great benefit in that the way certain operations are implemented means that the same code (or circuitry) could be used.  Such lack of efficiencies of design are another comment I've received about quantum resistant crypto schemes.

You may find it useful to read another paper by the same author form late 2015.

The researcher who authored this paper, Markku-Juhani O. Saarine, is one who has turned his attention to post quantum encryption.  I would suggest what we need are more of the same.

If you are interested in this area I would encourage you to read this new paper to convince yourself that whilst there may be some issues with the current state of the art in post quantum cryptography, it simply means there are opportunities for researchers to make new discoveries.

I think we all know that quantum resistant cryptography is not as mature as the public key encryption schemes in use today.  But, you can see that these problems are not insurmountable.  It takes effort and that takes money: both are becoming available so I think I'm still safe in asserting, as I did before, that quantum computing will not mean the end of public key encryption.

UPDATE 18/03/2016 - another interesting paper came out which showed a cache attack on BLISS.  This is clearly an active area of research.