3
$\begingroup$

If i have probability $Q = 2C(A\times B)$ where $A$ and $B$ are unknown probabilities and $C$ is a non-negligible probability, what can i speculate about probability $Q$ and how can i calculate bounds on probabilities $A$ and $B$ in order to make this value non-negligible?

$\endgroup$
  • 1
    $\begingroup$ How is this related to cryptography? Seems like a straight math question. $\endgroup$ – Mike Ounsworth May 5 '15 at 15:39
  • $\begingroup$ I tried to post in math exchange but apparently the question wasn't 'formulated correctly' and I could not get it to post. It is for a crypto proof. $\endgroup$ – henry May 5 '15 at 16:52
  • $\begingroup$ I suggest you go back to math exchange and play with the markdown formatting until it posts. This will get closed here as Off Topic. $\endgroup$ – Mike Ounsworth May 5 '15 at 16:58
  • $\begingroup$ ok, thanks, ill delete it, but already spend half an hour trying to get it to post! just have to struggle away on my own... $\endgroup$ – henry May 5 '15 at 17:09
  • 4
    $\begingroup$ I'm voting to close this question as off-topic because it is not about cryptography as described in our help-center. (It seems to be more fitting for Math.SE) $\endgroup$ – e-sushi May 6 '15 at 0:24
4
$\begingroup$

First of all, keep in mind that all meaningful probabilities must be between $0$ and $1$. In particular, this means that, if $X$ and $Y$ are probabilities, $0 \le XY \le \min(X, Y)$.

In cryptography, a probability is considered "negligible" if it is very small. What actually counts as "negligible" depends on context, but typically, we're talking about probabilities on the order of $1/2^{128}$ or less.

Conversely, a "non-negligible" probability may be high, perhaps even close to $1$. In fact, since we typically want probabilities (of an attack succeeding) to be small, we may safely assume that, in the worst case, all non-negligible probabilities are $\approx 1$. This leads to the following "rules":

  • The product of two negligible probabilities is (always) negligible.

  • The product of a negligible and a non-negligible probability is also (always) negligible.

  • The product of two non-negligible probabilities is (usually) not negligible.

    • Corollary: For the product of several probabilities to be negligible, at least one of them must (usually) be negligible.
  • Multiplying a probability by a constant $\approx 1$ (say, between $1/2^{16}$ and $2^{16}$) does not (usually) change its negligibility.

  • The sum of two negligible probabilities is (usually) negligible.

  • The sum of a negligible and a non-negligible probability (or of two non-negligible probabilities) is never negligible (and might not always, strictly speaking, be a probability).

Thus, without knowing anything about $A$ and $B$, except that they are probabilities, the most we can say about $Q = 2C(AB)$ is that it is somewhere between $0$ and $2C$. Furthermore if $C$ is not negligible, then $2C$ is definitely not negligible; thus, for $Q$ to be negligible, $AB$ must (generally) be negligible.

For $AB$ to be negligible, it's sufficient for either $A$ or $B$ to be negligible. If neither $A$ nor $B$ is negligible, their product cannot be assumed to be negligible either — although it's possible for $AB$ to be negligible (e.g. $AB \approx 1/2^{128}$) even if both $A$ and $B$ are only "nearly negligible" (e.g. $A \approx B \approx 1/2^{64}$).

Conversely, for $Q = 2C(AB)$ not to be negligible, neither $A$ nor $B$ may be negligible. (Strictly speaking, for any specific threshold of negligibility, the factor of $2 > 1$ could bump a probability just below the line to just above it; but the whole point of using terms like "negligible" is to note that we're speaking loosely and usually ignoring such factors of $\approx 1$.) It's still possible for all of $A$, $B$ and $C$ to be above our negligibility threshold, but for their product to be below it (if two or more of them are "almost negligible"), but we cannot assume this without knowing their values more precisely.

$\endgroup$
  • $\begingroup$ This treatment is a little strange: I think using an asymptotic definition for negligible probabilities would lead to a more precise discussion. $\endgroup$ – Reid May 5 '15 at 19:27
  • $\begingroup$ It's weird that the sum of one nn and on n probability is nn while for this for the product does not hold. $\endgroup$ – curious May 5 '15 at 22:15
  • $\begingroup$ Negligible probability is not a fixed threshold but a function, which has to decrease faster than any polynomial. Most commonly this references to exponential decrease, but it also could be $\frac{1}{g(x)}$, where $g(x)$ is super-polynomial. If specific thresholds for probability are mentioned, most commonly $\frac{1}{2^{80}}$ is considered the upper limit of improbable. $\endgroup$ – tylo May 6 '15 at 8:59
4
$\begingroup$

To be negligible is not a property of fixed numbers, it is a property of functions of some parameter. It does not make sense to talk about a probability being negligible unless you give a parameter relative to which the probability is negligible. In cryptography we will often consider probability being negligible in the security parameter of the given scheme. So if something is stated to be negligible without specifying what it is negligible in, it is usually taken to be the security parameter.

Formally a function $f(x)$ is said to be negligible in $x$ if for all polynomials $g$ there exists a $k$ so that $|f(x')| < 1/|g(x')|$ for all $x' > k$.

Now to answer your question you first have to think of probabilities $Q$, $A$, $B$ and $C$ as functions of some parameter $x$. Now what you can say about $Q$, given that $C$ is non-negligible in $x$, is that $Q$ can only be non-negligible if both $A$ and $B$ are non-negligible.

Why? Well say $B$ is negligible in $x$. Then since $C$ and $A$ are probabilities we know they are upper-bounded by 1, so we know that $$Q(x) = 2C(x)(A(x)B(x)) \leq 2B(x)$$ Now since $B$ is negligible in $x$ for all polynomials $g$ we know there exists a $k$ so that $B(x') < 1/g(x')$ for all $x' > k$. Since $g'(x) = \frac{1}{2}g(x)$ is also a polynomial if $g$ is a polynomial we can conclude that $Q$ will also be negligible.

$\endgroup$

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.