[messaging] Replacing group signatures with HMAC in Pond.

[Trevor Perrin]

On Thu, May 29, 2014 at 8:34 AM, Joseph Bonneau <jbonneau at gmail.com> wrote:
> 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.
[...]
>
> 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.

Oh I see, with serial numbers the server could at a minimum also track
them with a blacklist, which would be smaller than a blacklist of MACs
due to birthday bound (though I'd expect closer to a 2x difference
than 5x).  That makes sense, seems like a good optimization.

Trevor