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$
  • 2
    $\begingroup$ Related: quantumcomputing.stackexchange.com/q/23/26 $\endgroup$ – Sanchayan Dutta Mar 15 '18 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 Beaudrap Mar 15 '18 at 16:53
  • $\begingroup$ @tparker I don't think it is an duplicate, because the other question is asking for encryption methods impossible to crack using QC and non-QC and this question is asking for an encryption impossible to be cracked using an QC but not impossible using an non-QC. I would say that the other question is related and probably a subset of this question. $\endgroup$ – MEE the setup wizard Mar 28 '18 at 15:15
  • $\begingroup$ @MEE good point. $\endgroup$ – tparker Mar 28 '18 at 15:24
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.