Quantum Computing & How Cryptography Needs to Change

By: Laurence Weir
Technology Lead, Biomedical Engineer
23rd January 2020
5 minute read
The creation of quantum computers is one of the ethereal technological challenges of the modern age, along with the likes of nuclear fusion reactors, and low-cost space travel. Algorithms designed for quantum computers will offer results which have a profound impact on nearly every aspect of our lives. Problems like protein folding (used to find new Cancer drugs), or SETI (the search for extra-terrestrial intelligence), will be solved many orders of magnitude faster than is currently possible with supercomputers. However, this also means most of our secure data is at risk.
Back to basics; the state of a “bit” in computing, is binary;
1 OR 0. HIGH OR LOW. VOLTAGE OR GROUND.
With the inception of quantum computing and the quantum bit, or “qubit”, this is going to change. Qubits are not just 1 or 0. They are 1 and 0 and everything in between. Those without a background in quantum mechanics, feel free to just go with the flow.
Conventional binary computers offer amazing abilities to solve linear logical problems. Many of these problems can be simplified as:
“WE KNOW INPUTS A,B,C…, AND HOW THEY INTERACT TO PRODUCE OUTPUTS X,Y,Z…”
These algorithms almost instantaneously change their outputs to changes in inputs. Problems such as:
“HOW MUCH MONEY DO I HAVE TO SPEND THIS WEEK?”
“WHEN IS MY TRAIN GOING TO ARRIVE?”
“WHAT IS THE WEATHER GOING TO BE LIKE TOMORROW?”
However, with qubits, in a quantum computer, as well as being able to solve do everything the conventional computer can, new problems will be solvable. These can be simplified as:
“WE KNOW OUTPUTS X,Y,Z…, BUT HOW DID WE GET TO THIS?”
These problems are solved right now using either brute force algorithms, or rely on being able to identify patterns. Here are some examples:
“HOW TO WIN THIS CHESS GAME?”
“HOW DO I FOLD THESE PROTEINS TO CREATE A CURE FOR CANCER?”
“HOW DO I BREAK THIS PASSWORD?”
For instance, a password in binary is just a fixed series of 1’s and 0’s. A traditional computer can crack this by trying every combination of 1’s and 0’s, perhaps also intelligently predicting what series are most likely. However, with limited processing power, and a long enough password, solving this takes longer than is reasonable (usually the age of the universe). However, with enough qubits, a quantum computer is able to solve it. The qubits instantly try every combination of 1’s and 0’s, and the password is cracked.
The modern cryptographic method involves multiples of two primes to create very long numbers. Certain numbers only have two factors, both of which are prime numbers. For instance, the number 889. To find them might take you several minutes by hand. A conventional computer would be able to brute force it by checking a list of primes. However, if the number was 2000 digits long, this search algorithm would take too long. Again the quantum computer is able to solve it by just using two groups of qubits representing the two primes.
BTW…THE PRIME FACTORS OF 889 ARE 7 AND 127.
When this quantum computer potentially emerges over the next decade, it will be able to break every encryption method and protected piece of information. It will also be able to impose its own encryption on the data which can never be broken by conventional computing. The owner of the quantum computer will be in sole possession of most of the world’s protected data.
Before that happens, the designers of quantum computers will have to overcome immense technical hurdles. A single qubit right now costs around $10k to create, compared to around $0.0000000001 for a conventional computer bit. These $10k qubits are still not of good enough quality for large scale computers. This creates compounded problems to develop error corrective algorithms to overcome this poor quality. At the moment, controlling multiple qubits simultaneously is very difficult. Lastly, each qubit requires multiple control wires.
Regardless of these challenges, we are now looking at a post-quantum era to which we should be designing our cryptography. In 2016, the National Institute of Standards and Technology (NIST) put out a call to propose algorithms that would not be able to be solvable by a quantum computer. They are analysing 26 leading candidate before implementation in 2024. IBM has selected one, in particular, called CRYSTALS (Cryptographic Suite for Algebraic Lattices). This method generates public and private keys based on “lattice algorithms”. An example of which is; A set of numbers is produced, as well as the sum of a subset of those numbers. Determining the different combinations of numbers which made up the final answer is currently unsolvable by quantum computing due to the multidimensional nature of the problem.
Therefore, quantum computing will solve many of life’s problems but will make some of our current cryptographic methods redundant. We will have to start soon moving to new methods to keep our future data safe.
If you want to know more about Quantum Computing, please get in contact with us below.
The creation of quantum computers is one of the ethereal technological challenges of the modern age, along with the likes of nuclear fusion reactors, and low-cost space travel. Algorithms designed for quantum computers will offer results which have a profound impact on nearly every aspect of our lives. Problems like protein folding (used to find new Cancer drugs), or SETI (the search for extra-terrestrial intelligence), will be solved many orders of magnitude faster than is currently possible with supercomputers. However, this also means most of our secure data is at risk.
Back to basics; the state of a “bit” in computing, is binary;
1 OR 0. HIGH OR LOW. VOLTAGE OR GROUND.
With the inception of quantum computing and the quantum bit, or “qubit”, this is going to change. Qubits are not just 1 or 0. They are 1 and 0 and everything in between. Those without a background in quantum mechanics, feel free to just go with the flow.
Conventional binary computers offer amazing abilities to solve linear logical problems. Many of these problems can be simplified as:
“WE KNOW INPUTS A,B,C…, AND HOW THEY INTERACT TO PRODUCE OUTPUTS X,Y,Z…”
These algorithms almost instantaneously change their outputs to changes in inputs. Problems such as:
“HOW MUCH MONEY DO I HAVE TO SPEND THIS WEEK?”
“WHEN IS MY TRAIN GOING TO ARRIVE?”
“WHAT IS THE WEATHER GOING TO BE LIKE TOMORROW?”
However, with qubits, in a quantum computer, as well as being able to solve do everything the conventional computer can, new problems will be solvable. These can be simplified as:
“WE KNOW OUTPUTS X,Y,Z…, BUT HOW DID WE GET TO THIS?”
These problems are solved right now using either brute force algorithms, or rely on being able to identify patterns. Here are some examples:
“HOW TO WIN THIS CHESS GAME?”
“HOW DO I FOLD THESE PROTEINS TO CREATE A CURE FOR CANCER?”
“HOW DO I BREAK THIS PASSWORD?”
For instance, a password in binary is just a fixed series of 1’s and 0’s. A traditional computer can crack this by trying every combination of 1’s and 0’s, perhaps also intelligently predicting what series are most likely. However, with limited processing power, and a long enough password, solving this takes longer than is reasonable (usually the age of the universe). However, with enough qubits, a quantum computer is able to solve it. The qubits instantly try every combination of 1’s and 0’s, and the password is cracked.
The modern cryptographic method involves multiples of two primes to create very long numbers. Certain numbers only have two factors, both of which are prime numbers. For instance, the number 889. To find them might take you several minutes by hand. A conventional computer would be able to brute force it by checking a list of primes. However, if the number was 2000 digits long, this search algorithm would take too long. Again the quantum computer is able to solve it by just using two groups of qubits representing the two primes.
BTW…THE PRIME FACTORS OF 889 ARE 7 AND 127.
When this quantum computer potentially emerges over the next decade, it will be able to break every encryption method and protected piece of information. It will also be able to impose its own encryption on the data which can never be broken by conventional computing. The owner of the quantum computer will be in sole possession of most of the world’s protected data.
Before that happens, the designers of quantum computers will have to overcome immense technical hurdles. A single qubit right now costs around $10k to create, compared to around $0.0000000001 for a conventional computer bit. These $10k qubits are still not of good enough quality for large scale computers. This creates compounded problems to develop error corrective algorithms to overcome this poor quality. At the moment, controlling multiple qubits simultaneously is very difficult. Lastly, each qubit requires multiple control wires.
Regardless of these challenges, we are now looking at a post-quantum era to which we should be designing our cryptography. In 2016, the National Institute of Standards and Technology (NIST) put out a call to propose algorithms that would not be able to be solvable by a quantum computer. They are analysing 26 leading candidate before implementation in 2024. IBM has selected one, in particular, called CRYSTALS (Cryptographic Suite for Algebraic Lattices). This method generates public and private keys based on “lattice algorithms”. An example of which is; A set of numbers is produced, as well as the sum of a subset of those numbers. Determining the different combinations of numbers which made up the final answer is currently unsolvable by quantum computing due to the multidimensional nature of the problem.
Therefore, quantum computing will solve many of life’s problems but will make some of our current cryptographic methods redundant. We will have to start soon moving to new methods to keep our future data safe.
If you would like to learn more about quantum computing please get in contact below.