Elliptic curve math question

[casascius]

As you guys know, I make Casascius Physical Bitcoins.

I had an idea that maybe you math wizards could either validate or debunk.

First of all, when I create a physical bitcoin, one must trust that I am not keeping the private key.

I am wondering if EC math allows for a bitcoin address to be constructed from two parties using EC addition.  If it worked, it would allow physical bitcoins (or bills or whatever) that had two private key components, so both actors would have to collude to perform a scam.  Basically they could be more trustworthy.

So basically here is what I am asking.  Suppose I create an EC private key S1, and give the public key (X and Y) to the second party.

Some second party takes X and Y, and does EC addition to add some secret S2, that he independently generates, to X and Y, to create a new point (X1 and Y1).

We then compute a Bitcoin address from X1 and Y1.

My hope is that both secrets S1 and S2 would be needed to derive the actual private key needed to spend the funds.  Given that, both me and the other party would create a physical token that would contain keys from both of us.

Would this work?

[1715174020]

1715174020

[1715174020]

1715174020

[1715174020]

1715174020

[1715174020]

1715174020

[1715174020]

1715174020

[1715174020]

1715174020

[ByteCoin]

My hope is that both secrets S1 and S2 would be needed to derive the actual private key needed to spend the funds.  Given that, both me and the other party would create a physical token that would contain keys from both of us.

Would this work?

Yes that works fine except instead of point addition, use point multiplication.

S1 and S2 are random numbers about the same size of the group order. Send the second party the coordinates of S1*G where G is the agreed "generator" point. The final public key is S2*(S1*G) and the private key is (S1 * S2) modulo the curve order.

ByteCoin

[cbeast]

As you guys know, I make Casascius Physical Bitcoins.

Yes you did. They are lovely collectables and a proof of concept toward trading with Bitcoin offline. I'm not sure how math can solve a problem of trust except for the purchaser. If we can't trust the artist, then it takes away from the intrinsic value of the art.

Maybe I don't understand the problem, but if you want to take away our trust of you, then just have the purchaser send you a public key and an encrypted private key.

[casascius]

Maybe I don't understand the problem, but if you want to take away our trust of you, then just have the purchaser send you a public key and an encrypted private key.

I don't think it's a matter of taking away trust, I just feel I can offer a better product if it permits its buyer to put more "trust in numbers" and require less trust in the manufacturer.

For example, we've got robkohr on another thread learning the best way to create his own bitcoin bills.  How sweet a product he would have, if his bills had two holograms on them, each one coming from a different party.  A built-in "check and balance" if you will.

I don't think anyone seriously thinks I will burn them on a 1 BTC coin, especially knowing that I'm charging 1.80 for the coin, and would be drying up a pretty sweet opportunity to sell them at an 80% markup by burning a few people.  When I start cranking out 100 BTC gold bars, people start wanting to be a little bit more cautious, and rightfully so, no matter who I am.

On the other hand, if it's possible to produce bars where no single party has the full private key, it's possible to produce higher-denomination bars with better assurance to the buyer that they are the only one with access to their funds.  Why not a 1000 BTC bar?  It would keep the premium low, and would appeal to the non-technically-oriented buyer.  Same thing would go for a paper savings wallet.

Unlike a 1 BTC coin, a bar also has enough surface area to hold multiple hologram stickers and multiple private keys.

I suppose I could just as easily create bars with nonstandard "two party" scripts that require two separate private keys to redeem, it would just add complexity to the redemption process as well as the production process (e.g. I would have to find a reliable miner who would accept these transactions into the block chain).  All the better if the magic can just be hidden in the math I suppose.

[DeathAndTaxes]

As you guys know, I make Casascius Physical Bitcoins.

Yes you did. They are lovely collectables and a proof of concept toward trading with Bitcoin offline. I'm not sure how math can solve a problem of trust except for the purchaser. If we can't trust the artist, then it takes away from the intrinsic value of the art.

Maybe I don't understand the problem, but if you want to take away our trust of you, then just have the purchaser send you a public key and an encrypted private key.

That wouldn't help then second hand buyers couldn't trust the coin.

The goal would be to have 2 PARTIES that must collude in other to defraud buyers of the coins.  That increases trust.  Because either one can't defraud buyers without the other.

[cbeast]

2 PARTIES that must collude in other to defraud buyers

That NEVER happens. heh.

[DeathAndTaxes]

2 PARTIES that must collude in other to defraud buyers

That NEVER happens. heh.

Of course it can happen but it obviously isn't easier than 1 party working by itself to defraud the buyer.

For example say Gavin, casascius, and Mt. Gox each had to collude together to misaproriate funds from the private key.  If you trust even 1 of the 3 parties you are ensured that even if the other 2 parties wanted to steal your funds they can't.  Now if you don't trust all 3 parties well there is no increased protection but even still it isn't worse than a single party having access to the private key.

If the all of the parties are trustworthy and have something to lose it reduces the likelihood that collusion will happen.

[fivebells]

I believe there's a javascript address generator which you could include inthe ordering process.  The webpage would send you only the data necessary to construct the coin, and give the user the full address info.

Obviates the trust issue completely, but inevitably some users would fail to save this data and lose the coins.

[dree12]

I believe there's a javascript address generator which you could include inthe ordering process.  The webpage would send you only the data necessary to construct the coin, and give the user the full address info.

Obviates the trust issue completely, but inevitably some users would fail to save this data and lose the coins.

The issue is that then the coins are no longer reusable and become average tokens.

[fivebells]

Sorry, I don't follow.  Can you elaborate, please?

Edit: Oh, do you mean the coin has no resale value because the purchaser is not supposed to know what's under the hologram sticker?  I guess that's a concern.  Still, if we're talking about 1000BTC transactions, I wouldn't be trusting the integrity of the transaction to the integrity of a sticker anyway.

[Mike Hearn]

This sounds a lot like threshold cryptography, which is extensively studied.  For example see this paper which covers threshold ECDSA, ie, can a group of players sign a message such that if some players become unresponsive they are kicked out - you need a "threshold of players" hence the name.

If you look at that paper, the part that's relevant is the "ECVSS without a dealer" section. Some older threshold DSA schemes required the key to be created and split by a trusted dealer. Newer schemes can do without that. So you'd adopt the verifiable secret sharing scheme but ignore the threshold signing.

[BTCurious]

Yes, it is possible. Either with ByteCoin's suggestion:

Yes that works fine except instead of point addition, use point multiplication.

S1 and S2 are random numbers about the same size of the group order. Send the second party the coordinates of S1*G where G is the agreed "generator" point. The final public key is S2*(S1*G) and the private key is (S1 * S2) modulo the curve order.

ByteCoin

Or with point addition (slightly different, but the security is the same):
The first party generates S1*G, and sends the X and Y to the second party. The second party adds to this point the point S2*G.
This means the public key is now S1*G + S2 * G = (S1+S2)*G, and the private key is (S1+S2). (Of course, everything modulo the curve order.)

Maybe I don't understand the problem, but if you want to take away our trust of you, then just have the purchaser send you a public key and an encrypted private key.

That wouldn't help then second hand buyers couldn't trust the coin.

Actually, they could, if the hologram is intact. Since under the hologram S2 is stored, the first buyer can't have redeemed the coins unless the hologram is broken. (Assuming safe holograms here.)
You, as a second hand buyer, of course have to trust the first buyer to give you the correct S1. But since the knowledge of S1 an sich is useless to the first buyer, there is no gain for them in scamming you. Unless they don't like you.

This sounds a lot like threshold cryptography, which is extensively studied.  For example see this paper which covers threshold ECDSA, ie, can a group of players sign a message such that if some players become unresponsive they are kicked out - you need a "threshold of players" hence the name.

If you look at that paper, the part that's relevant is the "ECVSS without a dealer" section. Some older threshold DSA schemes required the key to be created and split by a trusted dealer. Newer schemes can do without that. So you'd adopt the verifiable secret sharing scheme but ignore the threshold signing.

The "simple" case discussed up till now where all the keys involved need to be known is rather trivial, and is not threshold signing. That said, threshold signing may be useful, since invariably one of the parties is going to lose his key, and you don't want the money to be gone then.

[casascius]

I was thinking of having S1 and S2 both on the physical piece.

Example, I make a high-denomination bar with two receptacles for keys.  I load it with S1, and then ship the whole batch over to (e.g.) BitBills or MtGox and they use their own custom hologram and load it with S2.  I would never bother with this for 1 BTC, just for 100BTC+.

A scam would require collusion between me and Bitbills/MtGox, so short of that, nobody but the person peeling the sticker can redeem the funds.

There is still the possibility that an exploit could be found against the sticker itself, but someone who acquired the bar directly from me or the other party wouldn't have to worry about that.  Such a vulnerability would only benefit someone who bought a bar, did the exploit, and passed it off in an in-person transaction.

[BTCurious]

Yes, this would work. You have to make sure the other party knows which public key goes with which gold bar though, so make sure your communication is clear on that.

For the record: Either of you can load the bitcoins onto the address. If you (casascius) want to do it, the other party needs to tell you the address(es).

[DeathAndTaxes]

I was thinking of having S1 and S2 both on the physical piece.

Example, I make a high-denomination bar with two receptacles for keys.  I load it with S1, and then ship the whole batch over to (e.g.) BitBills or MtGox and they use their own custom hologram and load it with S2.  I would never bother with this for 1 BTC, just for 100BTC+.

A scam would require collusion between me and Bitbills/MtGox, so short of that, nobody but the person peeling the sticker can redeem the funds.

There is still the possibility that an exploit could be found against the sticker itself, but someone who acquired the bar directly from me or the other party wouldn't have to worry about that.  Such a vulnerability would only benefit someone who bought a bar, did the exploit, and passed it off in an in-person transaction.

I like it in theory.  One potential risk is Q/A.  If either you or the countersigner "screw up" the funds are lost.  One way to partially safeguard against that is extensive testing and possibly random audits by a 3rd party (someone you pay to randomly buy coins and verify them).  You are also linking your rep to the actions of the countersigner.  Their screw up is your screw up. 

Still I could see a lot of potential counter-signers.  If a large escrow service w/ significant reputation and assets ever rose up in the community their entire business is trust/rep.  They would have a lot to lose by colluding.  The same thing with any of the larger exchanges.  Someone who sells high value products (like real gold bullion).   Essentially anyone who is in the "trust business" and the public believes has a lot to lose by colluding.

Hopefully w/ automation the process could be streamlined and it be used for smaller denominations.   Maybe I am just silly but I would love to see a 10 BTC note featuring dual keys on security paper, protected by independent custom engraved holograms.   It is all about volume.  If demand is 10x higher maybe someday volume would support that.

[casascius]

If this is all true, then it has big unrealized implications for ways wallets can be secured, far stronger than wallet encryption.

Imagine a web wallet service which created and managed s1 and which signed your transactions after verifying them via SMS. (s1 would be mailed to you encrypted, or on a CD-R, as a failsafe)

Imagine a paper wallet printer which took s1*G and printed you a 100% safe paper wallet because you generated s1*G from a passphrase (s1=sha256(passphrase)) using an app on your smartphone.

[ByteCoin]

Or with point addition (slightly different, but the security is the same):
The first party generates S1*G, and sends the X and Y to the second party. The second party adds to this point the point S2*G.
This means the public key is now S1*G + S2 * G = (S1+S2)*G, and the private key is (S1+S2). (Of course, everything modulo the curve order.)

This suffers from a security flaw that my scheme does not have. Whether it's exploitable depends on the details of the implementation.
Can anyone else see a problem with the above?

ByteCoin

PS

If this is all true, then it has big unrealized implications for ways wallets can be secured, far stronger than wallet encryption.

I think you're a bit hasty with the "unrealized"

[casascius]

This suffers from a security flaw that my scheme does not have. Whether it's exploitable depends on the details of the implementation.
Can anyone else see a problem with the above?

I would be eager to understand the flaw you say you see.  I do not understand the math well enough to be qualified to see the flaw, I have to take someone's word for it.

[jothan]

If the private keys are k1 and k2, and the base point is BP and the resulting public key is PK then:

PK = (BP * k1) *k2

With intermediate public keys:

PK1 = BP * k1
PK = PK1 * k2

Where * represents point multiplication.

Edit: in theory, the private key PK = k1 * k2 (mod n), (where * is scalar multiplication) but my ECC math is a bit rusty.

I do not think there is a way to do a "symmetric" or "simultaneous" way to do this. So Alice has to generate a normal key pair, and Bob needs to generate a key pair, using the key Alice provided as a base point.


I almost added ECC cryto to GnuTLS, I had a full python prototype, but someone beat me to it.

[BTCurious]

Or with point addition (slightly different, but the security is the same):
The first party generates S1*G, and sends the X and Y to the second party. The second party adds to this point the point S2*G.
This means the public key is now S1*G + S2 * G = (S1+S2)*G, and the private key is (S1+S2). (Of course, everything modulo the curve order.)

This suffers from a security flaw that my scheme does not have. Whether it's exploitable depends on the details of the implementation.
Can anyone else see a problem with the above?

Could you maybe tell what the flaw is?.. Because as far as I know, there isn't one.
Note: Your way of phrasing your comment makes it sound like you're lecturing. Maybe this wasn't intended.

I do not think there is a way to do a "symmetric" or "simultaneous" way to do this. So Alice has to generate a normal key pair, and Bob needs to generate a key pair, using the key Alice provided as a base point.

Assuming the addition way of generating a joint key is secure (which it is, as far as I know), then you can do this symmetrically. Both generate a private key, calculate the public key, and then send the public key to each other. The public keys added are the total public key.