What is the prp-advantage of a $2^{80}$-time adversary attacking AES-256?

Question

I am somewhat confused with something I read in Dan Boneh's slides discussing the advantage of a $2^{80}$-time adversary attacking AES-256; according to Boneh, the assumption is that this advantage is bounded by $2^{-40}$ (see slide 8 here or fast forward to 7:04' in the video here).

I have been looking to a few lecture notes (e.g., Goldwasser-Bellare, pg 72, section 5.5 at cseweb.ucsd.edu/~mihir/papers/gb.pdf) and books (e.g., Boneh-Shoup cryptobook draft 0.3 chapter 4, the katz-lindell book, or the handbook of applied cryptography chapter 7), but I am still unsure about this bound. It seems unrelated to quantum attacks on the key, which may justify a square root on $2^{80}$; however, an exhaustive search for AES-256 keys should take $2^{128}$ steps on a quantum computer.

In addition, it doesn't seem to be related to the birthday paradox either. Most birthday attack related bounds in the aforementioned references were linked to a mode of operation (for example, CTR-mode attacks related to the number of blocks encrypted under the same key), proofs related to PRFs, etc. What I find confusing is the connection between the time complexity of the adversary and the PRP advantage bound, as the attack that distinguishes the PRP from a truly random permutation is unclear.

Is the $2^{-40}$ advantage assumption accurate? If so, how is it explained? Why the adversary is getting this advantage after all?

Answer 1

You misunderstood what Dan Boneh was trying to say. There is no known attack on AES256 that comes even close to this complexity. However, if there was a known attack that came close to this, then it would be very unwise to assume that this is the best attack. When formalizing an assumption, one needs to be conservative relative to what is known. Thus, Dan was giving an example of how one could formulate a conservative assumption about AES, and he was being very conservative (which is a good thing).