If we did not use a hash function, or if we could assume that there exist no collisions in the hash function, are the signatures generated by a (generic digital signature scheme) guaranteed to be unique?
In general no, there is not a single signature for a given message (or hash) for a general definition of digital signature. Many signature schemes are randomized, including ECDSA and DSA: signing the same message twice will (most often) generate different signatures.
(..) ECDSA does not provide "strong existential unforgeability" because "if $(r,s)$ is a valid signature for some message, then the different $(r,n-s)$ also is valid for the same message." To me, it sounds like this that signatures are not unique (at least under ECDSA).
Yes this implies the signature is not unique, but it tells something more: that it's possible to turn a signature into a different signature valid for the same message (and hash), without knowledge of the private key. It should be distinguished two criteria:
- Deterministic signature (versus not): deterministic means the legitimate signer always generates the same signature. Randomized implies not deterministic (and strictly speaking means that even knowledge of the private key and history of the signatures made does not allow to predict the next signature).
- Strong qualifier to existential unforgeability (versus mere existential unforgeability): that tells it's impossible to exhibit a (message, signature) pair that verifies and where signature is not the signature produced by the signer for this message. Compare to mere existential unforgeability, that tells it's impossible to exhibit a (message, signature) pair that verifies and where the signer did not sign this message.
Some signature schemes are such that a single signature can verify for a given message and hash, which (assuming existential unforgeability) implies 1 and 2. Example: strict implementation of RSASSA-PKCS1-v1_5.
For other signature schemes (that is such that the holder of the private key is able to produce different signatures for the same message and hash), the four combinations resulting from the criteria 1/2 above are possible, with at least the first three common:
- Deterministic signature with strong existential unforgeability: EdDSA
- Randomized (thus non-deterministic) signature with strong existential unforgeability: RSASSA-PSS, DSA.
- Randomized (thus non-deterministic) signature with mere existential unforgeability: ECDSA.
- Deterministic signature with mere existential unforgeability: ECDSA modified by using a CSPRNG keyed with a hash of the message and the private key, instead of a true RNG.