<https://carnegieendowment.org/2019/04/25/implications-of-quantum-computing-f...> [...] The security of encryption systems relies on the use of operations that can be done quickly by someone who knows a secret key but requires vastly more time for someone who does not know it. An encryption algorithm typically has an adjustable key size, and the algorithm is designed so that a modest increase in the key size causes a modest increase in decryption time for those who know the key, but a massive increase in decryption time for those who don’t know it. This ensures that the key size can be made large enough so that decryption becomes massively, prohibitively expensive for those who do not know the key, but remains very practical for keyholders. The security of a cryptographic algorithm depends on maintaining a very large gap between the effect of a key size increase on those that know the key versus those that do not know it. Decryption without knowing the key amounts, in practice, to a kind of brute-force search: it requires searching an extremely large space of possible secret keys, trying different keys in turn until finding one that unlocks the encrypted data. On a classical computer, the expected time required to do this is proportional to the number of possible keys that exist—the searcher must try half of the possible keys to have a fifty-fifty chance of trying the correct one. The effect of quantum computing on the security of an encryption algorithm depends on how large of an effect quantum computing will have on the time required for nonkeyholders to find the secret key. Encryption Algorithms That Quantum Will Thoroughly Compromise For some encryption algorithms, quantum computing might allow those without the key to sidestep entirely the need to do brute-force search by, for example, enabling a key extraction algorithm that can find the decryption key directly without a blind search. For instance, the popular Rivest-Shamir-Adleman (RSA) encryption algorithm relies on the assumption that factoring a large number is very difficult. In RSA, the secret key is essentially a pair of large prime numbers, P and Q. The product of multiplying P and Q is published, but it is assumed that an adversary who knows the product of P and Q cannot derive the factors P and Q from that product except by a variant of brute-force search. Factoring appears to be very time-consuming for classical computers, but a quantum computer could quickly extract the factors P and Q by using a method called Shor’s Algorithm. In a world with large quantum computers, RSA would not be secure because someone without the key who knows the publicly available product of P and Q could quickly recover the secret key. Encryption Algorithms That Can Be Kept Secure By Increasing Key Size Other encryption algorithms are not prone to being defeated so thoroughly by a method like Shor’s Algorithm. For these methods, quantum computing is not a fatal threat, because an adversary must still engage in brute-force search. But there is a quantum shortcut, called Grover’s Algorithm, that can speed up any brute-force search substantially, allowing a space of a given size to be searched in an amount of time proportional to the square root of that size. This approach would be enough to defeat many encryption methods if they are not adjusted. In this case, it is possible to compensate for the effect of quantum computing by increasing the key size, expanding the space that must be searched by brute force, so as to counteract the effect of Grover’s Algorithm. For many encryption algorithms, doubling the key size, say from 128 bits to 256 bits, has the effect of squaring the size of the key space that someone without the key would have to search. This countermeasure exactly offsets the square-root effect of Grover’s Algorithm, restoring the security level of the pre-quantum algorithm. One consequence is that data that was encrypted before the emergence of viable quantum computing—with the original smaller key size—will become susceptible to decryption when quantum computing does become available, but data encrypted with the larger quantum-safe key size will continue to be secure. (Like classical computers, quantum computers would be expected to get faster over time, necessitating the same kinds of generational increases in key size that have been necessary in the pre-quantum computing era.) [...]