Topic: New HD wallet that tolerates leakage of some child private keys - page 2. (Read 3935 times)

Thanks for explanation... I get it and agree.

I jumped the gun and was thinking it would
protect a lot more leakage.  My initial comment
was referring to the fact that people have
expressed desire for higher security when
sharing a public key for auditing purposes.

That isn't as large of a limitation as you might be thinking, at least not in most applications.  The hardened keys are used to produce the major "branches" and then unhardened keys are used to leafs.  There aren't many scenarios where you would compromise just a few but not too many of the leaf keys AND not also compromise the parent (branch) key at the same time.   Still the OP is an interesting academic concept but I agree with gmaxwell in that scenarios where it would provide additional security is limited.

hi DT!

Yes, I was aware of that; I did read the paper and
this appears to be relevant:

That is not correct in all scenarios.  Private keys can either be hardened or normal.  Hardened private keys can not leak the parent key.    Even with unhardened private keys the leak of the key alone is insufficient to leak the parent as well.  You need to leak a child private key AND parent public key to compromise the parent private key.

Clearly, the use cases presented in the paper are compelling.

I don't fully understand your question due to a lack
of technical expertise, but it sounds like
you are saying the leakage would still be too great
to be practical?

The paper says:


My understanding was that there was until now,
zero tolerance of any leakage of private keys
in an HD.  If that is incorrect or there
are better ways to do it, please clarify.

Can you please help me understand how this would be useful in practice? The amount of tolerated leak is linear in the size of the scriptpubkey. Just giving a party random address also achieves that. Using the homomorphic derivation is attractive for cases where the linear size is not acceptable.

Excellent idea!  People have asked about this kind
of thing in the past.  The use-case is really important
for the future of Bitcoin.

I'm a bit confused in your paper, in the description of your wallet, because d is used to represent master private keys and child private keys.

I can't figure out if this is a new hd wallet or just lots of old hd wallets that would each, individually, be susceptible to the same attacks that you are trying to avoid?

EDIT sorry, I've got bad eyesight, I missed the hat on top of the letter, I'll read it again and see if I can understand it

https://bitcointalksearch.org/topic/a-failed-solution-to-a-collusion-flaw-in-deterministic-wallets-819424

related proposal

Would your method be compromised if only, say, m/0/0 and m/1/0 private keys were known?

Perhaps the 1 leaked key protected methodology would be good if we could separate each used key below it's own path (not sharing the same direct parent with any other generated key)

This is explicitly called out in the specification, it is not folkore or a revelation.

Very interesting observation!

Though it's arguably more fragile in one sense that you may think you can release a private key securely but really you cannot because if you leak too much you are broken. It's difficult to write software which will only act a small non-zero number of times e.g. it crashes and forgets that it's already performed one disclosure, certainly the user cannot be counted on to remember such things.  So I think it would be an obvious improvement and might well be worth an increase in the resulting master public key size just for additional robustness, I don't know that in practise it would safely permit intentional use of it.

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.

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