It appears to use cut-and-choose technique to create a non-interactive ZKP on a one-way accumulator (from Camenisch & Lysanka). That results in relatively big ZKPs which impact bitcoin scalability, it doesnt say how big they actually are but for good security margin I'm guessing something like 128 individual proofs, which can get kind of heavy. They say its like to exceed the bitcoins 10kb per tx limit. (People may recall cut-and-choose as Chaum's original blind RSA signature based proposal to support offline spendable ecash with identity exposure as the penalty - the owners identity would be embedded in the coin via cut and choose, and then if they double spend revealed as ther is some recipient choice within the spend that would reveal two shares). Stefan Brands ecash by contrast with the more flexible discrete log representation problem provided a direct (non-cut-and-choose) offline double spend deterrence method. (Cut and choose is a simple idea that if you have to commit first and reveal one of two options you have a 1 in 2 (0.5 or 2^-1) chances of cheating (and putting someone elses identity in the coin eg for revealing during an offline double spen), but if you do it 128 times you have a 2^-128 chance of cheating. The same approach plus demonstrably fair way to generate witnesses is a general method for constructing NIZKPs from ZKPs.) Also in principle you have to construct a NIZKP all the way back to the first zerocoin, and while the accumulator is constructed incrementally and stored in each block bitcoin requires public auditability so the verifier has to go check the corresponding "spent" list that grows. (The ZKP is that the zerocoin is a member of the set of zerocoins previously exchanged for bitcoin, and is not a member of the spent list. The expensive part is the former, the latter is just a bit list of spent zerocoin serial numbers. Thy do suggest just trusting the last block accumulator as a starting point, but I think you can only do that if the zerocoin was issued after that, and the effectiveness of that optimization is in some conflict with anonymity set requiremnts to hold the zerocoin for a while to at least have a decent number of coins your mixin with. The accumulators allow faster NIZP of set membership than proving with a bit list of OR operations, but the cut-and-choose itself isnt a direct NiZKP it involves 128 rounds or whatever the security parameter is. The accumulator uses a trusted party to generate an RSA key and discard the private keys. (Though happily there are RSA UFOs (way to generate an RSA key without ever knowing the private key in a trustworthy way)). So thats all pretty cool, and I think an efficiency improvement over previous NIZKP of set membership (or non-set-membership) but a bit heavy. btw about payment privacy (or lack thereof in bitcoin) an amusing link http://www.listentobitcoin.com/ to get an idea of the bitcoin transaction volume and transaction sizes - highlighting visually the extremely open nature of the realtime transaction history. I saw a massive $640k transaction float past when I looked. Soothing sounds it makes too. (Bitcoin is private only in the self chosen psuedonym sense, and is otherwise an open book by design). Adam On Sat, Apr 13, 2013 at 01:40:36AM +0300, ianG wrote:

Steve Bellovin posted this on another list, hattip to him.

http://www.forbes.com/sites/andygreenberg/2013/04/12/zerocoin-add-on-for-bit...

For those following Bitcoin this is news. Matthew Green writes:

For those who just want the TL;DR, here it is:

Zerocoin is a new cryptographic extension to Bitcoin that (if adopted) would bring true cryptographic anonymity to Bitcoin. It works at the protocol level and doesn't require new trusted parties or services. With some engineering, it might (someday) turn Bitcoin into a completely untraceable, anonymous electronic currency.

http://blog.cryptographyengineering.com/2013/04/zerocoin-making-bitcoin-anon...

(iang adds:)

Bitcoin is psuedonymous but traceable, which is to say that all transactions are traceable from identity to identity, but those identities are psuedonyms, being (hashes of) public keys. This is pretty weak. In contrast, Chaumian blinding was untraceable but typically identified according to an issuer's regime. Because Chaumian mathematics required a mint, this devolved to trusted/identified, so again not as strong as some hoped.

Bitcoin fixed this 'flaw' by decorporating the mint into an algorithm. This suggests a new axis of distributed. But Bitcoin lost the untraceability in the process, thus rendering it a rather ridiculous attempt at privacy, as the entire graph was on display. Bitcoin is more or less worse at privacy than Chaumian cash ever was.

The holy grail in Chaumian times was untraceable & unidentifiable, to which Bitcoin added distributed. This paper by Miers, Garman, Green & Rubin suggests untraceable & psuedonymous & distributed is possible:

http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

(I haven't as yet read the paper so there may be killer details in there.)

iang _______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography

cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE