What does "with all but negligible probability" mean? I have met the sentence that something will happen "with all but negligible probability" in the paper "Homomorphic Signatures for Polynomial Functions". However, I cannot quite figure out what exactly they mean by this. I know the definition of something happening with negligible probability, it is the "all but" that throws me off. In the paper they are referencing, it is described that it happens with probability $1-2^{-\Omega(n)}$, so I figure this must be the definition of it happening with all but negligible probability? However, I do not know what they mean by $\Omega(n)$, and I cannot seem to find the definition in the paper. Can someone perhaps clean things up for me?
$\Omega(n)$ is a mathematical notation from the same family that the notation $O(n)$ comes from.

To review, $O(n)$ is bounded from above; that is, if we say that $f(n) = O(g(n))$, what we're actually saying is that, for all sufficiently large $n$, there exists a constant $c &gt; 0$ such that $f(n) &lt; c \cdot g(n)$, that is, $f(n)$ grows no faster than $g(n)$.

$\Omega(n)$ is the same, except that it is bounded from below; that is, if we say that $f(n) = \Omega(g(n))$, then (for all sufficiently large $n$) there exists a constant $c &gt; 0$ such that $f(n) &gt; c \cdot g(n)$, that is, $f(n)$ grows at least as fast as $g(n)$.

Hence, what they mean when they say $1 - 2^{-\Omega(n)}$, there's a constant $c$ such that the probability of success is always $&gt; 1 - 2^{-cn}$ (except for possibly small $n$); hence, for large $n$, the probability is quite high (however, that doesn't say what "large" means in this context :-)

In case you're wondering, from the same family, we also have "little-oh" notation $f(n) = o(g(n))$ ("f grows strictly slower than g"), little-omega notation $f(n) = \omega(g(n))$ ("f grows strictly faster than g") and theta notation $f(n) = \Theta(g(n)))$ ("f grows as fast as g, within multiplicative upper and lower bounds")