Deterministic Digital Signature Algorithms
A gentle introduction to what makes a digital signature and how to make it deterministic:
In practice we see a need for caution and care around the commitment part of a signature. If the commitment secret is duplicated for different messages, then the signing key secret for that key can be recovered. When an attacker holds the key, they may impersonate the honest key holder and defeat the security of the scheme that relies upon that authenticity.
The security of a signature scheme requires that all commitment secrets be unique (at least as far as distinct messages go). One way to do this is to record information that changes over time, called state. It could be a counter or a collection of all previously issued commitments. Unfortunately, state in this scenario requires consistency for any application that holds the private key. Also, maintaining a set of all commitments that can be efficiently searched is difficult at scale. An alternative is to partition counters such that each signer has a reserved counter space, so other signers will not accidentally duplicate commitment secrets that will collide.
Instead, we have a cryptographic tool which is collision-resistant. Cryptographic hashes or message digests exist to fill the role of what is called a "random oracle." In computer science theory, an oracle is something that gives an answer, and a random oracle gives a random answer which has never been seen before. Replying with a pre-existing signature does not reveal more information about the secret key. By definition something that has never been seen before cannot collide with previous answers.
We deem a hash function as broken when a collision is found. MD5 is easily broken, and SHA-1 (see shattered) can be broken with sufficient money and server time.
To create a deterministic commitment secret with a hash function, we need to maintain one important requirement: the hash digest used to create the commitment secret must be unguessable. Also, the public form of the commitment which goes into the signature should not reveal the commitment secret.
Ed25519 uses the message and part of a SHA-512 hash of the signing secret key to create a deterministic commitment secret and then the commitment is made from that commitment secret. Because secret bits of sufficient entropy were added to the hash of the message, it is too difficult to guess or reverse what the commitment secret is.
Deterministic ECDSA (RFC6979) uses a unique approach to probe for safe commitment secrets using HMACs. The message and signing secret key are mixed together with HMACs to create a possible commitment secret. If the commitment secret is unsatisfactory, it probes for another value with a deterministic algorithm. For example, a commitment secret of all 0’s is unsatisfactory.
A deterministic commitment secret protects the secret signing key from being recovered. This protection relies on the collision resistance property we get from cryptographic hashes. Besides key generation, the commitment secret generation part of digital signatures is the only probabilistic part of creating a signature. By replacing the commitment secret probabilistic process with a deterministic process, the complete signature process for a pre-existing key becomes deterministic.
Deterministic signatures remove the risk of exposing a secret signing key when commitment secrets could be misused. This provides a defense against application developer ignorance (like Sony) and poor randomness from the environment (like some transactions on the blockchain).