14

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.

Questions:

  • 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.

Thanks.

Yehuda Lindell
  • 27,820
  • 1
  • 66
  • 83
Student20
  • 431
  • 2
  • 8
  • I'd guess you'd have finite sets in crypto so measurability shouldn't be an issue. – kodlu Mar 29 '16 at 22:16
  • @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. – Student20 Mar 29 '16 at 23:45
  • 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)$. – yyyyyyy Mar 29 '16 at 23:57
  • You can assume that X is finite because the machine cannot read infinitely many bits (since it halts after finite time) – fkraiem Jul 10 '16 at 15:38

1 Answers1

12

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.

yyyyyyy
  • 12,081
  • 4
  • 47
  • 68
Yehuda Lindell
  • 27,820
  • 1
  • 66
  • 83
  • 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 ? – Biv Jul 10 '16 at 18:18
  • @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. – kodlu Jul 10 '16 at 22:04
  • @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). – Biv Jul 11 '16 at 00:26
  • @Biv, thanks, I undid my edit... shouldn't have posted so soon after watching the Euro 2016 final (!) – kodlu Jul 11 '16 at 00:30
  • Indeed, it is an UPPER bound. That's why it's fine to write $|X|$ and not $|X|-|\Omega|$. – Yehuda Lindell Jul 11 '16 at 04:43
  • 2
    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. – Yehuda Lindell Jul 11 '16 at 05:40
  • 1
    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|$ – tylo Jul 11 '16 at 09:53