Probabilistic polynomial time algorithms in MAC's

Question

According to the Wiki article, a MAC is a triple of probabilistic polynomial time algorithms $(G, S, V)$ such that:

• G gives the key k on input 1^n, where n is the security parameter
• S outputs a tag on the key k and the input string x
• V outputs 'accepted' or 'rejected' on inputs: the key k, the string x and the tag t.

From my understanding, a probabilistic polynomial time algorithm is one that runs in polynomial time, and returns a probability.

I don't really see how the outputs of G, S and V count as 'probabilities'. What are they measuring the probability of?

Answer 1

From my understanding, a probabilistic polynomial time algorithm is one that runs in polynomial time, and returns a probability.

Sadly, no. A probabilistic polynomial time algorithm is an algorithm that runs in polynomial time and may use (true) randomness to produce (possibly) non-deterministic results.
The "probabilistic" in the name comes from the fact that one can only predict certain outcomes with a certain probability. For example an algorithm that takes no input and simulates a coin-flip, would be such a probabilistic algorithm, as it's not sure (before evaluation) what the outcome will be, either head or tail?

---

In the concrete situation, only the key-generating algorithm must be probabilisitc (i.e. use randomness).
The tag-generating algorithm may use randomness but may also decide not to, HMAC for example is deterministic, while other MACs may not be. In either case, saying they are "probabilistic" doesn't hurt and gives the algorithms more freedom.
The verification algorithm on the other hand, must be fully-deterministic as you always want the right answer to the question "is this tag valid in this context?". However, it's still a probabilistic algorithm that just happens to never use the randomness it is allowed to use.