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 Mar 29 '16 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 Mar 29 '16 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 Mar 29 '16 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 Jul 10 '16 at 15:38

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.

| improve this answer | |
  • $\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 Jul 10 '16 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 Jul 10 '16 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 Jul 11 '16 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$ – Yehuda Lindell Jul 11 '16 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 Jul 11 '16 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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