What Are the Threats of Quantum Computing?
In the previous blogs we have briefly touched upon how resistant symmetric and asymmetric cryptography are against quantum attacks. Here we discuss the topic in more depth.
Among the various other implications of a working quantum computer, the ones that are among the most important for the cryptographic landscape are attacks based on quantum algorithms like Shor’s and Grover’s. For now, these attacks are just theoretical, first devised in 1994 and 1996. With a quantum computer they could be implemented in practice.
Shor’s attack can be applied to asymmetric codes (public key cryptography), such as RSA and ECC. What it essentially does is it factorizes a given integer N in polynomial time. For a given key of length K, Shor’s algorithm needs 2K qbits to break RSA, and 6K qbits to break ECC. The important part is, Shor’s algorithm can break both the RSA and ECC codes. This is the reason why various PKI infrastructures are one of the security areas the most threatened by quantum attacks.
Grover’s algorithm, on the other hand, can be applied to symmetric cryptography, and to hash functions. The good news is, it does not break them completely, it “just” provides a quadratic speedup to known attacks and thus decreases the levels of security.
The tables below, prepared by Entrust, give us a good overview.
Cryptographic Algorithms 
Type 
Purpose 
Impact from Quantum Computer 
AES256 
Symmetric Key 
Encryption 
Secure 
SHA256, SHA3 
 
Hash function 
Secure 
RSA 
Public key 
Signature, Key Establishment 
Not Secure 
ECDSA, ECDH 
Public Key 
Signature, 
Not Secure 
DSA 
Public Key 
Signature, 
Not Secure 
Crypto Scheme 
Key Size 
Effective Key Length/Security Level (in bits) 

Classical Computing 
Quantum Computing 

RSA1024 
1024 
80 
0 
RSA2048 
2048 
112 
0 
ECC256 
256 
128 
0 
ECC384 
384 
256 
0 
AES128 
128 
128 
64 
AES256 
256 
256 
128 
How are we preparing?
A number of quantumresistant ciphers has been developed in the past decade or so that could take the place of RSA or ECC. The National Institute of Standards and Technology (NIST) is currently in the process of evaluating several candidates for postquantum standards covering publickey encryption and keyestablishment, and digital signatures. On January 30^{th} 2019 NIST has announced 26 candidates that made it into the 2^{nd} round of the NIST PQC (Post Quantum Cryptography) Standardization Process. The selection process is expected to end between 2022 and 2024.
It therefore seems that we will still have to wait quite a few years for PQC standards, though we can’t predict when exactly quantum attacks will become a real threat. When the first working quantum computer is built, we can safely assume that there is a high probability it won’t immediately be public knowledge. It should therefore be our goal that by the time quantum computers become a reality, the present cryptography has already been substituted by PQC.
How long will the transition to PQC take?
In order to try to answer this question, let us look at other transitions of cryptographic algorithms we have faced in the past. ECC was, for example, defined in 1984 and became a NIST standard in 1994. Around 2005 NSA was pushing for a greater adoption of ECC in the governments and banking sector, but by 2016 it has partly dropped ECC because of low adoption rates. Another example is SHA1. The depreciation of SHA1was recommended five years before it went into effect, yet it still took about 13 years until widespread change. So all in all, the industry’s track record on adopting new algorithms is not that great.
At the same time, it is true that now we have more incentive to move quickly because of a greater potential threat. There are many things the companies can already do right now to make the coming transition to PQC easier – understanding what types of keys your systems use, where they are stored, which algorithms will have to be changed, how to achieve crypto agility,… Additionally, certain quantumready products are already available on the market.

Source: Nastja Cepak, PhD Cryptography, and CREAplus Cybersecurity Team.