If there is any attack that is assigned probability 1/N under µ, and we sample 10N queries from µ, then we are basically guaranteed to get the attack. So if we sample 10N queries and don’t get an attack, then we can be basically guaranteed that there are no attacks with probability >1/N. In other words, there are no attacks with complexity < log(N).

That’s all I’m saying here, it’s not a very deep observation and I might be overlooking something, I’m not sure I understand your comment.

(In reality you’d want to tighten the discussion by talking about KL between distributions rather than individual inputs that have high probability.)