11
$\begingroup$

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...)

$\endgroup$
13
$\begingroup$

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.

$\endgroup$

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.