There has been considerable progress made in recent years into producing a viable quantum computer. Forms of quantum computer are already being sold to organisations such as Google, NASA and Lockheed Martin. This has led some to speculate that such computers pose an imminent threat to online security and, if made available to criminals, would leave many vulnerable.
Whereas conventional computers use “bits” for computing algorithms, quantum computers use “qubits”. Both bits and qubits can have the values 0 and 1, but qubits can be both 0 and 1 simultaneously during the execution of certain algorithms. In essence, quantum computers can run certain algorithms on a range of possible values in parallel, reducing to a single answer only when measurements are taken.
One of the first quantum algorithms developed was by Peter Shor. It was a way of using a well-known conventional algorithm for deriving the two prime numbers that have been multiplied to produce a composite number, known as factoring. One of the most popular public key encryption schemes in use today, RSA, relies upon the fact that it is easy to multiply two large prime numbers together but very difficult to determine those prime numbers given the resulting large product. All of the main forms of public key encryption in use on the internet today (RSA, ECDSA and DSA) rely upon mathematics that should be easy to compute in one direction but are computationally very hard to reverse (one way functions).
Shor’s algorithm introduced a way in which one particular part (known as order finding) could take advantage of the parallelism afforded by quantum computers. The result was that a quantum computer could derive the prime numbers in a composite in a fraction of the time it would take a conventional computer running the same algorithm. Subsequently it was realised that Shor’s algorithm was one of a class of quantum algorithms known as the Hidden Subset Problem (HSP).
It was then realised that the mathematics behind RSA, ECDSA and DSA are all solvable by variants of the HSP, using a quantum computer, in timescales that render these encryption schemes insecure. What might take thousands of years to solve on a conventional computer will take minutes on a large quantum computer running, for example, Shor’s algorithm.
It is likely that the first substantial quantum computers will be run by large, possibly government, organisations. Hence, one might argue that the threat is limited even once they enter operation. However, even before they evolve to domestically housed devices in the way conventional computers did, it is highly likely that the ability to use such systems will be widely available.
This model is already visible in the way companies such as IBM and DWave make their existing quantum computer facilities accessible to the wider public as a form of cloud computing. Hence, it is possible that criminals may be able to utilise the power of quantum computers to undermine internet security within the foreseeable future. The consensus is that this situation could exist as early as 2025-2030.
It is notable that although quantum information processing has been studied since the 1980s, there have not been a large number of quantum algorithms developed. There are essentially only three classes of quantum algorithm of which the HSP is the only class that appears to have implications for online security.
It should also be noted that not all quantum computers use the same principles. For example, the offering from DWave is not suitable for running algorithms for solving the HSP.
Some argue that the second class of quantum algorithm that contains Grover’s algorithm (a form of rapid searching in unstructured data) means that it is easier to, for example, conduct searches for encryption keys when those keys are of a known form. This typically applies to symmetric encryption rather than public key encryption. However, the speed advantage given by Grover’s algorithm is not the same exponential increase seen with Shor’s algorithm. The consensus is that by doubling the length of the shared secret key used by parties to a secure dialogue the advantages of using a quantum computer would be overridden.
Whilst law enforcement should be concerned about the threat that quantum computers pose, and they should be aware that it is a problem already looming on the horizon, it is a problem that has well understood boundaries. Hence, in working with academia and industry, law enforcement should encourage research into, and the adoption of, encryption schemes that are not susceptible to quantum algorithms within the HSP.
Candidates are being sought where a mathematical one way function that replaces those in use with RSA, ECDSA and DSA, and for which the HSP does not provide a solution. In searching for such a post quantum candidate, one also has to remember that it has to satisfy all of the security requirements of current schemes, i.e. it has to resist attacks that might be run on conventional computers.
Some candidates have existed since the earliest days of public key encryption, and despite 30 years of attempts they have resisted all attempts to break them. However, they failed to gain traction for a variety of reasons. For example, the public key that was generated was very large and would necessitate megabytes of data being exchanged for each transaction. Since the threat from quantum computers was recognised, variants of these early schemes have been suggested which solve some of the practical problems. Unfortunately, the variants so far proposed of these early schemes have been found to lack the level of security of the early versions.
The most likely source of post quantum encryption currently appears to be what is called Lattice Based Encryption. In the last 10 years this has seen a relatively rapid evolution into deployable schemes. The most popular of these schemes (known as NTRU) has not been widely explored in commercial practice as patents exist requiring licencing. However, this changes in late 2017. There are also recent variants of the NTRU scheme which are not affected by patents.
The most recent work has extended the original lattice based schemes with a technique known as Learning With Errors (LWE). These schemes have seen some very rapid evolution in the last two years. The most recent variant, proposed only at the end of 2015, is called New Hope. An experimental implementation of New Hope has already been deployed by Google as part of the SSL/TLS implementation in its Chrome browser.
Quantum computers are very likely to pose a threat to online security within the next decade.
Whilst quantum computers will require significant infrastructures to run in their early forms, there can be no doubt that the gains to be made from undermining existing online security will drive criminals to access such technology. In a world of cloud computing this is likely to be possible from the earliest eras of quantum computing.
However, whilst quantum computers pose a very specific threat we already know how it can potentially be mitigated. The European Union has already provided significant funding for research into identifying viable post quantum encryption schemes, and NIST277 has begun public consultation on the criteria that it should specify in a post quantum encryption scheme competition.
In the same way that security software has to be updated to mitigate new forms of malware, or encryption libraries have to be updated if a flaw is identified, commercial implementations of public key encryption software (particularly implementations of TLS) are likely to adopt post quantum encryption schemes which will be useless in preventing crime if they are not put into use.
Those involved in ensuring online security should be encouraged to remain abreast of these developments as it could see steep changes which alter the threat landscape.