The main unrealistic assumption in Lemma F.1 is that the prior over the logit values is i.i.d. uniform over an interval. A better assumption might be that most of the logit values come from a light-tailed unimodal distribution. We leave more realistic lower bounds and attacks that make use of this better prior to future work.