[messaging] Replacing group signatures with HMAC in Pond.

[Joseph Bonneau]

On Wed, May 28, 2014 at 12:01 PM, Trevor Perrin <trevp at trevp.net> wrote:
>
> No, I'm just pointing out that the bitmap needs to be sized for MAX
> number of messages (2^20 ?), whereas a list of received MACs only
> needs to store the ACTUAL number of messages, so whether (MAX * 1 bit)
> will be a space savings vs (ACTUAL * 64 bits) is not totally clear to
> me (but maybe you can compress the bitmask if sparse?).


The serial numbers don't need to be 64 bits, just lg(N) where N is the
number of tokens you can give out before a refresh. The space savings vary
with the percentage of tokens redeemed so far, call it p. The improvement
depends on the length of MAC you're comfortable with, call it L. Assume
lg(N)=20, you get a [L/lg(N)] = 5x space savings right off the bat for p
close to 0. Eventually it becomes L/2 = 50x savings when p=0.5, and then as
p approaches 1 it becomes [L/lg(N)] = 5x again (because eventually you
store just the serial numbers or MACs of unredeemed tokens). You can vary
the savings gradually in between the two using compressed bitmap techniques.

Seems like a worthwhile optimization though since you get 5x minimum
improvement and you can get more depending on how much implementation
effort you want to put into bitmaps. Also the nice thing is you get to 50x
savings at the point where the most storage is required when storing full
MACs, so the max storage in this scheme at any point is a full 50x less,
and that's regardless of your choice of N.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140529/235294a6/attachment.html>