I am trying to understand the Forking Lemma in cryptography which is a lemma used to prove security of signature schemes by showing that a forging machine can be "forked" (i.e., snapshotted and then multiple instances started in different environments) in some strategic way to break a hard problem.
The original forking lemma was described in Security Proofs for Signature Schemes by Pointcheval and Stern. I'm having trouble with Lemma 3, which states:
Let $A\subseteq X\times Y$ such that $P(A(x,y)) \geq \epsilon$. Then there exists $\Omega\subseteq X$ such that (a) $P(x\in\Omega)\geq\epsilon/2$ and (b) if $a\in\Omega$, $P(A(a,y))\geq\epsilon/2$.
The paper calls this "well-known". It is not well-known to me and a few simple proof strategies don't seem to work. In particular I'm not sure why we get division by 2 rather than square-rooting or something when we transition between the probability function on $X\times Y$ and those of $X$ and $Y$.
Can anyone provide a proof of this statement?
Let $$\Omega=\{\,a\in X\mid P(A(a,y))\ge \epsilon/2\,\}.$$ Then $$\epsilon \le P(A(x,y))\le P(x\in\Omega)\cdot 1+P(x\notin\Omega)\cdot\frac\epsilon 2 \le P(x\in\Omega)+\frac\epsilon 2$$ hence $P(x\in\Omega)\ge\frac\epsilon2$.