The Republic of Brutopia are updating the design of their library cards with a new security feature: a 2D barcode containing a cryptographically signed copy of the human-readable fields on the card. This will allow anyone to verify that a card is genuine and has not been tampered with.
Unfortunately, the library card is the principal form of government-issued ID in Brutopia. You'll probably show yours to almost-random strangers several times a day, whether you want to buy beer, open a bank account, or pick up a package at the post office. And now civil rights advocates and conspiracy theorists alike are up in arms about the privacy implications of using the new barcoded cards for that. Who can really know if the barcode only contains the data about you that you can see for yourself on the face of the card?
It didn't help the government that they published full specifications for the barcode content, including a DSA signature at the end. The critics pointed out that a DSA signature contains an ostensibly-random nonce, and there is no way you can check that it is really all random and doesn't secretly code for personally identifiable data.
It appears that what the government needs is to use something else than DSA for signing the cards. As far as I can make out, what we would ideally want here is a public-key signature scheme with the additional property that
It should be infeasible to construct a valid public key $K_p$, a message $M$, and two different signatures $S_1$ and $S_2$ such that $S_1$ and $S_2$ are both valid signatures for $M$ under key $K_p$.
Does this property (or something like it) have a name?
And are there generally accepted signature schemes that provide this?
Naively I would expect that RSA, with the input being a hash of the message, padded to the modulus length in some deterministic way, might work -- but apparently best practice is always to use some random padding when using RSA for anything, so I'm not sure whether that would be vulnerable somehow.