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?
5
$\begingroup$
$\endgroup$
-
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 '17 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 '17 at 10:29
-
$\begingroup$ We want a system to work with overwhelming probability and fail with negligible probability. $\endgroup$ – user2768 Apr 18 '17 at 14:51
6
$\begingroup$
$\endgroup$
"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}}$.
