[cryptography] summary of zerocoin (Re: an untraceability extension to Bitcoin using a combination of digital commitments, one-way accumulators and zero-knowledge proofs, )

[Adam Back]

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-bitcoin-could-make-it-truly-anonymous-and-untraceable/
>
> 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-anonymous.html
>
>
>
> (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 at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
_______________________________________________
cryptography mailing list
cryptography at 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