# What does "overwhelming" mean in cryptography?

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?

• 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.
– SEJPM
Apr 18 '17 at 8:45
• 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". Apr 18 '17 at 10:29
• We want a system to work with overwhelming probability and fail with negligible probability. Apr 18 '17 at 14:51

"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}}$.
• 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! Mar 17 '20 at 23:45