3
$\begingroup$

Oded Goldreich in his book [Foundations of Cryptography, 2004, Section 3.2.3] proves a theorem by polynomial number of hybrids.


enter image description here


In rather recent years, Marc Fischlin and Arno Mittelbach published a paper [FM21, IACR 2021/088] and prove lemma 3.1 (equivalent to Goldreich's above theorem) by first considering 4 types of hybrid arguments:

1-section 3.1 Constant Number of Hybrids,

2-section 3.2 Polynomial Number of Hybrids with a Universal Distinguishing Bound,

3-section 3.3 Polynomial Number of Hybrids: Non-uniform Variant,

4-section 3.4 Polynomial Number of Hybrids: Uniform Variant (Goldreich proof is the item 2 of case 4)

Goldreich doesn't mention these 3 type of polynomial number of hybrids at all and prove the above theorem. Does he overlook some important details and his proof need correction?

I quote some lines from the paper:

Our blunder on the presentation of the hybrid argument was a good reminder how easy it is to trip up on formalizing cryptography and how seemingly small details can have devastating effects. Yet, when researching the literature we found that we were in good company.

... is utterly wrong if one allows non-constant t. And yet, this statement not only appears on Wikipedia, but also in this form in many research papers and cryptographic lecture notes.


In the paper, a counter example has been presented:


enter image description here


Especially this part of Goldreich's proof in the following, is it correct?

...Because the total number of hybrids is polynomial in $n$, a non-negligible gap between (the “accepting” probability of $D$ on) the extreme hybrids translates into a non-negligible gap between (the “accepting” probability of D on) a pair of neighboring hybrids. ...

In the paper, Fischin and Mittelbach feel that we need some conditions and consider 4 types of hybrid arguments.

And here is Goldreich's proof:

enter image description here

$\endgroup$
2
  • $\begingroup$ His proof predates the recent work So, the new work may be a refinement of the model/proof method that he uses. What exactly are you asking? Do the authors of the recent work refer to his work? That's the natural direction one should look. $\endgroup$
    – kodlu
    Feb 13 at 18:02
  • 1
    $\begingroup$ @kodlu, No they do not refer to prior works and state "Our blunder on the presentation of the hybrid argument was a good reminder how easy it is to trip up on formalizing cryptography and how seemingly small details can have devastating effects. Yet, when researching the literature we found that we were in good company." ... " is utterly wrong1 if one allows non-constant t. And yet, this statement not only appears on Wikipedia, but also in this form in many research papers and cryptographic lecture notes" I want to know if Goldreich's proof for this theorem misses something or not? $\endgroup$ Feb 13 at 22:24

1 Answer 1

4
$\begingroup$

Goldreich proves an "$m$-fold repetition" theorem: if $X \approx Y$ then $X^m = (X,X, \ldots, X) \approx Y^m = (Y,Y, \ldots, Y)$. In this setting, $m$ is an arbitrary polynomial function of the security parameter.

His reduction says, more or less: if $A$ can distinguish $X^m$ from $Y^m$, then consider $B$ which does the following on input $s$:

  • sample $i$ uniformly from $\{1,\ldots,m\}$,
  • sample $x_1, \ldots, x_{i-1}$ from $X$,
  • sample $y_{i+1}, \ldots, y_m$ from $Y$,
  • give $(x_1, \ldots, x_{i-1}, s, y_{i+1}, \ldots, y_m)$ to $A$

He then argues that $B$'s advantage is $1/m$ times $A$'s advantage.

Observations:

  1. The theorem Goldreich proves is not invalidated by Fischlin-Mittelbach. Indeed, they too use the $m$-fold repetition as a concrete running example for how their theorems work.

  2. Goldreich proves it by a reduction algorithm that chooses the hybrid index $i$ uniformly. This is exactly one of the recipes that Fischlin-Mittelbach propose in section 3.4. The $B$ that I described is precisely the $B$ that they describe on page 19, where transformation $T$ is the obvious thing for a $m$-fold repetition.

$\endgroup$
17
  • 2
    $\begingroup$ Fischlin-Mittelbach are giving convenient general-purpose recipes for proving statements like "if $H_i \approx H_{i+1}$ then $H_0 \approx H_n$," for totally arbitrary distributions $H_i$. Goldreich is only proving "$m$-fold repetition," a special case where $H_i = (\underbrace{X, \ldots, X}_i, Y, \ldots, Y)$. [Actually his theorem statement only cares about proving that the endpoints $H_0$ and $H_m$ are indistinguishable.] You only need one of the Fischlin-Mittelbach recipes to prove this special case. $\endgroup$
    – Mikero
    Feb 14 at 1:28
  • 2
    $\begingroup$ In summary, Goldreich proves "if $X \approx Y$ then $X^m \approx Y^m$", he proves it in maximum generality (i.e, for all $X,Y$). He does it by introducing a sequence of hybrids and reasoning about the hybrid argument in a way that is equivalent to one of the Fischlin-Mittelbach-approved methods. Fischlin-Mittelbach also give more methods, which can work even in other hybrid proofs. $\endgroup$
    – Mikero
    Feb 14 at 1:37
  • 3
    $\begingroup$ I'm sorry but I just don't know how many other ways to say that Goldreich's proof is valid and complete. Goldreich proves "If $X \approx Y$ then $X^m \approx Y^m$" -- can you give an example $X$ and $Y$ where you think his proof overlooks something? $\endgroup$
    – Mikero
    Feb 14 at 15:21
  • 1
    $\begingroup$ But that $H_i$ is not a useful sequence of hybrids for proving $m$-fold repetition, right? We don't have $H_0 = X^m$ and $H_m = Y^m$, so what does this "counterexample" have to do with proving $X^m \approx Y^m$? Why should Goldreich need to consider this kind of $H_i$? He (implicitly) introduced a different hybrid sequence with $H_i = (X, \ldots, X, Y, \ldots, Y)$ and (correctly) reasoned about it. Note that I asked you for an example of $X$ and $Y$ such that Goldreich's proof overlooks something about $X^m\approx Y^m$, not an example of an arbitrary hybrid sequence. Do you see the difference? $\endgroup$
    – Mikero
    Feb 15 at 14:14
  • 2
    $\begingroup$ Do you appreciate the distinction between the following: (A) "if for all $i$, $H_i \approx H_{i+1}$ then $H_0 \approx H_{\text{poly}(\lambda)}$; vs (B) "if $X \approx Y$ then $X^{\text{poly}(\lambda)} \approx Y^{\text{poly}(\lambda)}$ ?? (A) is not always true. (B) is a very special case of (A) where the hybrids are all "nice" -- they are all of the form $(X,\ldots,X,Y,\ldots,Y)$. (B) is always true, for all $X$. The F&M counterexample $H_i$'s don't look anything like the hybrids used in (B). Goldreich only proves (B). $\endgroup$
    – Mikero
    Feb 15 at 18:00

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.