Quantum computing is a hotbed of innovation. The extraordinary potential of this weird yet wonderful intersection of physics, maths and computer science is attracting heavy investment from companies around the world. Each has heard that the magnitude of gains promised by the coming revolution will make today’s purely classic approach seem like something out of the stone age. But a word of caution: our digital security is threatened as soon as quantum computing is fully realised.
Securing interconnectivity, enabling new ideas
Quantum computers have some special properties which give us the power to run next-generation algorithms. One of them, Shor's algorithm, would allow a quantum computer to far outperform our classical computers for solving certain problems. The difficulty of factorising large integers and solving the discrete logarithm problem are facts which many of our current asymmetric encryption standards such as RSA and ECDSA rely upon to stay secure (NIST)1. This is where the threat to digital security lies.
Symmetric cryptography is also not safe from the rise of quantum computing. Grover’s algorithm can crack symmetric crypto more efficiently than classical alternatives. While it does speed up this process – for the algorithms vulnerable to it – it is less disruptive than Shor’s algorithm. The commonly chosen approach to counter this new algorithm is to just double the size of the encryption keys, which brings us back to acceptable security levels. This, however, does not give us much respite. In most typical applications, symmetric keys are initially established or exchanged using the asymmetric methods vulnerable to Shor’s algorithm, so these are still at risk from quantum computing.
Post quantum cryptography is an important new technology which is the topic of heavy research.
The whole idea is to write algorithms capable of running on classical hardware, which are secure against the computations possible in quantum computers. The US organisation NIST is running a competition to find a suitable new algorithm, or set of algorithms, to keep us secure.
1 NIST Standards relating to encryption relying on integer factorisation and the discrete logarithm problem are outlined here https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br2.pdf and here https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar3.pdf respectively.
Promising competition algorithms
Having just begun the competition’s third round, NIST has identified some promising algorithms as finalists with some backups just in case. The majority of the finalist algorithms use lattice based cryptography which is showing some promising characteristics in general, not only in the post quantum security space but also in homomorphic encryption. This technology has the potential to drive advances in secure distributed computing.
One of the final hurdles to surpass before we start applying these new algorithms in anger is to test their implementations against physical attacks such as side channel attacks, power analysis and other such physical threats to their security.
Are we still safe?
While the quantum computers that we can make currently are not powerful or large enough to run the algorithm that will render RSA vulnerable, our data is still not truly secure anymore. An attacker could be saving encrypted data now – they then just need to wait until they have access to a quantum computer.
This may not be important for some information which only needs to be secure for maybe the next five years. But for data which needs to be secured longer than this, we should be concerned. While it’s difficult to make estimations as to how fast quantum technology will advance, most observers suggest we have between five and 30 years.
Now with the NIST competition still ongoing, one might ask why not sit back and wait? Let a standard be chosen and switch to it as required, job done. Sadly, it may not be as simple as that. Quantum computing is young as a field and will only grow. It is still difficult and unintuitive to design new, useful or potentially dangerous algorithms which leverage the properties of quantum computers.
There is still some doubt as to whether any of the algorithms in the NIST competition will continue to be secure far into the future. This highlights the importance of creating flexible architectures which can switch up their underlying encryption without needing to be recalled. As we want to avoid obsolete hardware.
As well as allowing us to stay secure for longer periods of time. It might even be that we no longer look to one standard authentication algorithm, key establishment algorithm or encryption algorithm. We might rely on a multitude of different combinations of algorithms, spread out and implemented where they are suited best. Leaving a tricky optimisation in choosing where you can bridge the gaps and affect performance the least.
We must act now
While there are plenty of algorithms which could replace RSA or Elliptic Curve crypto, the decision is not an easy one. There are many factors to consider when deciding an encryption algorithm’s performance. Key sizes are important. Low cost embedded hardware generally will be highly constrained in this regard and so having too large a key size has potential implications on the IoT market as a whole.
Embedding post-quantum cryptography into today’s devices
An algorithm will take time to run, some are fast and others slow. Switching to a significantly slower algorithm could cause noticeable slowdowns as the sheer bulk of data we are interacting with on a daily basis increases. This brings up the question of how you scale networks using slower or more bulky underlying tech. Networks will only grow larger. How do our current architectures handle themselves with the new encryption under the hood?
This is why it is so important to be ready for the changes that are to come. The changes needed are required now. As data becomes more and more valuable, the security of the data becomes even more important. IoT devices and 5G networks will only increase the amount of data in circulation but we need to keep it safe.
So, what are we doing? We’re undertaking research to explore the challenges around building real-world products relying on post quantum crypto. The different algorithms have different strengths and weaknesses and assessing these to find how they fit within current product design patterns is an important step towards seeing them used on a wider scale.
Get in touch
We are aiming to not only understand the challenges, but also potentially develop new secure architectures which maximise the value and security the different post-quantum algorithms bring. This complements some of our other research in the quantum domain quite nicely. For example, our investigations into quantum key distribution are looking at how quantum computing can help improve our security rather than threaten us. If you are investigating the impact quantum computers might have on the security of your products, we’d love to hear what you’ve found and discuss any help we can provide.