# Combining classical attacks and quantum cryptanalysis

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?

• 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. – SEJPM Oct 24 '18 at 19:41
• 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? – Maarten Bodewes Oct 24 '18 at 19:43
• 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? – Maarten Bodewes Oct 24 '18 at 19:51
• 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? – Maarten Bodewes Oct 24 '18 at 19:58
• 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)? – fkraiem Oct 25 '18 at 12:45

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.

• 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. – fgrieu Oct 25 '18 at 9:04
• @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. – Maarten Bodewes Oct 25 '18 at 15:05
• @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" – mephisto Oct 26 '18 at 16:59
• 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. – fgrieu Oct 27 '18 at 10:00