[rocqua]

I personally still prefer a password vault stored in the cloud combined with a strong master password.

You can quite freely backup the password vault, because pure access to it isn't the end-all-be-all. It's essentially a second factor.

I'd also like to compare this to a simpler challenge-response based protocol. Have the shared secret be e.g. SS = scrypt(hmac(passwd, serviceID)), and the challenge be nonce, to which one should respond hmac(SS, nonce).

The biggest difference I see is the issue of leaking the shared secret. It doesn't leak anything about the passwd, but compromises access to the service. If your public key leaks, that still can't be used to authenticate you with the service. If I'm not mistaken, the shared secret approach has the advantage of better privacy.