4
$\begingroup$

How can we use Quantum Computing to break a Cryptosystem like RSA or AES-256?

Can we use Quantum Computing to solve difficult mathematical problems like Discrete Logarithms or Prime Number Factorization?

$\endgroup$
4
$\begingroup$

RSA is based on high computational complexity of integer factorization. In simple words you prepare two large prime numbers $p$ and $q$. These composed your private key which is used for decryption. The public key used for encryption is simply product $m = pq$. If you were able to factorize public key, you would get private key and break the cypher. Since for large $p$ and $q$ this taks is very difficult as factorization of integers is exponentially complex on classical computers, it is not possible to break RSA in reasonable time.

There is Shor's algorithm which is able to factorize an integer to primes in polynomial time on quantum computers insted of exponential time as is the case for classical algorithms. However, current quantum computers can run Shor's algorithm for numbers like 21 or 35. This means the algorithm is useless for breaking RSA. Recently, so-called Variational Quantum Factoring appeared. This algorithm converts integer factorization to binary optimization task which can be solved even on single purpose quantum annealers. The VQF is able to factorize numbers in order of ten thousand which is still very low for breaking RSA.

Overall, quantum computers can increase speed of integer factorization rapidly (the speed-up is exponential) and help to break RSA. But nowadays, quantum computers are too noisy and have too few qubits to do so.

$\endgroup$
2
  • 1
    $\begingroup$ To add on this: A quantum computer is good in finding periods. Cracking RSA can be converted into finding a certain period in a function (see Shor's algorithm) and 'therefore' it can be done efficiently on a QC. Some other cryptography standards (like elliptical curve) can also be converted in this sense, so they are also not safe against QC's. AES is something else (for starters, it is symmetric), and the fastest speedup you can get in cracking AES is only a quadratic speedup through Grover's search algorithm (as you're searching the entire database of passwords faster). $\endgroup$
    – JSdJ
    May 4 '20 at 10:25
  • $\begingroup$ @JSdJ: Thanks for addition mainly about AES. Could you please post it as another answer? I would give you points. $\endgroup$ May 4 '20 at 11:34
4
$\begingroup$

To add on the answer of Martin Vesely:

RSA is not safe against a general quantum computer, because of Shor's algorithm (see link in other answers), which translates the problem at hand (in RSA) of factorizing large coprime numbers to a problem of period finding within a function (namely, the discrete logarithm). Quantum computers are, among other things, good in period finding through the quantum Fourier transform.

Moreover, RSA is not the only classical encryption standard that can be translated into period finding; for instance some forms of elliptic curve cryptography. All these standards are, to an extent, known as 'discrete logarithm' cryptography standards. The discrete logarithm is the source of the hardness of these standards.

For post-quantum cryptography, there are essentially two ways to go:

  • Post-quantum (classical) cryptography, with a promising candidate forms of lattice based cryptography. The hardness in computing the keys for these standards are also evident on quantum computers (they are not all-powerful machines); in complexity theory terms we say that these problems are outside $BQP$, the $P$-equivalent of quantum computers.

  • Quantum cryptography, where you use the powers of quantum computers (or rather quantum networks) to attain what some people call inherently safe cryptography: the key is not hidden through some hard-to-compute calculation as with RSA or other classical encryption standards, but the key is inherently not-computable or knowable (using one-time pad encryption, where the key is generated through the quantum cryptography protocol). Even if the adversary was all-powerful and had all the computable power imaginable, the encryption cannot be broken, provable based on our current understanding of nature (specifically, quantum physics).$^{1}$

Note that all of the above is on public or asymmetrical cryptography, where the key is not shared in advance. For symmetric key encryption like AES, a quantum computer can have at most a quadratic speedup through Grover's search algorithm, which allows us to search the database of possible keys quadratically fast. This is, at least from a theoretical perspective, not an issue: just double the key size and breaking is equally hard again. In practice, symmetrical key encryption will not be impacted by quantum computers.

$^{1}$ This is the theoretical slimmed down version. Of course, in practice, there are many caveats and exclusions. For some more discussion see this previous question and answer and this answer it references on the cryptography stack exchange.

$\endgroup$
1
  • $\begingroup$ Thank you a lot! $\endgroup$
    – Maf
    May 7 '20 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.