Introduction: With the arrival of the first quantum computers – while still imperfect, cryptologists from all around the world have started to ring the alarm bell: If a quantum computer is built, it has the ability to crack many of the widely used cryptography present in everyday’s life in several industries, including the banking industries. Here we aim at presenting facts regarding whether or not it is realistic to start already preparing for a Post-Quantum cryptographic migration.
What are Quantum Computers and What is Quantum Cryptography?
Quantum physics study phenomenon, mostly energy phenomena that occur at a very small scale in the matter. The theory was developed in the early 1900s by Max Planck, a German physicist, in order to explain phenomena in a subatomic level that classical physics could not explain.
Quantum physics is a hard field, and especially a very active field of research. Particle accelerators, synchrotrons are technologies which are almost entirely based on quantum physics.
Quantum physics do not generally use a deterministic approach but rather a probabilistic one. This is mainly due to the very nature of quantum physics which parameters cannot be measured without significantly perturbing the whole system. The incertitude principle of Heisenberg, when applied to the subatomic level, is partly responsible for this.
Therefore quantum physics use tools such as Wave functions and superpositions of states to describe the physics at subatomic levels.
In other terms a quantum system, usually subatomic particles such as electrons, photons, neutrons, bosons, fermions etc… will be described by a probabilistic model where the number of states and the probability they are actually in a given state is computed.
If we take a very simple model, where a particle can have two states 0 or 1:
Roughly and with great simplification, this is the physical property that quantum computers are using to create quantum computing.
While digital computer works with two bits 0 and 1, a quantum computer works with qubits- quantum bits. An n-quantum bit is a series of n states of the wave function. What we just described previously is a 2-qubits. From this, recently, quantum chips have been created using quantum circuits. A quantum chip does not process 2 bits but n-bits. Anyway, the n-qubits are different than “just” n simultaneous bits. We just want to give to the reader a very basic overview and understanding of what is a quantum computer.
Quantum computers are actually been build – as of 2019 – and are still imperfect due to heavy noise.
IBM for example and the Fraunhofer institute are very actively researching and building quantum computers.
Google, rigetti, and D-Wave are among the other companies which are providing quantum computers.
Microsoft developed the Q# programming language to design and implement quantum algorithms.
Next, we investigate why Quantum computers are a threat to our “modern” cryptography.
Why Quantum Computers are a Threat to the Actual Cryptography
“Modern” cryptography results from the works of Alan Turing and a team of polish cryptographers led by Marian Adam Rejewski whose combined efforts in the 30’ and ’40s resulted in breaking the “Enigma’ german machine, which was an electro-mechanical computer.
Cryptography usually uses ciphering techniques where you must solve a challenge. If you have the key, solving the challenge is easy. If you have not the key, solving the challenge is hard. And this is how hard it is to solve the challenge without the key which determines how secure a cipher is.
In the past, ciphers looked like puzzles with symbols being scrambled with a hidden logic. That hidden logic was the key. It evolved to so-called ‘modern’ cryptography where the logic used to scramble the information ( aka ‘the cipher algorithm’ ) is no more the real challenge, but to reverse a mathematical system.
Using Turing machine and therefore digital computers to cipher and decipher messages became our actual cryptography, the post-WWII cryptography.
Messages are made up of bytes which are scrambled, combined with cryptographic keys (which are made up of bytes themselves as well), transformed by all sorts of diffusion mechanisms until the output becomes a stream of apparently random bytes.
The Data Encryption Standard (DES/3-DES) is a product of such techniques, using so-called substitution tables (S-Tables).
Other techniques involve number theories such as Fermat’s little theorem so to produce what is known as the RSA public-key cryptography system.
3DES (symmetric key algorithm) and RSA (asymmetric key algorithm) are among the encryption algorithms which are the most widely used all over the world. Emails, Web servers, ATMs, Credit Card Chip transactions (EMV) and many military encryption systems are for example using one or both of these algorithms.
Before any Quantum computer was even built, in the ’80s, the power of quantum cryptography was studied, mainly by the physicist Richard Feynman. Shortly after, the mathematician Peter Shor described an algorithm that is using quantum computing to factor an integer into its prime factors (The Shor’s Algorithm).
That algorithm involves the creation of dedicated quantum circuits with the quantum Fourier Transform having a central role in it. It was proved that the time needed by the algorithm to factor numbers is polynomial, meaning that it is not a complex challenge in terms of quantum crypto. The RSA is therefore vulnerable to such attacks.
Given an integer N, find its prime factors P1,…, Pn. The problem is extremely simple to understand but extremely hard to solve. The best-known algorithm using ‘conventional’ digital computers is GNFS (general number field sieve) and it takes a time of:
to factor a b-bit integer! On a quantum computer, using Shor’s algorithm, it takes only time of:
To have a better understanding of the difference, we may consider that it will take a time of:
to factor, an integer coded with b bits on a digital computer while it will take a time of:
to factor it on a quantum computer…
With a 400 bit number, we see that we need a time of 1,000,000,000 seconds to break it on a digital computer. While it will take 10,000,000 seconds to break it in a quantum computer. Of course, that time is relative to one CPU or to one core.
But it means that roughly if it takes 115 days for a quantum computer to factor a 400-bit integer then it will take … 31 years for a digital computer to do the same! “Fast” Factoring a number into primes is equivalent to breaking RSA. Therefore a quantum computer is able to break most RSA ciphers on the planet unless they would be using ridiculously huge key size (what would dramatically slow down the RSA ciphering and deciphering operations ).
Grover’s algorithm, same as Schor’s algorithm is able to break 3DES using a probabilistic iterative method.
What is Post-Quantum cryptography
As long as Quantum computers existed only on paper, there was no real matter for the cryptographers to be concerned. Now, as the threat of a “real” quantum computer to be built is becoming more and more possible, the rules of the game have changed… according to the US National Institute of Standards and Technology (NIST):
“Researchers working on building a quantum computer have estimated that it is likely that a quantum computer capable of breaking 2000-bit RSA in a matter of hours could be built by 2030 for a budget of about a billion dollars.”
Post-Quantum cryptography consists of migrating from what are considered as theoretically weak cipher algorithms to what are considered theoretically as strong cipher algorithms regarding quantum computing.
Most Post-Quantum algorithms are using the following technique to make sure they are “Quantum proof”:
Lattices are “just” Z-basis over an n-dimensional manifold. They can be easily visualized as equidistant grids like for example, a metal mesh. Such mathematical objects have been studied by Gauss or Minkowski during the past centuries. Lattice and elliptic curves are deeply connected with the most complex number theory problems. For instance, it took an incredible amount of work over hundreds of years to solve the Big Fermat Conjecture as it was linked to a special type of elliptic curve. Therefore, many problems involving lattices are among the hardest mathematical challenges known and for which there are no solutions. The only solution is an exhaustive search, which is unfeasible even for the most powerful quantum computer.
Learning with Error (LWE)
The learning with error problem consists in totally recreating or as close as possible, a function over a finite ring knowing only a given sample of that function, and some of these samples may be intentionally erroneous. This is linked to the general techniques used in Monte-Carlo methods to reconstruct laws of unknown phenomena given a set of samples. It is difficult to recreate such functions with samples with errors. That difficulty is the base of the security behind all LWE Post-Quantum crypto.
Isogeny Graphs
Isogeny is a transformation between elliptic curves which is slightly more than isomorphisms (where the j-invariant is the same). Supersingular curves are then special objects that lie all in a unique isogeny class. From that, supersingular isogeny graphs are created where vertices are the supersingular objects and where edges are isogenies. It is extremely difficult to find paths inside these graphs so this is the base of all isogeny related post-quantum crypto.
In general, all these algorithms are using the latest developments in algebraic geometry, which is actually the hardest field in research math.
The security of these algorithms is based on the assumed fact that if the human brain still could not break these challenges, a quantum computer won’t be able to do it either, and will only be left with the option of an exhaustive search.
We could not rule out that, by following the same logic, Post-quantum crypto will, some days, use for instance, Lie groups or even Universal Teichmuller theory (when that theory becomes more understandable).
Here is a list of recommended quantum-proof algorithms:
FrodoDH and frodoKEM, a Ring Learning With Errors (R-LWE) encryption and key exchange algorithm
SIDH, aka Supersingular Isogeny Diffie–Hellman key exchange, an elliptic curve-based key exchange algorithm using the fact that the isogeny group of a supersingular elliptic curve is non-abelian
NewHopeDH, another Ring-Learning-with-Errors key exchange protocol
McEliece (Classic), an old asymmetric encryption algorithm relying on goppa error code
SIKE, aka Supersingular Isogeny Key Encapsulation, using random walks on isogeny graphs
Kyber, a CRYSTAL (Cryptographic Suite for Algebraic Lattices) algorithm for key encapsulation using LWE
NTRU prime, another R-LWE cipher algorithm
Dilithium, the other CRYSTAL algorithm using the “Fiat-Shamir with Aborts” technique in lattice-based cryptography.
Do We Need to Prepare for Post-Quantum Cryptography?
The motivation to start preparing for a migration to quantum-proof algorithms is that cryptosystems may have dozens of years of the life of use and may still be in use when quantum computers are able to break them.
Nevertheless, should companies start preparing for something which is supposed to happen in about 10 to 20 years? We all know about the Greenhouse effect and prediction of climatic changes. Their consequences may by far overpass the threat of a quantum computer… so should companies in the Silicon Valley start to relocate in the mountains to prevent been destroyed by a possible tsunami that may occur in the next 10 years, as a result of climatic changes? Not to mention preparing for a global economic crisis or even a third world war which effects would certainly make futile the fears for a quantum computer.
Quantum computers are real, yet they are still not able to break anything, or at least not significantly.
Besides, there are no real proofs that quantum-resistant algorithms are actually resistant because there are simply no quantum computers to test them.
If an effective quantum computer would be built, it would be created by a large country, namely the USA, China or Europe or Russia. These countries have already a lot of intelligence allowing them to break cryptosystem using malware, trojans, or simply forcing backdoors into them. So, in a nutshell, this would not be used by the average hacker group operating on the darknet.
There are therefore few reasons to start worrying about such a “threat”. Besides, there are other sorts of computers been actively developed such as neuronal or biological computers which may use complex AI and who may have the ability to break the quantum-proof algorithms.
The rise of non-digital computers is a fact and when they will be able to break our “modern cryptography”, it will be time to think of next-generation cryptography, the post-digital cryptography.
Acodez is a renowned web design and web development company in India. We offer all kinds of web design and web development services to our clients using the latest technologies. We are also a leading digital marketing company providing SEO, SMM, SEM, Inbound marketing services, etc at affordable prices. For further information, please contact us.
Looking for a good team
for your next project?
Contact us and we'll give you a preliminary free consultation on the web & mobile strategy that'd suit your needs best.
Rithesh Raghavan, Co-Founder, and Director at Acodez IT Solutions, who has a rich experience of 16+ years in IT & Digital Marketing. Between his busy schedule, whenever he finds the time he writes up his thoughts on the latest trends and developments in the world of IT and software development. All thanks to his master brain behind the gleaming success of Acodez.
