On Mon, Sep 20, 1999 at 03:46:39PM +0100, Adam Back wrote:
> How communication and computationally intensive is the ZK proof as a
> function of the coin list length? Could the proof be used in a
> practical system?
The complexity is polylog in the number of coins, but unfortunately it is
not practical yet because the (noninteractive) ZK proofs use generic ZK
constructions rather than known efficient ZK proof systems (though the
authors say they are working on a practical version).
> Couldn't one have a mintless method of injecting new coins into the
> system by using hashcash in a similar way to that proposed by Wei Dei
> in b-money [1]?
I propose as an alternative to the above that (when it becomes practical)
we use Sander and Ta-Shma's protocol as a subprotocol in b-money to obtain
payer-payee unlinkability. (Payers and payees in b-money are pseudonyms,
but in the basic protocol the pseudonyms can be linked by payer-payee
relationships.) Each round the Sander-Ta-Shma protocol is run, and whoever
wants to pay converts b-money into coins and send them to payees. Payees
must convert coins back into b-money during the same round (the coin
database is wiped between rounds). This way the size of the distributed
database is minimized.
BTW Sander and Ta-Shma's paper is available at
http://www.icsi.berkeley.edu/~sander/publications/audit.ps.
