5
$\begingroup$

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?

$\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$

"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}}$.

$\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.