My apologies, tamper-resistant is more accurate. The cards we plan to use are certified at the EAL 5+ level (http://en.wikipedia.org/wiki/Evaluation_Assurance_Level) which I understand to be fairly high - maybe not high enough for military apps but definitely designed to withstand casual hacking attempts.

Thank you!
Razvan

Petertodd would probably recommend bonding the cards in some (or multiple ways).

One way would be to make every card contain a shared bitcoin private key (same key in all cards) for some large amount of Bitcoin, visible sitting in the chain. The card could prove that it contains the key by being willing to do a bitcoin-signmessage for the key.

If someone can compromise your tamper resistance, they can obtain the coin and in doing so would alert everyone that the tamper-resistance has been compromised at least once.

Thats kinda bad for privacy.  You could use a cryptographically secure bloom filter to improve privacy, but it's probably asking too much for your CPU power.

Interesting, done right you could probably make it so your alert mechnism wrote a cryptographic proof that could be showed to other people.

btw I its not so clear in the book, and I reinvented it in my 1995-2005 pre-bitcoin attempts to find a way to deploy a decentalized anonymous ecash, as specified what he is saying is actually not offline respendable, only offline spendable; ie after you've done your spend, before you can respend, you have to deposit the funds in an issuer bank.  (And in bitcoin or zerocoin or the 1999 Ta-Shma & Sander "auditable anonymous electronic cash" paper there is no central bank, but you have to send it to the blockchain/zerocoin mix/shared blackboard respectively, but the dependency is still present).

What I figured out is you can offline respend without deposit (without going online) using 0-value coin collection as the initial witness.  Very excited when I figured out that in 2000, and I asked Stefan about it, but it turns out there was a masters thesis on this topic and its mentioned in a footnote somewhere in Brands PhD thesis/book referenced above.

Anyway it seems to me you're more interested in offline re-spendability so you need to use that follow-on invention/re-invention.

Why I did nothing with this protocol (eg like rush off and implement it with B-money) is I was thinking it was not good enough - its necessarily, like bitcoin, pseudonymous, and publicly linkable, which I considered, and still do consider to be a privacy problem (and in bitcoin whether you believe in privacy or not, a fungibility problem in addition, hence all the debate about zerocoin, coinjoin, mixers and taint, whether you actually even want anonymity or not, those security concerns of fungibility and anonymity are actually orthogonal - you can have fungibility (via coin anonymity) with pseudonymity, or escrowed identity and other variants just fine).  Btw there is a difference between payment confidentiality and pseudonymity/anonymity also, you can have payment confidentiality with or without pseudonymity/escrowed identity pseudonymity/anonymity.  Bitcoin has limited payment confidentiality (you have to work hard with wallet control, which is not implemented, and disciplined fund separation, and mixes/coinjoining is of apparently statistically weak value according to the data analysts who have looked at the network flow statistics.  And thats a problem.  If nothing else we need to make bitcoin payment amounts confidential (eg homomorphic value encryption).  And even payees is extremely invasive if you think about it.  Oh the public can see you bought an ebook from this publisher.  Or you bought a condom pack from this supplier.  etc  Its ridiculously invasive as is, and if your credit card issue or bank account put your statements online like the block chain there would be a public outcry.

Also I have to say I am not someone convinced by the offline respendability security argument.  Even if there is a fidelity bond, the problem is offline respendable card is a license to print money, and people will just spend a multiple of the fidelity bond or try to.  One somewhat defense is that if multiple people have offline respenable money flowing around, some of them are going to convert it to online ("deposit" it) and as soon as that happens the double-spend hw hack is blown.  You want to pass a "this key and card series hacked" protocol revocation cert through the network, and switch to the ciphersuite/keyset B while working on deploying card C or firmware upgrade C.

Adam

It's a nice idea, but as you say yourself "The only trusted authority is the issuer of the OtherCoin card".

So first of all you need to trust an authority.

Second, you need to have some kind of making sure that the card is not just pretending to be issued by an authority - this I guess you can do by putting the authority's private key inside the card and telling it to sign messages with it.

But the third problem is (and I had worked with smart cards for awhile) that basically every smart card can be hacked - it is only a matter of time and money.
So eventually someone will manage to get the authority's private key out of it and then will be able to make his own, fake cards.

And on top of that, there is always tha ever lasting: how can you even trust an authority?

But the idea is appealing and probably worth exploring.

I would not call the guy a criminal, but... http://www.youtube.com/watch?v=Qk73ye2_g4o

For the application we are talking about, all it takes to extract the authority's private key is to successfully hack one card.
You might destroy hundreds of thousands of them, on the way there, but all you need is the master key that is shared among all of them.
So one is enough and you can make millions of fake ones ever since that moment.

That's actually the plan, but we need to make sure that the person reporting the hack is not the person that has actually hacked the card. If we have a physically intact card that contains a private key that we've seen a spend operation for on the blockchain and the card can keep track of the previous owners of that private key, it can be asked to reveal that chain of previous owners. If two or more physically and logically intact OtherCoins report this, we can compare the chains and find the actual card that has performed the double spend.

The wallet will most probably employ Bloom filters to monitor the blockchain - but most wallets already do that, don't they? The wallet knows the public keys addresses to look for and it's up to it to fine tune the Bloom filter to not reveal the exact addresses it's looking at. I wouldn't want to implement that on the smartcard.

Piotr, the way it works is that there are two separate operations. The first one (called REVEAL) takes the Bitcoin private key out of the secure storage, encrypts it with the RSA-2048 public key of the recipient, then moves it to a public buffer (no longer in secure storage) that the wallet can read it from as many times as it wants. Once the wallet has successfully forwarded that encrypted key to the other end, it issues a second command called REMOVE that clears the public buffer. The Bitcoin private key is erased from secure storage as soon as REVEAL is called, but it is still available in its encrypted form (decryptable only by the recipient) in the public buffer until REMOVE is called.

So in the case of a communication breakdown, the sender can keep reading it from the buffer (or just cache it internally since it's encrypted) and retry sending it to the recipient that is now the only entity capable of recovering that Bitcoin private key.

The scheme also does replay protection by using a nonce sent together with the RSA public key (preventing you from resending an old recorded payment message to a recipient to convince him to reimport the key into its private storage).

What is the protocol to establish an authenticated and encrypted channel between the smart cards that is resistant to MITM attacks?