I am trying to figure out if there is a known construction of a post quantum secure EUF-CMA secure signature scheme for which the signature procedure is deterministic.
It seems that it is possible to "determinize" a randomized signature scheme which uses a bounded amount of randomness by means of a post quantum PRF: sample a key k for the PRF and attach it to the private key of the signature scheme. When signing a message m use PRF_k(m) instead of the random bits. It seems this could be also extended to general randomness with standard arguments (e.g. use PRF_k(m), PRF_k(m+1) etc. to generate sufficiently many random bits).
Intuitively it seems to me that if the original scheme is strong EUF-CMA secure than so should be the resulting scheme (since statistical difference in the views of the same adversary in the security games of the two schemes seems to imply a distinguisher between the PRF and a truly random function).
It also seems that it might be easy to transform a deterministic weak EUF-CMA secure scheme to a strong one by means of cryptographic hash functions: attach the hash of the signature to the signature. This will make render signature that the verification procedure might have accepted even though they weren't created by the signing procedure invalid, as long as the adversary is unable to find a collision in the hash function.
Are these intuitions solid, or am I missing a crucial subtlety? More importantly, do they already appear somewhere in the literature? I couldn't find anything useful.
