[ZcF-general] May update

[Samuel D Gordon]

We have continued working on our paper.  While thinking about how to analyze our scheme, we realized that our framework doesn’t have to be applied on top of ring signatures / monero per se.  Any method for fully anonymous mixing among a small set can be composed to provide mixing for a much larger set, with differential privacy. The trade-off is security for efficiency: for n parties to fully mix their coins using ZKP (whether with SNARKS or ring signatures) require O(n) expensive operations per party.  Using our approach, we require polylog n operations per party, but leak some information.


We have also improved on our construction, further reducing the computational cost by about a factor of 10 (depending on the choice of epsilon).  Currently, we believe we can claim improved computation cost for any n > 1600 participants in the mixing.


Issues to address:

  *   We are still looking at ways to reduce the needed noise.

  *   With the recent introduction of short ring signatures (log size), our construction will have worse communication complexity than existing schemes.  We don’t really see a way to address this, and will instead analyze the savings in computational cost, and the relative importance of this savings.

  *   We still need to think about how much of our communication needs to be put on the blockchain, vs. what can be done off chain.  This was less of a concern prior to the introduction of log-sized ring signatures.