# 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