The 2^64 attack there is for 128-bit ECC, which is not hypothesis---it's a standard Pollard rho attack. That is, the entire purpose of rho is to find a "key col

The 2^64 attack there is for 128-bit ECC, which is not hypothesis---it's a standard Pollard rho attack. That is, the entire purpose of rho is to find a "key collision" aP + bQ = cP + dQ, from which we can immediately derive the secret key. The point there is that batching helps the attacker finding the first AES key by a factor of m, m being the number of keys being attacked, but it doesn't really help finding the first ECC key---although it does help with the cost of finding the second, third, etc a bit. So for example, the effective multi-key security of AES-128, given 2^32 different keys (read: sessions), is 2^96. See for example [1] for a formalization of multi-key security in the symmetric encryption setting. [1] https://eprint.iacr.org/2015/101 https://eprint.iacr.org/2015/101