Why are MACs in general deterministic, whereas digital signature constructions are randomized?

Question

The fact is I'm not quite sure if my question statement is true, however all the MAC constructions I know of (e.g. CBC-MAC, CMAC, HMAC) are deterministic, whereas many constructions for digital signature are randomized (e.g. DSA, ECDSA, RSASSA-PSS). I also know that RSASSA-PKCS1.5 is deterministic but still considered secure (though not recommended in favor of RSASSA-PSS).

• Why is it the case that most MACs are deterministic whereas most digital signature schemes are randomized? Are there randomized MACs that I simply don't know about, and do they provide any advantages over the deterministic approach? Is there some fundamental difference between MACs and digital signatures that makes the randomization more desirable (but still not required) for signatures?

• Are there randomized constructions for MACs or digital signatures that breaks badly if the randomizer output is not indistinguishable from random, or do they all simply reduce to a still secure deterministic scheme?

Answer 1

One rationale for avoiding randomized schemes in general, and in MACs in particular, is that the random in such schemes tends to increases the size of cryptograms or reduce the size of the payload. An example is scheme 2 in ISO/IEC 9796-2 RSA signature with message recovery, where the size of the random/salt field is directly antagonist with the amount of data recoverable from a signature.

Also, a randomized scheme typically opens a "subliminal channel" backdoor that can't be detected in a black-box testing of an implementation, and could funnel out sensitive information. E.g an RSA (SSA-PSS or ISO/IEC 9796-2 scheme 2) signature blackbox could leak a factor of the private key, CBC-encrypted with random IV and a backdoor-key in the field supposed to be random.

Given that MACs do not seem to need to be randomized to be secure, the above is reason enough that most MACs are deterministic in their definition. Notice however that in practice, the MACed message itself often contains a random component, or/and that (in order to resist side-channel attacks on implementations) the key could be a random session key, in effect randomizing the MAC.

If the random source in a randomized digital signature scheme is bad, that often weakens the scheme. The best example might be [EC]DSA and the PS3 signature fiasco, see this, including comment #2.