Random Simon-oracle distribution for a classical lower bound

For every nonzero $s$, the map $x\mapsto x\oplus s$ is a fixed-point-free involution, so its $2^n$ addresses split into $C=2^{n-1}$ two-element cosets. Since $m\ge n-1$, $L=2^m\ge C$, and the number of injections from a $C$-element set into an $L$-element set is $L(L-1)\cdots (L-C+1)>0$, the sample space is finite and nonempty.

Give every pair $(s,\lambda )$ weight $1\mathrm{/}((2^n-1)L(L-1)\cdots (L-C+1))$. There are exactly the denominator's many pairs, so the weights are nonnegative and sum to one by [F2]. Because the number of injections is constant for each $s$, the induced hidden mask is uniform and, conditional on it, every injection is equally likely.

If $x\oplus s=y$, the two addresses lie in the same coset and receive the same label. Conversely, if $f_{s,\lambda }(x)=f_{s,\lambda }(y)$, injectivity of $\lambda$ gives equal cosets, hence $y=x$ or $y=x\oplus s$. Since $s\mathrm{\ne }0$, this is exactly the Simon promise with unique hidden mask $s$.