[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 adam at cypherspace.org
Thu Apr 18 07:12:34 EDT 2013


Someone asked me offline for the UFO RSA reference, so I am posting my reply
here.  (RSA UFOs are a way to generate an RSA key without ever knowing the
private key in a trustworthy way).

Its ref 26 in the zerocoin paper:

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

T. Sander, “Efficient accumulators without trapdoor extended
abstract,” in Information and Communication Security, vol.
1726 of LNCS, 1999, pp. 252–262.  citeseer has it:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.4015

Btw thats presumably not coincidentally the same Sander from Sander & Ta
Shma that published auditable distibuted NIZKP-based "auditable anonymous
electronic cash" in 1999.  

http://www.cs.tau.ac.il/~amnon/Papers/ST.crypto99.pdf

You've got to say that paper is really close to the distributed publicly
auditable aspects of bitcoin.

They were aiming for privacy, auditability and distribution; so its really
close to bitcoin - bitcoin drops the blinding/ZKP based privacy target and
adds hashcash distributed mining and the b-money (Wei Dai) or bitgold (Nick
Szabo) inspired inflation control + later independent exchanges sprung up so
there was no direct banking interface.  

The only aspect of privacy in bitcoin is that there is no bitcoin address
requiring identity, so you are pseudonymous, plus can consequently create
many addresses (and the clients seem to encourage this by design).  The
exchanges of course require identification for wire transfers, but there is
some ambiguity between "spent" and transferred to another coin you own.  Not
a huge amount though and people dont reasn well about statistics as Shamir
et al showed in "quantitative analysis of the full bitcoin transaction
graph".

http://eprint.iacr.org/2012/584.pdf

Adam

On Wed, Apr 17, 2013 at 11:49:00PM +0200, Adam Back wrote:
>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...


More information about the cryptography mailing list