Crypto Currency Cabal

Schedule

Starting Wednesday and every following class: Be prepared to give an elevator pitch for your project. Your pitch should be no more than 2 minutes long. You may use visuals as long as you can obtain them by (quickly) entering a URL in a web browser. Your pitch should get across in a convincing and engaging way:

• The purpose of your project (what problem are you solving)
• What you are actually doing
• Why we should care

Monday, 23 November (8:29pm): Project Progress Reports. Send an email to ccc-staff@cs.virginia.edu, cc-ing all members of your project team. The email should have a subject line, Project:Title, with your project title. Its body should contain at least this information:

1. A link to the website for your project (this could be a github page if you want). That site should have a front page that describes your project, lists the team members, and provides more information about your project.

2. A short paragraph explaining how your project has changed since the preliminary proposal email. This should explain if the goals of your project have changed and why.

3. A description of what progress you have made on your project.

4. A description of what you plan to do to complete your project, and your plans for doing this. If you have a multi-person team, this should include an explanation of how your team is working together and who is doing what.

5. (optional) Any questions you have for us.

Addendum

Vignesh raised a really good point about Chaum’s scheme which I misunderstood in class until he clarified it after, so I’m posting an explanation here.

The issue he noticed is that if the bank knows all the possible I values (all the customer identities), and receives one of the identity split perimages, e.g., I_1L, then the bank can search through all the identities to find an I_1R such that h(I_1R) matches the hash value. This is done by just xor-ing all the I values with I_1L to find a guess for I_1R, and then computing the hash to check if it is the right one. As I presented the scheme, this would be a big vulnerability! It violates the desired property that the bill spender’s anonymity is protected (even from the bank) unless she attempts to spend the bill twice.

To defeat this, we need to ensure that the set of possible I values is not known (even to the bank). One way to do this would be to add some randomness in the I values used in the generated banknotes used in the cut-and-choose for the blind signatures. Each note with have a different I, but one the bank can verify is still the right account owner. I’ll leave the details of how to do this as a challenge problem.

Notes

High Trust Bank must be trusty!

David Chaum, Amos Fiat, and Moni Naor. Untraceable Electronic Cash. CRYPTO 1988.

Simple RSA Signatures
Public Key = (e, n) Private Key = d

Identity: M^de = M mod n

Sign(m) = m^d mod n

Blind Signatures Alice picks random k in [1, n)
t = mk^e mod n
Sends t to signer.

Signer returns t^d.

Signer returns t^d.

t^d = (mk^e mod n)^d mod n
    = m^dk^ed mod n
    = m^dk mod n

Dividing by k gives Sign(m) = m^d mod n.

What should a signer know before signing a random-looking string?

Cut-and-Choose

Suppose Alice sends 256 copies and the Bank checks 255 of them. What is the probability Alice can cheat without getting caught?

What should the maximimum bill size be to prevent cheating?

Identity Strings

I = “alice@alice.org”

M_i = “Bill #[r_i] : Bear’s Turns Bank owes the holder of this message $100.”
    + identity strings:       I₁ = (h(I_1L), h(I_1R)), …, I_n = (h(I_nL), h(I_nR))
    where h is a one-way hash function and each I_iL ⊕ I_iR = I (but I_iL is choosen randomly).

To spend a bill, the reciever chooses either L or R for each pair for spender to open.

What is the probability Alice can spend a bill twice without revealing her identity?

Before Bitcoin: The Rise and Fall of DigiCash

By all accounts Chaum was a charismatic leader with an interesting management style, but he refused to compromise his artistic vision in any area against the best advice of his employees. He was suspicious of everyone and ‘paranoid’ with a habit of suddenly changing his mind without warning. At one time, Microsoft had offered DigiCash $180 million to allow them to preinstall Ecash software on Windows computers and the deal was on the verge of completion, but Chaum suddenly decided that his product was worth more and the deal collapsed. If the deal had gone through, cryptocurrency would now be as ubiquitous as Internet Explorer.

Links

“Still think you’re anonymous on the Dark Web?”, NCA_UK’s tweet, 7 November 2014

Sambuddho Chakravarty, Marco V. Barbera, Georgios Portokalidis, Michalis Polychronakis, and Angelos D. Keromytis. On the Effectiveness of Traffic Analysis Against Anonymity Networks Using Flow Records. Passive and Active Measurement Conference, March 2014.

Tor security advisory: “relay early” traffic confirmation attack