I found the term "overwhelming" when I study cryptography.

According to the definition, we call $f$ overwhelming if $1-f$ is negligible.

I already know the negligible function and its way to use but I don't understand why we consider the overwhelming function.
Can someone teach me how to use it and some examples?

  • 2
    $\begingroup$ IIRC we don't always want to guarantee that cryptosystems are functionally correct with probability 1 which is when we them to work with overwhelming probability / fail with negligible probability. $\endgroup$
    – SEJPM
    Apr 18, 2017 at 8:45
  • $\begingroup$ An example could be the correctness of decryption: in certain encryption schemes (e.g. most lattice based schemes) we have a negligible probability of decryption error, i.e., a ciphertext may not decrypt to the correct message. So we say the scheme decrypts correctly with "overwhelming" probability. "Overwhelming" is essentially just a convenient way to say "with probability 1-f, for a negligible function f". $\endgroup$
    – Guut Boy
    Apr 18, 2017 at 10:29
  • $\begingroup$ We want a system to work with overwhelming probability and fail with negligible probability. $\endgroup$
    – user2768
    Apr 18, 2017 at 14:51

1 Answer 1


"With overwhelming probability" means that an event happens with probability at least $1−2^{Ω(n^\varepsilon)}$ for a constant $\varepsilon >0$.

Example: In a public key cryptosystem where $\mathcal{PK}$, $\mathcal{SK}$ and $\mathcal{R}$ are the spaces of public keys, secret keys, and sender randomness respectively, if $∆_{\mathcal{R}}$ denote the distribution on $\mathcal{R}$, then we require the usual correctness condition: for all $pk ∈ \mathcal{PK}$, all $sk ∈ \mathcal{SK}$, and $b ∈ \{0, 1\}$, we have $Dec_{sk}(Enc_{pk}(b; r)) = b$ with overwhelming probability over $r ← ∆_{\mathcal{R}}$.

  • $\begingroup$ Thanks for your answer, but how do you define $\Omega(m)$ for a positive real number $m$? I see that you used it for $m:= n^{\epsilon}$. TIA! $\endgroup$
    – Mathmath
    Mar 17, 2020 at 23:45

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.