5
$\begingroup$

I'm regularly reading that AES-256 is secure against quantum computers because Grover's algorithm will only halve the key strength (i.e. "only" require $\sqrt{2^l} = 2^{l/2}$ operations instead of the full $2^{l-1}$ operations required to brute force the key).

However, would it be possible that classical attacks on symmetric ciphers such as AES could be sped up using quantum computing based algorithms? Is it possible / likely that the security of a block cipher is degraded more severely (e.g. by more than an additional 2 bits strength) if or when capable quantum computers become available?

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ One may want to note that standard quantum cryptanalysis attacks (eg Shor) already combine classic with quantum computations, but of course you can efficiently emulate a classical computer on a quantum computer anyways. $\endgroup$
    – SEJPM
    Commented Oct 24, 2018 at 19:41
  • $\begingroup$ Noted! But I presume Shor doesn't use known weaknesses in a cipher such as AES and the attacks that have been defined to exploit them? $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 24, 2018 at 19:43
  • 1
    $\begingroup$ Well, yes, OK, but what I'm getting at is that there could be existing classical attacks that can be sped up. It may not be needed to define entirely new and currently unknown attacks that use a quantum computer (?). Should we therefore already consider that the security strength could degrade even further than we're currently seem to expect? $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 24, 2018 at 19:51
  • 1
    $\begingroup$ Of course, of course, but all the more reason to look at the other possible / known attacks as well, right? Some - or in the case of AES, all - are currently infeasible because of memory / time requirements. But will they still be infeasible when QC comes around? $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 24, 2018 at 19:58
  • 1
    $\begingroup$ Why does the question say "known or unknown attacks" when everything else (title, comments) hints that it is about known attacks (and whether they can be improved by quantum computers)? $\endgroup$
    – fkraiem
    Commented Oct 25, 2018 at 12:45

1 Answer 1

Reset to default
2
$\begingroup$

The short answer is: Of course! Why not!

It is pretty easy to build an artificial secret key encryption scheme that is based on RSA and breaks if the adversary has a quantum computer*. Of course no one would want to build a symmetric primitive out of number theoretic assumptions as that would defeat the main purpose of being far more efficient than asymmetric crypto (the usual exceptions left aside...VSH...). However, symmetric primitives might provide exploitable structure that we just did not find yet. Indeed, in a far stronger security model where the adversary gets quantum access to honest parties (i.e., the CPA oracle) one can actually break several secret key encryption schemes as they are vulnerable to period finding algorithms. Therefore, the conventional effort of cryptanalyzing symmetric primitives has to be enhanced by the study of quantum algorithms.

[*] capable of running Shor's algorithm, which breaks RSA.

Improve this answer
$\endgroup$
4
  • $\begingroup$ It's beyond me why RSA is in the answer, when the question does not mentions RSA, but rather mentions AES-256 and Grover's algorithm. If we hypothesize a quantum computer with enough usable qubits, Grover's algorithm is the algorithm of choice against AES-256, but not RSA, which according to currently common wisdom seems best tackled by Shor's algorithm. $\endgroup$
    – fgrieu ♦
    Commented Oct 25, 2018 at 9:04
  • $\begingroup$ @fgrieu I think the idea of this scheme was to show a proof of concept, showing that a currently secure secret encryption scheme can be broken using a quantum computer, with a complexity less than Grover, i.e. by using Shor. I don't think it is such a bad answer in that sense, although common secret key algorithms are of course not build using the RSA problem. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 25, 2018 at 15:05
  • 2
    $\begingroup$ @fgrieu this is indeed the intention. It shows that there do exist secret key encryption schemes which are not secure against quantum adversaries. Now, we know that the structure of the RSA problem is vulnerable in that sense, however, there might exist other structures which turn out to allow for quantum attacks. What if ARX turns out to be such a structure? I am not arguing that secret key crypto is insecure in that setting, I just wrote that there is no justification to assume it is secure. Other than "we do not know an attack" $\endgroup$
    – mephisto
    Commented Oct 26, 2018 at 16:59
  • $\begingroup$ Ah I now get the idea. Indeed this "shows that there do exist secret key encryption schemes which are not secure against quantum adversaries". I took the liberty to edit the answer (which also allowed to reverse my down-vote); feel free to remove my note. $\endgroup$
    – fgrieu ♦
    Commented Oct 27, 2018 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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