Homomorphic encryption and Bitcoin
post by jimrandomh · 2011-05-19T01:07:14.192Z · LW · GW · Legacy · 9 commentsContents
9 comments
BitCoin is a recently introduced currency, based on public-key cryptography combined with a peer-to-peer network for verifying transactions. I've been thinking a lot about BitCoin recently, and particularly about BitCoin's main weakness: if your computer is compromised, an attacker could copy your BitCoin wallet and use it to steal coins. That's bad. But I've come up with a possible improvement that would greatly mitigate this risk, and was hoping for some help confirming its viability and filling in the details.
The basic idea is to make it so that rather than having a single computer which can steal your coins if it's compromised, you have two computers (or a computer and a phone), such that your coins can only be spent if both devices cooperate. It is much harder to break into two computers belonging to the same person than just one, so this makes coins harder to steal. You could also have one of the computers involved be a third party that you trust to keep its files secure, and while that third party would be able to freeze your funds, it wouldn't be able to steal them. Using a third party this way, you could also add withdrawal rate limits and time delays, further improving security.
I believe that this can be done in a fully backwards-compatible way, without any changes to the BitCoin protocol, using homomorphic encryption. BitCoin is based on elliptic curve cryptography; a receiving address is a public key, and a wallet file is a collection of private keys. The goal is to create a protocol where two cooperating computers produce a split key, such that they can use it cooperatively to sign transactions later, but neither one can sign transactions or determine the whole key on its own. My understanding is that homomorphic encryption can be used to implement a simulated computer that does arbitrary trusted computation, so this should be possible. However, I'm a bit fuzzy on the details, and I don't have the time or comparative advantage to implement this myself.
(To deal with the risk of one one computer being lost or damaged, there could also be an override key; both computers would have the public half of the override key, and the private half would be kept offline in a bank deposit box or something similar. Then both computers use the override key to encrypt their halves of the split key, and send the encrypted keys to a cloud backup provider.)
9 comments
Comments sorted by top scores.
comment by paulfchristiano · 2011-05-19T01:45:27.231Z · LW(p) · GW(p)
This doesn't require any difficult encryption: just split your private key into two uniformly random strings which XOR to the correct value (ie, generate one half randomly, and XOR it with the private key to get the other).
To maintain a backup, you can either store the private key itself in a safe place, or cut up the key into 3 pieces such that the original can be recovered from any 2.
If you want an adversary to need simultaneous access to both devices, you can periodically refresh the keys.
Replies from: jimrandomh↑ comment by jimrandomh · 2011-05-19T01:52:36.312Z · LW(p) · GW(p)
This doesn't require any difficult encryption: just split your private key into two uniformly random strings which XOR to the correct value (ie, generate one half randomly, and XOR it with the private key to get the other).This doesn't require any difficult encryption: just split your private key into two uniformly random strings which XOR to the correct value (ie, generate one half randomly, and XOR it with the private key to get the other).
That doesn't work. If you do that, then every time you send money, then to sign an outgoing transaction, you have to put the two keys back together on one or the other of the two computers. The point of using homomorphic encryption is to avoid doing that, since it creates an opportunity to steal the combined key.
Replies from: paulfchristiano↑ comment by paulfchristiano · 2011-05-19T02:52:53.229Z · LW(p) · GW(p)
I see. My earlier proposal defends you against an adversary who steals your computer, but not against one who has root access without your knowledge.
In that case it is sufficient to have secure function evaluation. This is conceptually much easier than homomorphic encryption (having been discovered some 25 years earlier) and is currently much more practical (ie, practical at all). I don't know much about existing implementations.
comment by Pavitra · 2011-05-19T01:34:39.330Z · LW(p) · GW(p)
The first sentence seems to be repeated after the second.
Edit now that I've read the post:
A full, unsplit key would presumably have to exist at some point if you're trying for full backward compatibility with the existing network protocol. There would be some logistical issues with ensuring that you didn't leave traces on the computer that performed this operation, or in the process of transferring the split halves from that computer to the other shareholder. A moderately experienced cryptographer should be able to anticipate and deal with this kind of thing, but it's worth pointing out to any prospective hobbyist hackers.
The override key can probably just be the unsplit key in a bank deposit box.
↑ comment by jimrandomh · 2011-05-19T01:48:47.444Z · LW(p) · GW(p)
The first sentence seems to be repeated after the second.The first sentence seems to be repeated after the second.
Fixed, thanks.
The override key can probably just be the unsplit key in a bank deposit box.The override key can probably just be the unsplit key in a bank deposit box.
If you do it that way, you can't make new receiving addresses, because those are private keys. You can keep the same receiving address for all your transactions, but if you do then it isn't as anonymous anymore. In any case, the override key is the easy part of this scheme, and anything that ensures you have a proper backup will do.
Replies from: Pavitracomment by dugancm · 2011-05-21T10:06:36.446Z · LW(p) · GW(p)
If you have three arbiters and require at least two of them to be party to any transactions and the creation of new arbiters, one can be a trusted or paid third party without risking theft, account freeze or unauthorized arbiter creation and you can safely recover from losing a single device.
I am ignorant of the details necessary to implement this and how difficult it might be.
comment by playtherapist · 2011-05-19T02:11:37.715Z · LW(p) · GW(p)
Sounds brilliant to me. :)