Can a Deterministic Signature Algorithm be paired with a Probabilistic Encoding Method? I'm working with a C++ library and I’m currently investigating the changes needed to accommodate Deterministic DSA and ECDSA Signatures (RFC 6979). While the RFC 6979 changes are specific, I'm trying to understand more about the breadth of the potential changes to some of C++ classes involved in the implementation.

Is it possible to pair a “Discrete Log/ElGamal”-alike signature scheme (like – for example – DSA/ECDSA), adorn it with determinism (the deterministic $k$), and then pair it with an encoding method which uses randomness (maybe like something found in a PSS, perhaps with a salt)?

I realize RSA-PSS is a different class of signature schemes. I'm less clear or some of the unique or unusual pairings that may be experienced in the field with lesser known schemes.

This question on pairing primitives is about extensibility planning in software. It leaves open the mathematical questions of correctness and proofs. We often have to ask a theoretical crypto question here to ensure the cryptography is well represented, even though it could be off-topic.



Here's a question that touches on similar: Why use randomness in digital signature algorithms?


  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 ...
First, some clarifications.

A randomised signature scheme is a signature scheme that produces randomised signatures, that is, if you sign the same message twice, you are not likely to get the same signature twice.

We can "derandomise" a signature scheme by replacing the randomness with pseudo-randomness generated as a function of the messaget to be signed and a secret key. The result is a deterministic signature scheme, where if you sign the same message twice, you will get the same pseudo-randomness and therefore the same signature. If the randomised scheme was secure and the derandomising was done correctly, the deterministic scheme will also be secure.

A padding scheme is a way to encode messages in one "format" as messages of a different "format", typically arbitrary bit strings as bit strings of length divisible by some number, or short bit strings as long numbers, or ... Usually, these schemes are in some sense injective, in that if you encode two distinct messages, you never get the same padded message.

A randomised padding scheme is a padding scheme that if you encode the same message twice, you are not likely to get the same padded message twice. Such schemes can sometimes be used to turn certain somewhat insecure signature schemes into secure signature schemes, typically by turning the message to be signed into a random-looking message that can be safely signed by the insecure scheme.

Now, the answer: Given the way we define "secure signature scheme", composing a secure signature scheme with any padding scheme cannot result in an insecure scheme (just a pointless scheme). So:


Derandomising DSA results in a deterministic signature scheme.
Since we believe DSA is secure, derandomised DSA should also be secure.
Since we believe derandomised DSA is secure, derandomised DSA composed with a padding scheme like PSS should also be secure (but pointless).


So the answer to your question appears to be yes.

However, one caveat. DSA involves a hash function: you hash the message and then the hash is included in some number-theoretic computations that results in a signature. The hash is an integral part of DSA. If you replace the hash with (say) PSS, you have not composed a secure signature scheme with a padding scheme, but modified a secure scheme. And when you modify schemes, the composition result I mentioned does not apply, and you may end up with something insecure.