Robust digital signature revisited

In CT-RSA 2019, Geraud, Naccache and Rosie introduced the notion of robustness (ROB) for digital signature schemes to guarantee that the same signature and message pair cannot be valid under two different public keys. Their definition of complete ROB (CROB) can even support the ROB when the keys are malignantly generated. Motivated by the fact that the signature and the key could be illegally produced in some circumstances, we extended the ROB security one step further to guarantee that one valid signature cannot be modified to another valid signature under a different public key, which we call extreme robustness (EXROB). After analysing the relations between the EXROB security and existing ROB related definitions, we describe generic constructions to convert any digital signature scheme that is unforgeable into an EXROB secure one. Our hash-then-sign construction is very efficient, which only adds one hash calculation to the underlying digital signature scheme and does not increase the size of the signature generated by the underlying digital signature scheme.