Gavin, I looked at the papers Bytecoin cited, to see if it is worth effort implementing this.

Especially the first paper is very intersting. I agree that it should be possible to adapt the two zero knowledge proof parts from the Paillier crypto system (for which the paper gives a solution) to elliptic. Moreover, it probably involves quite a bit of thinking and implementing; it's not really as straight forward as it may seem.

Therefore, I spent a few hours analyzing the situation. I think that splitting private keys in the form you describe in your first post is the right direction but not really what we want. Let me first outline some problems I see with your approach and then provide an amendment to your thoughts.

Risk of loss: Suppose, we lose one of the two devices. Then we have lost our money, since we no longer can form the requested signature. Thus, while we gain more security against attackers, the burden on backup gets higher: We now have to backup two devices and we should do this after every generation of new keys. Lose your laptop, drop you mobile on the floor: Your money is gone. Two devices - double risk.

Burden of key-splitting: Every time we generate a new key, the two devices must synchronize, for the scheme to work. So: When generating a new bitcoin address, I need a new PAIR of private keys, which requires an activity on both devices. If you only have one device with you on generation time, you have got bad luck.

Usability: Looks like I always have to have both devices on me when using Bitcoin. Sometimes I will not. So I might end up having some small cash on some addresses which are only on one device. Or the other. And only the addresses with the big money are secured by secret splitting. Which may lead to user confusion and a hassle when trying to get the devices synchronized.

Mobility: Right now, BTC is a desktop application. It will become a mobile application. Fine. So will i need two mobile devices in that scheme, when I am having my beer in bitcoin bar? One could be a mobile phone. And the second? Smartcard? USB token? Second phone? How useful are two devices for a mobile solution?


Currently, I see two ways out of most problems: A cryptographical one (using a different crypto scheme) and an operational one.

Cryptographical idea: We do not want private key splitting, we want more. We want a threshold scheme with proactive sharing (and, if possible, verifiability). This means:

Threshold: We split keys not into two but into a larger number. For example: Five. (Desktop PC at work, desktop PC at home, mobile phone, smart card, USB token). We impose a threshold. For example: Two devices together can produce a valid signature. This solves the backup issue. Lose one device, you still have four left. I think, this threshold concept if a major improvement of the backup situation.

We have to modify the life-cycle of the keys, of course, to solve the other issues mentioned above. No small pools any longer, but 1.000 keys or more which are generated at the beginning. So we do not have to distribute fresh key shares so often.

Proactive sharing comes into the game, when we lose one of the devices. In this case, we want to disable the keys as fast as possible (before the attacker manages to steal a second of our devices). Proactive secret sharing allows us to redistribute the shares in such a manner, that compromised shares lose their value for the attacker.

Verifiability comes into the game, when one of devices is not lost but compromised or defective. It allows the other sharing participants to check if a sharing participant lies about his share (but, of course, without learning anything about the share).

For elliptic crypto and DSA, there exist threshold based signature schemes. I am currently researching, if there are proactive schemes (I assume, yes) or verifiable schemes (I do not know).

This concept should work without touching anything on Bitcoin crypto - we only add a wallet client.

Organizational idea: We do not split at the wallet private key level, but at the level of the user.

Our wallet is handled by a secure and trustworthy organization or node. We tell that organization or node using secret splitting schemes as outlined above, when they are supposed to use the wallet keys on our behalf. The node might be a pluggable PC such as openplug.org running out of my home (with a backup of the keys stored somewhere). The activating devices then are a smartcard to be put into any card reader and a mobile phone. These two devices would not have to use Bitcoin elliptic crypto but just ANY existing key sharing scheme (which is much easier to do). Again, Bitcoin client does not have to be modified.

The advantage here is: When I lose one of the devices, I do not lose my bitcoins. Not only the attacker has no advantage, I have no damage in case of a loss. It is easy to get a new mobile and place it in synch with the second device and the trusted node.

Those who do not want to buy a pluggable PC can delegate this to an authority they trust. (I admit, this is not completely satisfactory. So, rather, have your own pluggable PC).



Would be great to get a bit of feedback on these thoughts.

Thanx.