Computer scientists have been searching for any possible cracks in our modern encryption techniques. One specific type of encryption, RSA (Rivest, Shamir, Adleman), is particularly at risk against quantum computers. Fortunately this risk is not immediate.
To understand how quantum computers put encryption at risk first let’s explore the RSA Algorithm:
The RSA algorithm utilizes the totient function to construct a modular exponentiation out of the product of primes. This serves as the encryptor/decryptor.
The totient of a number n finds how many numbers <n don’t share a common factor with n. It is trivial to find the totient of n if you know the prime factors of n because the totient of a product is the product of the factors’ totients; and the totient of a prime is very simple:
totient(p) = p-1. (If a number is prime, every number below it does not share a common factor.)
The idea is that only the person with the private key can decrypt a message M, because they know the variable d in M=C^d(modn). Finding the exponent in modular exponentiation is a heavy computation.
The best way to crack this encryption is to find the prime factors of n, but this is incredible cumbersome for regular computers. Shor’s algorithm utilizes quantum mechanics to slice through this computation.
“The algorithm is composed of two parts. The first part of the algorithm turns the factoring problem into the problem of finding the period of a function and may be implemented classically. The second part finds the period using the quantum Fourier transform and is responsible for the quantum speedup.” -wiki
For quantum computers the basic unit of quantum information is a qubit i.e. a quantum bit. A quantum bit differs from a regular bit in that it is analog rather than binary. Traditional bits can be flipped on and off while qubits can be an entire range of on/off. Think of a traditional light switch versus a dimming light switch.
Initially it was estimated that a quantum computer would need ~1 Billion qubits to threaten RSA encryption, but Craig Gidney and Martin Ekerå have optimized the modular exponentiation such that it will only take ~20 million qubits to decrypt a 2048-bit RSA encryption in 8 hours.
To put this into perspective the largest quantum computer as of 2020 is google’s 72-qubit chip. So clearly quantum computing has qu-a-bit of development before we need to be concerned.
Another large issue with quantum computers is circumventing quantum noise, which is rather costly. Taking these obstacles into account, experts suggest it will take a few decades before quantum computers become this powerful.
There are post-quantum encryption methods, so the future of encryption in general is not at risk. However, databases with large amounts of RSA encrypted data will struggle to change the encryption of all their data.
For the average individual, you should not be concerned. Who’s at threat are those that have RSA encrypted data that would be harmful if released 20 or more years from now. Examples would be governments, militaries, and possibly larger companies. So there is a public concern if certain secrets or valuable information are released, just not an individual concern.
— Image and Explanation of RSA encryption
— Excellent Minute Physics video on this subject
