Why use randomness in digital signature algorithms? I understand why randomness has to be employed in encryption, because deterministic ciphers are not IND-CPA. I don't understand why digital signature schemes that employ randomness, like RSA-PSS, are any better than purely deterministic ones like RSA-FDH. Isn't it still likely that RSA-FDH is EUF-CMA?

Acronyms:


IND-CPA: indistinguishable under chosen plaintext attack
RSA-FDH: Hash the message, then apply textbook RSA
RSA-PSS: Another RSA variant
EUF-CMA: Existentially unforgeable under (adaptive) chosen message attack
The main benefit of adding randomness in RSA signature padding is that it simplifies and strengthens security arguments. At least that's claimed by PKCS#1v2, paragraph above 8.1.1 (emphasis mine)


  RSASSA-PSS is different from other RSA-based signature schemes in that it is probabilistic rather than deterministic, incorporating a randomly generated salt value. The salt value enhances the security of the scheme by affording a “tighter” security proof than deterministic alternatives such as Full Domain Hashing (FDH); see [Mihir Bellare and Phillip Rogaway: The Exact Security of Digital Signatures-How to Sign with RSA and Rabin (in proceedings of Eurocrypt 1996)] for discussion. However, the randomness is not critical to security. In situations where random generation is not possible, a fixed value or a sequence number could be employed instead, with the resulting provable security similar to that of FDH [Jean-Sébastien Coron: On the Exact Security of Full Domain Hashing (in proceedings of Crypto 2000)].


De-randomization can be used to turn a randomized signature scheme (such as RSASSA-PSS of PKCS#1v2 parameterized with significant random salt) into a deterministic one: we use some CSPRNG seeded with the (hash of the) message to be signed instead of true randomness, essentially transforming the scheme into a deterministic one (similar to deterministic RSA-FDH), with a security proof. The weakness in that simple argument is that an adversary that hypothetically could get benefit of some characteristic the random portion may have, can now try messages until finding one with the corresponding pseudo-randomness having that characteristic, then obtain a signature; so quantitative security bounds on the number of signature queries (rather than any kind of oracle queries) necessary to make a forgery is not as good as with the original randomized scheme.

Update following comment: in the above I'm considering a truly secure CSPRNG, but one that is known to the attacker, which can thus run it without querying the signature-producing device/oracle. That conceivably could matter: a real-life attacker might have a low and hard limit on the number of signatures for chosen message she can obtain from a remote server, but can run the CSPRNG (and whatever other computation involving the public key) at high speed with her own CPUs.

Note: My answer above is at the hand-waving level, with no proof, rather than a precise comparison of the security of RSA-PSS and RSA-FDH for stated security criteria and hypothesis on RSA; which is complex.



While some fault-based attack (like Dan Boneh, Richard A. DeMillo, Richard J. Lipton's On the Importance of Checking Cryptographic Protocols for Faults, in proceedings of EuroCrypt 1997) indeed are blocked by a randomized message, this is an a posteriori rationalization; such attacks should be blocked by independently checking any signature produced against the public key before it is output.

Randomized rather than deterministic padding has an influence for side-channel attacks, but it is debatable that randomizing improves security; when doing some DPA attacks, a known random input is often the ideal setup (note that the padded message gets known to the adversary in any RSA signature scheme).