Let $\lambda$ be a statistical security parameter. Consider a security proof that is based on hybrid argument, where there are polynomially many (say, $n = p(\lambda)$) hybrids, $H_1, ..., H_n$. Any two hybrids $H_i$ and $H_{i + 1}$ can only be efficiently distinguished with probability $2^{-\lambda}$. So, by iterating through all the hybrids, it seems to me that the probability that $H_1$ and $H_n$ can be efficiently distinguished is bounded by $(p(\lambda) - 1) \cdot 2^{-\lambda}$ using union bound. Asymptotically, this probability is negligible in $\lambda$.

My question is that, when $n = p(\lambda)$ is polynomially bounded with respect to $\lambda$ but not known, it seems impossible to choose a reasonable $\lambda$ such that $(p(\lambda) - 1) \cdot 2^{-\lambda}$ is sufficiently small (e.g., $< 2^{-40}$). I think that the same issue may exist as well when it comes to some computational security parameter $\kappa$. It would be appreciated if someone could give me any hint on this question. Many thanks.

  • $\begingroup$ I don't think I would call that an application of the union bound. The event of distinguishing between the extreme hybrids is not the union of distinguishing between the intermediates. It simply follows from the triangle inequality instead. In general, if you only have an asymptotic guarantee for the size of $n$ you cannot deduce a concrete bound from it. Where does the bound on $n$ come from in your case? $\endgroup$
    – Maeher
    Commented Oct 5, 2020 at 9:18
  • $\begingroup$ @Maeher, the number of hybrids comes from the number of random strings contained in $H_0$. $H_{i + 1}$ is identical to $H_i$ except that one of the random strings is replaced by the output of a PPT algorithm $A$. For example, consider the security proof of garbled circuit using hybrid argument (with respect to some computational security parameter $\kappa$, although). The number of random strings is asymptotically indentical to the number of garbled gates. So, what confuses me is that, in this case, is the security of garbled circuit paradigm dependent on the size of circuit? $\endgroup$
    – X. G.
    Commented Oct 5, 2020 at 9:34

1 Answer 1


a function "polynomially bounded" means there exists $d\in \mathbb{N}$ such taht $f(\lambda)\leq \lambda^d$ asymptotically. You don't have to know $f$, but if you want to bound the advantage of your adversary asymptotically, you have to know a such $d$ which verifies this inequality.

If you don't, then you can't deduce anything. But in general, if you look the proof in details what is $n$, and why it has been claimed polynomially bounded, it's easy to find a such $d$, such that $n\leq \lambda^d$ asymptotically.

  • $\begingroup$ It is generally not true that an explicit bound can "easily be found". $n$ could depend on adversarial behavior, such as $n$ being the number of queries issued by an adversary. In such a case we cannot deduce any fixed bound on $n$. $\endgroup$
    – Maeher
    Commented Oct 5, 2020 at 9:14
  • $\begingroup$ I don't understand your point, give an example please. $\endgroup$
    – Ievgeni
    Commented Oct 5, 2020 at 9:19

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.