Cryptography

Quantum computation and its effects on cryptography

Claudio Dodt
March 14, 2019 by
Claudio Dodt

Cryptography is a method of protecting communication and data through the use of codes, so that only the ones with authorized access can read and/or process it.

Stating that cryptography is a fundamental security control is by no means an exaggeration; for millennia, military communications have been ciphered and thus protected with the use of some cryptographic model. From the era of Caesar with a basic substitution cipher, through World War II with the famous Enigma machine used by German forces. Even today, nations’ secrets are protected with what is still called military-level encryption.

Learn Applied Cryptography

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Of course, data protection has long moved on from being an issue restricted solely to the military. As expected, businesses and even individuals make use of encryption to protect their data, from a simple home Wi-Fi network to personal data regulations by the GDPR, and financial transactions that require confidentiality, integrity and non-repudiation.

Yes, encryption is a key information security control, but let me introduce you to a hard reality: All you need to break even the most sophisticated encryption is time and processing power. Fortunately, while an encryption algorithm such as Caesar's (which is over 2,000 years old) can be broken in a matter of minutes by a regular PC, algorithms’ current mathematical models such as AES, RSA or ECDSA are safe against brute-force attacks, even with massive processing power. It would take a long, a long time, centuries, to break a current cryptography correctly implemented with a reasonable size key.

Everything would be perfect, but as perfect is something rarely associated with information security controls, here comes a new threat: Quantum computing.

What Is Quantum Computing?

Quantum computing is a new way of computing. In a conventional computer the quintessential information particle, the bit, can only exist in two states, 0 or 1. A quantum computer benefits from the ability of subatomic particles to exist in more than one state simultaneously.

In this case, quantum bits (or QuBits for short) can store much more information because they make direct use of quantum mechanics properties, such as superposition and entanglement. Essentially, while bits can only be 0 or a 1, QuBits can assume any superposition of these values. This means computational operations can be performed at a much higher speed and with much less power consumption.

Quantum computing is nothing short of revolutionary. If you think this is a science fiction subject, take a look at The Quantum Computing Report and check out how global giants such as Intel, Google, IBM and Microsoft are investing heavily in the development of quantum computers.

Company Type Technology Now Next Goal

Intel Gate Superconducting 49 TBD

Google Gate Superconducting 72 TBD

IBM Gate Superconducting 50 TBD

Rigetti Gate Superconducting 19 128

USTC (China) Gate Superconducting 10 20

Qubit Count Updated January 21, 2019
Source: QUANTUM COMPUTING REPORT

If you still have any doubts, check out IBM’s Q System One, the very first commercial quantum computer. It has an initial 20-qubit capacity and was released early this year. Quantum computing is already a reality in 2019, and not only are big companies entering this market, but also governments and even joint ventures.

What Are the Impacts of Quantum Computing on Cryptography?

We’ve already established how essential encryption is in today's world — especially those based on the "public key" model, which are responsible for protecting most electronic transactions.

Public key encryption (also known as asymmetric encryption) actually relies on a number of mathematical algorithms that are considered too complex to break, especially when using an encryption key of a good size such as RSA-2048, ECDSA-256. Again, even with a massive amount of conventional computing power it might take an amount of time equivalent to the age of our universe (no, this is not a joke!) to ensure that cryptography will, in fact, be broken.

Quantum computing is a game-changer. It is possible to use something like the Shor’s algorithm, which explores quantum mechanics to solve the problem of integer factorization (i.e., given an integer N, find its prime factors) or another similar hypothesis such as the discrete logarithm problem. This is something essentially unfeasible for regular computers when the numbers involved are too large. But why would that matter? Well, many asymmetric cryptographic algorithms, such as RSA, are based on the assumption that large integer factorization is computationally unfeasible.

Back to the present: This assumption has proved true for conventional computers, but a hypothetical quantum computer with a sufficient Qubits capability could break RSA and other similar asymmetric algorithms, turning public-key encryption into a basically useless security control.

Ironically, symmetric algorithms (the asymmetric predecessors, which do not serve to protect electronic transactions since they have a single key) such as AES could still be considered safe, assuming they use a reasonably-sized key (i.e., AES 256 or higher).

Encryption in a Post-Quantum World

Assuming that with a few more years of evolution, quantum computers will reach the point where public-key cryptography can be easily broken, should you be worried and prepare for a world where electronic transactions will no longer be secure? Well, not exactly. There are already many studies directed to post-quantum cryptography, such as lattice-based cryptography, multivariate cryptography or hash-based cryptography, all of which are strong candidates for securing our data in a post-quantum world.

Of course, no one knows how long it will take to address potential vulnerabilities in post-quantum cryptography or even if they will be sufficiently reliable to protect their transactions.

Concluding Thoughts

It may be true that quantum computing is already a reality, but maybe it's still a little early for us to worry too much. Essentially, the quantum computing power needed to break current asymmetric algorithms will still be very expensive, which — at least initially — will probably be restricted to governments, especially those who like to pry into the secrets of other nation-states.

But a word of advice: We cannot rule out the possibility that the next scientific breakthrough in just a couple years will make quantum computing something accessible to the general public, or even worse, cybercrime syndicates. If that is the case, it will be necessary to bid farewell to old practices and hope that post-quantum cryptography has also evolved to the point of providing sufficient protection levels.

Learn Applied Cryptography

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

 

Sources

  1. What is Cryptography?, Kaspersky Labs
  2. Qubit Count, Quantum Computing Report
  3. System One — IBM Q, IBM
  4. Post-quantum Cryptography, Microsoft
  5. IBM warns of instant breaking of encryption by quantum computers: 'Move your data today', ZDNet
Claudio Dodt
Claudio Dodt

Cláudio Dodt is an Information Security Evangelist, consultant, trainer, speaker and blogger. He has more than ten years worth of experience working with Information Security, IT Service Management, IT Corporate Governance and Risk Management.