4
$\begingroup$

I am trying to understand the implication of the Borel-Cantelli Lemma to the random oracle model.

I think understanding a special case, say, a random oracle is one-way with probability 1, would be helpful. The statement (see, e.g., page 19 of Arkady Yerukhimovich's thesis) as far as I understand in words goes like "if the adversary $A$ given access to an $n$-bit random oracle $O_n$ succeeds in the game (given $y$, output a preimage $x\in O^{-1}(y)$) with probability at most $1/n^2$, then $A$ must fail the game for sufficiently large $n$ with probability 1 over choices of $O$."

I don't understand what it means by "with probability 1 over choices of $O$," when $O$ does not refer to a specific size $n$ (which I think is the setting where the Borel-Cantelli Lemma applies). The adversary $A$ is uniform, and therefore the adversary $A_n$ for $n$-bit oracle can be constructed by learning the size of $O$.

Let the distribution $D_n$ be the uniform distribution over $n$-bit functions. Clearly $D_n$ is the distribution of an $n$-bit random oracle. But I suspect that the same statement works for other distribution (i.e., whether the oracle distribution is uniform or not does not matter).

Does the statement mean that for $D=D_1\times D_2\times\ldots$ and a sequence of oracles $O_1,O_2,...$ sampled from $D$, $A_1,A_2...$ must fail the game for sufficiently large $n$ with probability $1$ over choices $O_1,O_2,...$? If that's correct, then I'm not sure if $D$ is well-defined. If not, I'd appreciate if you could let me know precisely what the correct statement is.

$\endgroup$
6
  • $\begingroup$ Borel cantelli lemma is hardly a standard cryptography tool. You can improve your question by stating it. Also, does it not apply to infinite sequence of RVs? $\endgroup$
    – kodlu
    Dec 9, 2022 at 2:19
  • 1
    $\begingroup$ Thanks. I improved the question. I suspect it applies but I'm not sure. $\endgroup$
    – user50394
    Dec 9, 2022 at 7:13
  • $\begingroup$ "I don't understand what it means by "with probability 1 over choices of $O$," when $O$ does not refer to a specific size $n$". Since the number of possible $O=\{O_1,O_2,\cdots\}$ is uncountable, we have to rely on measure theory. So, that statement should really be "for measure 1 of $O$s". There is a one-to-one correspondence between random (bit) oracles and reals: choose a random real $r$ and then the set the value of $O(x)$ as $r_i$, the $x$-th bit of $r$. So, it boils down to defining measure for reals, which you can find in standard textbooks. Does this clear your doubt? $\endgroup$
    – ckamath
    Dec 10, 2022 at 9:49
  • $\begingroup$ @ckamath I think my confusion is that whether the Borel-Cantelli lemma really means A wins the game with probability/measure 0 over $O_1,O_2,\ldots$. And my interpretation of your answer seems to suggest it is correct. And thanks for clarifying on whether the distribution over $O_1,O_2,\ldots$ can be made well-defined, though I still don't get what it means by choosing a random real. $\endgroup$
    – user50394
    Dec 10, 2022 at 19:03
  • $\begingroup$ "... whether the Borel-Cantelli lemma really means A wins the game with probability/measure 0 over..". It's subtle. It is used to show that only for measure $0$ of $O$s the adversary's advantage is more than expected at infinitely-many $n$s. In other other words, for measure $1$ of $O$s, the adversary's advantage is more than expected at only finitely-many $n$s. This can now be used to argue that for measure $1$ of $O$s, the adversary's advantage is negligible. $\endgroup$
    – ckamath
    Dec 11, 2022 at 20:35

1 Answer 1

2
$\begingroup$

$ \newcommand{\AA}{\mathsf{A}} \newcommand{\sO}{\mathcal{O}} \newcommand{\fO}{O} \newcommand{\str}{\{0,1\}^*} \newcommand{\strn}{\{0,1\}^n} \newcommand{\NN}{\mathbb{N}} \newcommand{\adv}{\varepsilon_{\AA,\fO}} \newcommand{\sP}{\mathcal{P}} \newcommand{\SUCCESS}{\text{SUCCESS}_{\AA,\fO,x}} \newcommand{\DEVIATION}{\text{DEVIATION}_{\AA,\fO,n}} $

Let's go through the proof from [Y,IR] in a bit more detail since it is technical and subtle (I struggled a lot with it). The role of Borel-Cantelli lemma will become clear in the process, and is summarised at the end.

Random oracles. We consider (function) oracles $\fO:\str\to\str$ interpreted as an ensemble of oracles $\{O_1,O_2,\cdots\}$, where $\fO_n:\strn\to\strn$. Let $\sO$, denote the set of all such oracles. Since $|\sO|$ is uncountable, before talking about random oracles, we need to define what it means to randomly sample from a sample space that is uncountable. To this end, one defines a probability measure. Since there is a one-to-one correspondence$^*$ between $\sO$ and $[0,1)$, one can resort to Borel sets and Lebesgue measure: see this lecture note for more details.

Random oracles are one-way. Now, our goal is to show that random oracles are one-way in a very strong sense: for measure $1$ of random oracles $\fO$, $\fO$ is a one-way function (OWF), i.e., $$ \Pr_{\fO\leftarrow\sO}[\forall\AA\in\text{PPT}:\adv(\cdot)\text{ is negligible}]=1, $$ where the advantage $\adv(\cdot)$ is defined as $$ \adv(n):=\Pr_{\AA,x\leftarrow\strn}[\underbrace{\AA(\fO(x))\in\fO^{-1}(O(x))}_{\text{Event }\SUCCESS}], $$ and it is negligible if $$ \forall c\in\NN~\exists n_c\in\NN~\forall n>n_c:\adv(n)\geq1/n^c. $$ We proceed as follows.

  1. Let's first analyse the advantage with respect to a fixed adversary and input. It can be shown by lazy sampling$^{**}$ that $$ \forall\AA\in\text{PPT}~\forall n\in\NN~\forall x\in\strn:\Pr_{\fO\leftarrow\sO}[\SUCCESS]\leq n^a/2^n, $$ where, for $a\in\NN$ (which depends on $\AA$), $n^a$ is the upper bound on $\AA$'s runtime.

  2. Next, we bound the probability that $\AA$ deviates from expected behaviour. To this end, let's define a bad event $$ \DEVIATION:\adv(n)> n^{a+2}/2^n. $$ It can be shown by applying Markov's inequality$^{**}$ that $$ \forall\AA\in\text{PPT}\forall n\in\NN:\Pr_{\fO\leftarrow\sO}[\DEVIATION]\leq1/n^2. $$

  3. We are now ready to apply Borel-Cantelli lemma. Since $$ \sum_{n=1}^\infty\Pr_{\fO\leftarrow\sO}[\DEVIATION]\leq \sum_{n=1}^\infty1/n^2<\infty, $$ by Borel-Cantelli lemma, we get that $$ \forall\AA\in\text{PPT}:\Pr_{\fO\leftarrow\sO}[\DEVIATION \text{ occurs for infinitely-many } n \text{s}]=0. $$

  4. This means for each adversary $\AA$, we can fix a measure $0$ of "bad" oracles $\sO^*_\AA\subseteq\sO$. Since the number of PPT Turing machines is countable (but infinite) and union of countable measure $0$ oracles is still measure $0$, we get that the set of all bad oracles $\sO^*=\cup_\AA\sO^*_\AA\subseteq\sO$ is still measure $0$. Therefore, we can switch the order of the quantifiers to get: $$ \Pr_{\fO\leftarrow\sO}[\forall\AA\in\text{PPT}:\DEVIATION \text{ occurs for infinitely-many } n \text{s}]=0. $$

  5. Finally, let's establish one-wayness. The above equation is equivalent to $$ \Pr_{\fO\leftarrow\sO}[\forall\AA\in\text{PPT}:\adv(n)>n^{a+2}/2^n \text{ for finitely-many } n \text{s}]=1. $$ It follows that there exists a $n_\AA\in\NN$ such that $\forall n>n_\AA,\adv(n)\leq n^{a+2}/2^n$. Since $n^{a+2}/2^n$ is a negligible function, and $\adv(n)$ grows slower than $n^{a+2}/2^n$ for all $n>n_\AA$, it follows that $\adv(n)$ is also negligible, which completes the proof.

To sum up, the Borel-Cantelli lemma is used to show that the bad event, $\DEVIATION$, does not occur infinitely-often, which then implies that it does not occur after a sufficiently large $n$, just like in the definition of negligible. This is key to establishing that the advantage is negligible.

$^*$This correspondence is easy to see for bit oracles: given a real number $r=0.r_0r_1\cdots\in[0,1)$, simply set the output $O(x)$ as $r_x$, the $x$-th bit of $r$. This can be extended to the function oracles as shown in [IR].

$^{**}$ See [IR,Y] for details.

[IR]: Impagliazzo and Rudich, Limits on the Provable Consequences of One-Way Permutations. STOC 1989.

[Y]: Yerukhimovich, A Study of Separations in Cryptography: New Results and Models, 2011, PhD Thesis

$\endgroup$

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.