Cryptography in the wake of Quantum Computers

PKI Glossary

The need for faster, efficient & cheap computing power is ever rising. All of the combined scientific research has culminated into the exploration of Quantum computers which has come a long way from theory to practice. In 1998 Isaac Chuang of the Los Alamos National Laboratory, Neil Gershenfeld of the MIT, and Mark Kubinec of the University of California at Berkeley created the first quantum computer (2-qubit). Till then, with millions of dollars pouring into the R&D, ground breaking improvements have been made.

Qubits are like the processing engine, the more you have the better computational power you generate. Qubits can be thought of like transistors in computers having different states (0,1 or both at the same time). In 2021 the 100 qubits threshold has been broken by IBM (0) with the effort to increase it further in 2022. IBM aims to build IBM Quantum Condor with 1000 qubit in 2023. Both IBM and Google are aspiring to build the first Quantum Computers with one million Qubits. Google is also catching up on its efforts and improving ways of optimizing Quantum computing.

IBM Quantum Technology Roadmap


What are the chances of building a powerful Quantum computer?

Building a computing machine with 1 million qubits is not simple. Both IBM and Google are confident and researching heavily to achieve their targets. To see how fast technology is progressing, in 1971 Intel built its first processor with 2300 transistors. Currently intel processor have over 5 billion transistors. We see a jump of around 2 million transistors per year. Technology is improving at an exponential rate. With tech giants investing heavily, expectations are quite high. So far Quantum developments are progressing quite well. Vendors are not only adding more qubits but also improving their efficiency. Keeping this in view, presuming that such powerful machines will not be here in a decade will be a false assumption. Organization, specially working on cryptography must align them to plan for the next big change.

Is cryptography heading for a disaster?

Current cryptographic algorithms are based on prime number factoring or elliptic curves over finite fields. The importance for post-quantum cryptography arises from the fact that both ECC and RSA based encryption and signature algorithms can be broken using Shor’s algorithm for factoring and computing discrete logarithms on a quantum computer. If a Quantum computer with 1 million qubits built, the current cryptography will get a serious threat. As of now, to break 256-bit Elliptic Curve Encryption, it requires 13 × 10^6 physical qubits. Once built it would take less than 2 weeks to break an ECC 256 key. Likewise asymmetric algorithms RSA 2048 bit keys may also be broken.

Can current Cryptography survive after 2030?

Cryptography is here to stay but it will take massive transformations to reduce future threats. NIST started post-quantum cryptography standardization process in 2017 with 69 candidate algorithms. In 2019 NIST revealed 26 algorithms advancing to the Post-Quantum Crypto ‘Semifinals’. On July 22, 2020, NIST announced seven finalists (“first track”), as well as eight alternate algorithms (“second track“). These are:

  • Public-Key Encryption/KEMs: Classic McEliece, CRYSTALS-KYBER, NTRU, SABER
  • Digital Signatures: CRYSTALS-DILITHIUM, FALCON, Rainbow

In addition, the following eight candidate algorithms will advance to the third round:

  • Public-Key Encryption/KEMs: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE
  • Digital Signatures: GeMSS, Picnic, SPHINCS+

Which cryptographic algorithms can be used?

Till commercial quantum crypto algorithms become available NIST recommends to use:

  • RSA 2048 bit keys size till 2030 and beyond 2030 use RSA 3072 bit keys.

  • For ECDSA, key size ranging 160 to 223 is deprecated and recommends minimum 224 or more till 2030 and then 384 or more for 2030 and beyond.

  • For symmetric encryption key sizes 3DES is allowed till 2022 and then disallowed from 2023. It recommends AES 128 till 2030 and AES 192/256 for 2030 and beyond.

  • SHA-2 (224+) is allowed till 2030. Post 2030 one must use SHA-256, SHA-512 or SHA-3.

    To know more about NIST recommendations see NIST Special Publication 800-57 Part 1 Revision 5

When will NIST publish post-quantum cryptographic algorithms publicly?

NIST is planning to release post-quantum cryptographic algorithms in the year 2024. Around this time commercial libraries or application should also be available.

Preparing for the future

All organizations must start planning and soul searching. Prior switching to the new crypto algorithms organizations must identify where changes is to be done before finding how to make the change. You may follow this check list:

List company assets employing cryptographic algorithms. These can be:

  • Hardware (Desktops, Mobile, Smart Cards, HSM, Network devices, Servers, IOT)
  • Operating Systems (PC, Server, Mobile, Firmware)
  • Applications (Business, Mobile Apps, Client or Server)

Make a list of information which is being protected:

  • Password
  • Transactions
  • Documents
  • Configurations
  • Sour code

Identify the sensitivity of the information guiding you how much important that information is from Low, Medium, High or Critical. Once you have this map, start with the most sensitive data and trace it back to the OS and Hardware to replace.

Make a list of cryptographic algorithms which are in usage

This will identify those algorithms which are to be replaced in quick time vs those which are strong enough and give you more time to withstand Quantum computer threats.

Regularly check quantum updates from Google, IBM and NIST. Around 2024, identify Post-Quantum Cryptography vendors to replace.

Procure Quantum Safe Solutions. Test & buy new solutions followed by applying changes to your staging system

Finally Step. Switch the test/staging to production and repeat for all the remaining assets.

To read more on planning see the document from NIST Migration to Post Quantum Cryptography.

Codegic Quantum proof assurance

While there are no known Quantum computers to break the current stable crypto algorithms but there are imminent threats. Keeping this in view Codegic is actively reviewing the improvements in the Quantum cryptography space. As of now, our products supports military grade cryptography and can with stands known brute force attacks . Having said, we are actively looking at how the cryptography evolves. As NIST finalizes the algorithms, we will start integrating the new set of Quantum resilient cryptographic algorithms. To stay up to date, keep checking our blog for more updates on Quantum cryptography.

Want to know more about quantum computing? See this introduction from Quantum Inspire.