Anthony Culligan, SETL Chief Engineer
10/8/19

SETL cryptography committee’s first recommendation was ‘parameterise everything’.  The basis was that all crypto methods have a lifespan and you must be able to upgrade your crypto as new techniques emerge.  Quantum computing threatens certain kinds of cryptography so, as with other threats, we need to be ready.  With this in mind, SETL successfully developed a number of post quantum techniques in 2018 which it could switch on very quickly if required.   

Google then announced ‘Quantum Supremacy’ in September 2019.  As you can imagine, this prompted a number of client calls.  The following puts the important Google announcement in some context and, we hope, clarifies a few things.
Quantum Supremacy is a controversial term.  It essentially says that a specific task was completed more quickly on a quantum computer than a classical computer – regardless of the task.  Google have found such a task.  It is a tiny but important step in the development of quantum computers.  Mainly it demonstrates that they were able to actually control a quantum computer and get deterministic results.

The problem with quantum computers is that they are impacted by tiny vibrations and interference.  Even then results are only probably right or wrong.  Smart algorithms have been devised to increase the ‘probably right’ outcomes but every time you add a step to a calculation, the uncertainty increases again.  Stringing enough calculation units together to do anything useful and overcoming both the physical and probabilistic barriers is very very hard.

On the effect on crypto – it is all still very theoretical.  The crypto used by blockchain is the same as that used in mobile phones, chip and pin cards, and on https sites on the internet.  It relies on two basic algorithms, Elliptic Curves and RSA.  Both are ‘trapdoor’ functions which essentially rely upon the fact that it is easier to find the product of two numbers than to find the factors of the resultant number – easy to go one way and hard to go the other.  There are algorithms to solve these trapdoor type problems which are smart kinds of trial and error approaches.  It so happens that those algorithms fall within what might be possible with quantum computers and the ‘probably right’ smart approaches – but it would require many many more calculation steps which in turn requires a solution to the instability and probability problems.

Even though it is still very much in the realms of theory, there is ongoing work to combat any threat should it arise.  This is typically co-ordinated by the NSA through their NIST standards.  They hold competitions for new crypto methods very regularly.   The stream which is looking at the quantum threat is progressing well.  See below.
https://www.nist.gov/news-events/news/2019/01/nist-reveals-26-algorithms-advancing-post-quantum-crypto-semifinals

The work being done by NIST focuses on three kinds of underlying mathematical techniques, Lattice methods, code based systems and multi-variate methods. SETL’s preparatory work has been mainly around Lattice methods.  Lattices methods rely upon geometric problems that are dissimilar to the ‘discrete log’ problem which underlies the RSA and Elliptic Curve methods and are not susceptible to the quantum approach.  Interestingly, other methods being proposed derive from research which was put aside when RSA was widely adopted.  These older methods might well be more reliable than brand new thinking as they would already have survived a number of years of attack.

In any case, our approach is to keep abreast of what is happening and to build our software so that we can plug in new algorithms as they become tested and available.  This manifests itself in, for example, using ASN.1 formats wherever we store keys – which means that every key is also stored with a tag which describes what kind of key it is.  This allows us to encumber assets and to authorise state transformations using a range of cryptographic methods and to introduce new ones in a controlled and relatively straightforward manner. 

To conclude, an interesting and important achievement was announced by the Google team but it is still quite a way from being a practical threat to our day to day use of cryptography.  Nonetheless no-one, particularly SETL, is sitting on their hands!  

We are very happy to engage if you would like to discuss SETL’s work on post quantum techniques and can assist in research and readiness projects.  Contact us here.