Hot answers tagged


One of the factors that determines how hard it is to forge a MAC for a given message is how long the MAC is. If it's 1 bit long, you can definitely produce the correct MAC in two tries. $2^n$ is the number of possible bit-strings of length $n$; $1/2^n$ is the probability that any random bit-string happens to be the MAC (of length $n$) for a given message ...


To be negligible is not a property of fixed numbers, it is a property of functions of some parameter. It does not make sense to talk about a probability being negligible unless you give a parameter relative to which the probability is negligible. In cryptography we will often consider probability being negligible in the security parameter of the given scheme....


Hint: you can notice that $n! > 2^n$ (except for very small $n$).


First of all, keep in mind that all meaningful probabilities must be between $0$ and $1$. In particular, this means that, if $X$ and $Y$ are probabilities, $0 \le XY \le \min(X, Y)$. In cryptography, a probability is considered "negligible" if it is very small. What actually counts as "negligible" depends on context, but typically, we're talking about ...


Yes, that is sufficient. I realise this isn't the most helpful of answers, but I'm not quite sure how we're supposed to deal with questions that lend themselves so neatly to one word answers. Certainly it seems wrong that something that has been solved should continue to sit in the 'unanswered questions' column!

Only top voted, non community-wiki answers of a minimum length are eligible