I’ve been asked a couple of times in the nearby past by partners, customers and prospects that encryption would not be secure for millions of years as always being stated. Instead of this it would be possible to “break” encryption within seconds in a 15-20 years’ timeframe when quantum computers become reality.
Well… kind of.
Since 1980, physics dream of a quantum computer that would be solve a mathematic problem without calculating the result. Quantum computers would be able to certain problems were todays computers would need years.
Certain problems?
Yes certain problems. Quantum computers will be able to solve specific mathematic problems like astronomic or physic questions very fast. All modern encryption technologies based on public / private key methods would become (almost) useless. But they’re not able to solve any kind of mathematic questions faster.
The reason is that public/private key methods are based on prime numbers (a natural number that has no other divisor than one and itself). So basically all common used methods like RSA, DSA or based on elliptic curves would be affected.
Asymmetric encryption methods are based on prime factorization and the calculation of discrete logarithms. Two problems (in theory) that can be solved with quantum computers using the Shor-Algorithm. (1994 by Peter Shaw)
Anything lost?
No: The post-quantum cryptography, PQC is a part of cryptography that deals with cryptographic principals (e.g. block ciphers, secure hash algorithms, strom ciphers, and cryptographic secure random number generators) which cannot efficiently be broken with quantum computers.
What about symmetric encryption (like AES or DES)?
Symmetric encryption is also impacted by quantum computers but not in the same way as asymmetric encryption. The Grover algorithm would allow half the bits of symmetric encryption keys:
e.g. 128 AES = 64 bit. (At least 80 bit would be required to provide a level of security which could be seen as secure and not to be broken in a human’s lifetime.)
256 would become 128 bit.
Longer symmetric encryption keys could be used to counteract with the bigger calculation power of quantum computers.
Quantum computers are not the end of encryption. Some of the methods used today will become obsolete but encryption in general will be even more relevant as unsecure methods could be broken easier which will lead to a higher demand for privacy.