Dear ZmnSCPxj,

> I think it would be unsafe to use a deterministic scheme, that takes as
input the message m and the privkey only.

Yes, using only the message and the private key is unsafe. Signer should
use all the data coming from the host, so f(sha256(n), m, privkey) is a
good candidate. If more than one blinding factor is sent - all of them
should be used as well.

> Otherwise a completely-random `k` would be much better, but the signer
might not have enough resources to gather sufficient entropy.

I am not a big fan of pure RNG-generated nonces, so I would suggest to use
this entropy only as additional data for a deterministic scheme.
For example, Yubikey had a problem with RNG initialization that caused
leakage of the private key [1].
If the signer has any source of entropy, even if it is not a very good one,
the entropy from this source can be mixed into the nonce generation
function:
f(sha256(n),m,privkey,entropy).

Another issue is that deterministic nonce generation is vulnerable to
glitch attacks - if I ask the wallet to sign the same message twice but
after nonce generation I glitch and flip a bit in the message, I will get
two signatures with the same nonce but with different messages - from these
signatures I can calculate the private key.
So I would recommend to include a monotonic counter into the nonce
generation function as well: f(sha256(n), m, privkey, entropy, counter)
As usual, counter should be increased _before_ signing.

Ref: [1]
https://www.yubico.com/support/security-advisories/ysa-2019-02/#technical-details

Best,
Stepan