[messaging] Replacing group signatures with HMAC in Pond.

[Trevor Perrin]

On Wed, May 28, 2014 at 11:54 AM, Joseph Bonneau <jbonneau at gmail.com> wrote:
>
> On Wed, May 28, 2014 at 2:24 PM, Trevor Perrin <trevp at trevp.net> wrote:
>>
>> You'd want to hand out serial #s randomly, so the server's bitmask
>> would need to be sized to MAX number of messages that a user can
>> receive.  Not sure if that's a win spacewise vs storing 100 or 64 bits
>> for each actual message.
>
>
> You hand out serial #s randomly from your pool, but I don't think they need
> to be random serial numbers from a 64-bit space. You can generate say 2^20
> key pairs with sequential serial numbers. Every time you hand some out to
> contacts, you pick a random set from those you haven't handed out yet. This
> enables the bitmap representation. Is there a flaw with that I'm missing?

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?).

> Eventually if you run out you get into the HMAC update process you
> described, this happens either way.

Sure.

Trevor