So do you think that multisig or Shamir's would solve the issue (as I am not clear how you could ever create a *perfect* system - maybe such a thing is not actually possible)?
I haven't looked into those yet. The best solution I can imagine so far would be a combination of the following:
1.) Deterministic choice of k given a certain Standard (RFC6979 or maybe EdDSA's way of doing it)
2.) Zero-knowledge proof of the fact that k has indeed been chosen according to the procedure.
This would be perfectly possible, as the statement there exists an skey such that: k equals H(skey||message||salt) and pubkey equals generator point multiplied by skey obviously is an NP statement and there exist non-interactive zero-knowledge proofs for any NP statement.
Note that this would not change anything for the Bitcoin protocol. The proof is just for the user himself to verify that his wallet is working properly, it does not have to be sent into the Bitcoin network.
But a new problem arises: How to implement the proof in a way that ensures that we don't create new side channels for leakage?