[messaging] Replacing group signatures with HMAC in Pond.

[Trevor Perrin]

On Tue, May 27, 2014 at 9:50 PM, Joseph Bonneau <jbonneau at gmail.com> wrote:
>>
>> Delivery attempts contain (msg, y, HMAC(k,y), sig(msg, x)). The server can
>> check the HMAC because it holds the HMAC key. The recipient can find who
>> sent a message because they know who a given public key was given to. A
>> sender's pool of pairs is refreshed in the normal exchange of messages.
>>
>> Once accepted, a server records HMAC(k, y) and rejects it in the future.
[...]
>
> There's a space optimization for the server I proposed here:
> https://moderncrypto.org/mail-archive/messaging/2014/000292.html
>
> The user distributes pairs (x, HMAC_k(i || y)) for serial numbers i in
> [1,N]. Now the server can just "cross off" the serial number i instead of
> HMAC(k, y). This can be implemented as a bitmap with 1 bit of storage for
> each outstanding value. This is probably a factor 100 space savings.

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.

Another way to reduce server state would be to change the HMAC key
occasionally, so the server could delete old state (whether bitmask or
list).

I can see a couple challenges there, but I think they're solvable:

 * Before you change your HMAC receiving key, you'd need to send a
"key-change" message with new pairs to all your correspondents, and a
time when they should discard old pairs and start using new pairs (and
your correspondents need to be time-sync'd and switch at the same
time, otherwise the server will be able to distinguish messages from
new-key vs old-key correspondents).

 * Before you send a message, you need to ensure that you've retrieved
any relevant "key-change" messages from your mailbox, otherwise you
might be unaware that a key-change had been scheduled, and use an
old-key pair.  Assuming key changes are scheduled at least a week or
month in advance, your client would prohibit you from sending a new
message until you had downloaded messages at least up to the last week
or month.

Trevor