Re: New HD wallet that tolerates leakage of some child private keys
Your security argument rests on 1MDLP, but we actually use these keys in the context of ECDSA. Inability to solve the DLP (or 1MDLP) does not provably result in the security of ECDSA, and ECDSA reveals another (random) linear relationship with the keys in question; it's concealable that it could undermine the security of the scheme. For example, imagine if the nonce were secrete but constant. Off the cuff, I do not see a reason that this is problematic for the security of your construction. Though in an abundance of caution we specifically constructed BIP32 to avoid constant any linear relationship out of concern for potential interactions with ECDSA which we were unable to prove did not exist.
If I understand correctly, you're worried about some problem introduced by the confluence of the facts that (i) our child private keys are constructed by linear combinations of the master private keys, and (ii) each ECDSA signature reveals a linear equation involving the private key. But, as you say, the information revealed in an ECDSA signature is masked by the random nonce so it's hard to see how this could be a problem. And if the nonce is "secret but constant" than you're screwed anyway.
What we do have is that recovering the wallet's signing keys without access to any signatures is as hard as the 1MDLP for elliptic curves.
Other than that, I'm not sure how to respond. This concern could apply to any use of ECDSA in which the keys are not truly random. I guess in order to address it one would need to prove a general reduction from cracking ECDSA with arbitrary keys to cracking ECDSA with constraints on key selection.
Thanks! Thanks again to everyone for the feedback. It's a shame we didn't get your feedback back when this paper was under review. I guess in the future we should post to bitcointalk.org before submitting.
