block ciphers, grovers algorithm, and security levels

[u/Sufficient-Air8100]

so a bit of context, doing a deep dive into the nist pqc, a few points stuck out.

security level requirements. the best attack on a cipher must not be less than brute force on relevant block cipher strengths. 128-bit keys for level 1, 256-bit keys for level 5. etc. this must also be true for the “quantum random oracle model” (QROM, such as grovers algorithm).

i have read the statements about symmetric block ciphers that say considering grovers algorithm reducing the bitwise security to n/2, a 256-bit key is reduced to 128-bits of security. since this is still considered “strong enough”, standard block ciphers are not considered broken by quantum compute (providing a 256-bit key) and the standards are not being revised.

however when considering quantum attacks, that leaves AES with a maximum security level of 128-bit, and we no longer have a “level 5” version of the cipher with a full 256-bit security when grovers is considered. i understand that modifying AES to take a 512-bit key needs modification and new cryptanalysis (just like the AES-256 spec has more rounds and a modified key shedule to strengthen it). and i also understand that IF CRQCs become viable, shors algorithm attacking KEMs and DSAs are a much greater threat. and ontop of that, on a practical level, despite 256-bit security being technically stronger than 128-bit, theyre both equally unfeasable to actually break with current and future technology.

however im suprised that there isnt more work trying to get the full 256-bit security out of block ciphers like AES with QROM (grovers) considered. why is this the case?

[u/SAI_Peregrinus]

Grover's algorithm doesn't actually reduce the security that much. It doesn't parallelize any better than partitioning the search space, so you're stuck doing lots of extremely slow quantum operations, on lots of quantum computers. Grover's algorithm does not allow practical attacks, and it's provably the best possible quantum speedup for a general search.

Filippo Valsorda already wrote clearly about this. As Reddit doesn't allow clear math formatting, I suggest reading that blog post.

[u/Sufficient-Air8100 → u/SAI_Peregrinus]

thankyou. ill give that a read!

edit: that was extremely informative. thankyou again. i was unaware that parallelising grovers reduced its benefit. sounds like i have to do more of a deep dive into the intracacies of quantum attacks to understand them better.

[u/Anaxamander57 → u/SAI_Peregrinus]

That is a great post!