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

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?