Pointcheval and Stern in their paper on "Security proofs for Signature Schemes" state the following "well-known" probabilistic lemma:

Let $A \subset X \times Y$, such that $\mathrm{Pr}[A(x, y)] \geq \epsilon$, then there exists $\Omega \subset X$ such that

  • $\mathrm{Pr}[x \in \Omega] \geq \epsilon/2$
  • whenever $a \in \Omega$, $\mathrm{Pr}[A(a, y)] \geq \epsilon /2$

I am not familiar with the notation used and I also can't find this result in my literature.


  • Can $A$ be any set or it must be an event (measurable set)?
  • Does the notation $\mathrm{Pr}[A(x, y)]$ mean $\mathrm{P}\left(\{(x, y) \in A\}\right)$? Notation $A(x, y)$ could also imply that $A$ depends on $x$ and $y$, but I don't believe this is the case.
  • Does the notation $\mathrm{Pr}[x \in \Omega]$ mean $\mathrm{P}\left(\{(x, y) \in \Omega\times Y\}\right)$ or does it mean $\mathrm{P}\left(\{(x, y) \in (\Omega\times Y)\cap A\}\right)$
  • How can I prove this? Where can I find the proof?

In my definitions I assume that $A$ is an event and a subset of the sample space $X \times Y$ and that $P$ is a probability measure.


  • $\begingroup$ I'd guess you'd have finite sets in crypto so measurability shouldn't be an issue. $\endgroup$
    – kodlu
    Commented Mar 29, 2016 at 22:16
  • $\begingroup$ @kodlu, the proof uses probabilistic Turing machine with random tape. Random tapes are infinite. Set of all random tapes is infinite and therefore $X$ could be infinite, too. $\endgroup$
    – Student20
    Commented Mar 29, 2016 at 23:45
  • $\begingroup$ I can answer your first three questions: (2) $\Pr[A(x,y)]$ is $P(\{(x,y)\in X\times Y\mid(x,y)\in A\})$, that is, nothing but $P(A)$; (1) for this to make sense, $A$ must be measurable; (3) indeed, $\Pr[x\in\Omega]=P(\{(x,y)\in X\times Y\mid x\in\Omega\})=P(\Omega\times Y)$. $\endgroup$
    – yyyyyyy
    Commented Mar 29, 2016 at 23:57
  • $\begingroup$ You can assume that X is finite because the machine cannot read infinitely many bits (since it halts after finite time) $\endgroup$
    – fkraiem
    Commented Jul 10, 2016 at 15:38

1 Answer 1


This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit).

First, I assume that when writing $\operatorname{Pr}[A(x,y)=1] \geq \epsilon$, then the probability is taken over a random choice of both $x$ and $y$. Now, the claim is that there exists a subset of $x$ values of a "large enough size" so that for every $x$ in this set, the probability of the event is at least $\epsilon/2$ when taking a random $y$ only.

This can be proven as follows: Let $\Omega$ be the set of all values $a\in X$ for which $\operatorname{Pr}_y[A(a,y)=1]\geq \epsilon/2$. (Note that for any $a\in X\setminus \Omega$ it therefore holds that $\operatorname{Pr}_y[A(a,y)=1] < \epsilon/2$.)

Our aim is to prove that $\Omega$ is of size at least $\epsilon/2 \cdot |X|$, since this will show what we need.

\begin{eqnarray} \epsilon \:\leq\:\operatorname{Pr}_{x,y}[A(x,y)=1] & = & \frac{1}{|X|} \cdot \sum_{a\in X} \operatorname{Pr}_y[A(a,y)=1]\\ & = & \frac{1}{|X|} \cdot \sum_{a\in\Omega} \operatorname{Pr}_y[A(a,y)=1] + \frac{1}{|X|} \cdot \sum_{a\notin\Omega} \operatorname{Pr}_y[A(a,y)=1]\\ & \leq & \frac{1}{|X|} \cdot \sum_{a\in\Omega} 1 + \frac{1}{|X|} \cdot \sum_{a\notin\Omega} \operatorname{Pr}_y[A(a,y)=1]\\ & < & \frac{|\Omega|}{|X|} + \frac{\epsilon}{2}, \end{eqnarray} We therefore have that $\epsilon \cdot |X| < |\Omega| + \epsilon/2 \cdot |X|$ and so $|\Omega| > (\epsilon - \epsilon/2) \cdot |X| = \epsilon/2 \cdot |X|$, as required.

I hope that this is clear.

  • $\begingroup$ Thx a lot for all this demonstration, but there is just a missing step that I can't get : $\frac{1}{|X|} \cdot \sum_{a\notin\Omega} Pr_y[A(a,y)=1]$ to $\frac{\epsilon/2}{|X|}$. Why isn't it : $\frac{\epsilon/2\times (|X| - \Omega)}{|X|}$ as we have $(|X|−\Omega)$ elements in the sum ? $\endgroup$
    – Biv
    Commented Jul 10, 2016 at 18:18
  • $\begingroup$ @Biv you're right but the conclusion still follows if you just upper bound your expression in the comment by $\epsilon/2$ and subtract $\epsilon/2$ from both sides. $\endgroup$
    – kodlu
    Commented Jul 10, 2016 at 22:04
  • $\begingroup$ @kodlu your edit is correct. But the follow up of the proof is not anymore. $|X|$ has to stay as a divisor (why else would we multiply by $|X|$ on the next line). $\endgroup$
    – Biv
    Commented Jul 11, 2016 at 0:26
  • 2
    $\begingroup$ Note that I have edited the question so that it is $\epsilon/2$ in both parts. This is what I have proven and is actually what is in the stated lemma in the paper as well. $\endgroup$ Commented Jul 11, 2016 at 5:40
  • 1
    $\begingroup$ There is just a little mistake in the last line. It should be an equality instead of an inequality $(\epsilon - \epsilon/2) \cdot |X| = \epsilon/2 \cdot |X|$ $\endgroup$
    – tylo
    Commented Jul 11, 2016 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.