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.

We don't even really need a hash function for generating coefficients.  All we really need is some way to map a child index to a vector of coefficients in such a way that two distinct child indices are unlikely to map to the same coefficients.  Even if the coefficients are completely predictable, an adversary still has the problem of solving a system of t
This "flat" scheme is dumb anyway.  It really only applies when the master public keys are public knowledge, since they're always needed to generate descendants.  (Previous post edited to include this fact.)  In that case, all HD wallet trees are equivalent to a single-level tree in the sense that there's no significant difference between a depth-three child m/x/y/z and a depth-one child m/(xyz) where (xyz) is some way of encoding the three indices x,y,z into a single index.  (Hence the name "flat".)  In order for a multi-level hierarchy to be functionally distinct from a single-level hierarchy you need the property that each subtree can pretend to be its own separate tree and doesn't need to know anything about its ancestors (ie. the master public keys are no longer public knowledge).  But the "flat" scheme doesn't have this property.  I shouldn't have mentioned it.

You're right.  That was a mistake on my part.  Sorry about that.  (Unfortunately, anyone who ever reads this thread forever after now needs to skim through that piece of stupidity.  That's the problem with fora.  Grr...)

What I said works if you reveal only the public keys for M/"0", M/"1", etc but not the private keys m/"0", m/"1".  If you want a multi-level hierarchy in the treasurer use case (in which everyone in the corporate ladder gets a private key) with this wallet then I see two options:

• [This point edited a bit after posting.]  If the master public keys are public knowledge anyway then you could just implement a "flat" or "simulated" hierarchy, meaning that the key m/x/y/z is a linear combination of the original n master keys d₁,...,d_n where the coefficients are derived from the hash of (x,y,z).  Note that a total of no more than n-1 private keys can be revealed from anywhere in the hierarchy.  That might seem bad but it's still an improvement on BIP32, where any one (non-hardened) private key from anywhere in the hierarchy can be combined with the master public key to break the wallet.
  
• If you really want to give each child a,b,c,... ability to reveal up to n_a,n_b,n_c,... private keys then you need at least 1+n_a+n_b+n_c+... master private keys.  This isn't a problem if you're the top-level admin because you can generate the private keys deterministically.  But if you're an auditor (who is only allowed to know the master public keys and needs to store them explicitly) then you could run into an exponential blow-up of public key size: if you want each node in a k-ary tree of depth d to be able to reveal up to n keys then you need something like (kn)^O(d) master keys.

Short answer: Every key, no matter where in the hierarchy, is ultimately a linear combination of the m master keys.  Thus, a total of m keys gathered from anywhere in the hierarchy is enough to break the wallet.

Less-short answer: We didn't even bother to explicitly define how one generates descendant keys beyond the first level.  One straightforward way to do it is as follows.  (m is overloaded; let n be the number of master keys.)  The first n child keys m/0 through m/n-1 are designated as the "master" keys for m/"0", the subsequent n child keys m/n through m/2n-1 are "master" keys for m/"1" and so on recursively.  So, for example, m/"0"/0 and m/"1"/0 are both linear combinations of the original n master keys d₁,...,d_n.

Thanks everyone for the comments.  It's great to receive such high quality feedback so promptly!  It's easier for me to post responses one at a time.  Here goes.


I certainly agree that

• You would need to be very careful applying this scheme for the purpose of fault tolerance.
• The wallet's utility is limited by the fact that you need to commit at the wallet's inception to a maximum amount of leak you're willing to tolerate over the life of the wallet.

But at the very least, you could protect against a one-off, black-swan event that leaks only a fixed number of keys.  It forces an attacker to compromise a bunch of keys---not just one.

Don't forget that there could be other uses of this wallet aside from fault tolerance (which admittedly isn't a killer app).  The treasurer-auditor is one, but I couldn't think of any others.

I'll reply to the second part of your comment later.  Cheers.

Douglas Stebila and I recently posted a new paper on hierarchical deterministic wallets:
http://eprint.iacr.org/2014/998
(To appear in Financial Cryptography 2015.)

Custom summary for bitcointalk.org

---

As observed by Vitalik and many others, it is possible to recover the master private key of a BIP32-compliant wallet from the mater public key and any (non-hardened) child private key.  From what I gather, many people think that this vulnerability is unavoidable.  However, we came up with a HD wallet that is secure even if up to m-1 child private keys are leaked at a cost of storing m master public keys, for any choice of m.

How it works:
Instead of one master private and public key we have m master private keys d₁,...,d_m and public keys Q₁,...,Q_m.  (The master private keys can be derived deterministically, so there's no need to store all m of them, but the master public keys must be stored explicitly.)  The ith child public key is a linear combination of the Q_i where the coefficients are determined by the hash of i (possibly concatenated with some seed, which may or may not include wallet-specific info such as the Q_i.)  The ith child private key is derived similarly from the d_i.

Security:
Anyone who can recover all m of the master private keys---even with knowledge of up to m-1 master or child private keys---can also solve the so-called "one more" discrete log problem.  Since that problem is believed to be intractable, so too must be the task of breaking our wallet.  See the paper for further details and caveats.

At an intuitive level, an adversary who learns any one master or child private key has learned only a linear combination of the m master private keys, which reduces the dimension of the space of all possible master private key combinations by at most one, and so m such keys are required to break the wallet.

Fallout:
Admittedly, this is not an earth-shattering discovery.  But it does enable a combined treasurer-auditor use case that is impossible with BIP32 wallets:

Auditor:  A company could reveal its master public key to auditors or regulators, thereby allowing for extremely detailed oversight with near-negligible overhead costs.
Treasurer:  The treasurer of a large company could create child key pairs for each department within the company, allowing each department head to control its budget without granting him/her access to the funds allocated to other departments.

With BIP32 wallets, a collusion between the auditor and a department manager could run off with all the company’s funds.  Our new HD wallet eliminates this vulnerability provided that the number m of master keys exceeds the number t of departments in the company.

Thanks for your attention.  Cheers.
-Gus Gutoski