Are there any encryption suites that can be cracked by usual computers or super computers, but not quantum computers?
If that's possible, what assumptions will it depend on? (Factorizing big numbers, $a^b\pmod d$ $a^c\pmod d$ $a^{bc}\pmod d$ etc...)
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Related: Can a quantum computer simulate a normal computer? & Is it possible for an encryption method to exist which is impossible to crack, even using quantum computers?. $\endgroup$– Sanchayan DuttaMar 15, 2018 at 15:32
-
4$\begingroup$ A quantum computer can theoretically do anything that a classical computer can do, in which case your question only makes sense as a question about the technological state of the art. All it would take is a cryptosystem which can easily be solved by a classical computer using basic arithmetic (such as simple addition modulo N) on sufficiently large numbers that those numbers cannot be stored on today's relatively minuscule prototype devices. $\endgroup$– Niel de BeaudrapMar 15, 2018 at 16:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This is not a very enlightening concept, because most interesting quantum algorithms, such as Shor's algorithm, involve some classical computations as well. While you can always shoehorn a classical computation into a quantum computer, it would be at unnecessarily exorbitant cost.
We don't yet know, of course, exactly what problems will be hard to solve even if given a quantum computer—the NIST PQCRYPTO competition is in progress right now to study that question.
However, even then, it likely won't be answered definitively any more than we can answer definitively what cryptography we can't break with classical computers: nobody has found a realistically efficient classical algorithm for factoring a product $n$ of uniform random 1024-bit primes whose totient $\phi(n)$ is coprime with 3, nor has anyone found a realistically efficient classical algorithm for computing cube roots modulo $n$, nor has anyone even ascertained whether factoring is harder than computing cube roots (though certainly it's not easier).
At best, we can say that a lot of smart people have been well-funded to think very hard about it, and we can choose parameter sizes that thwart the best attacks they have come up with. The outcome of the NIST PQCRYPTO competition will be the same, with any luck—unless someone clever thinks of ways to break every single one of the dozens of candidates.
answered Mar 15, 2018 at 16:41