[messaging] Replacing group signatures with HMAC in Pond.

[Joseph Bonneau]

On May 26, 2014 5:28 PM, "Adam Langley" <agl at imperialviolet.org> wrote:

> Rather than using group signatures, a user and their home server share a
> HMAC
> key, k. During the introduction protocol, a number of pairs are exchanged.
> Each pair contains a private key, x, and HMAC(k, y), where y is the public
> key for x.
>
> 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.
>
> Now a revocation involves sending a list of HMAC(k, y) values to the server
> to be "crossed off". This storage grows without bound, but very slowly. All
> the problems with messages bouncing and needing to be resigned are solved.
> So
> is the problem of having pending revocations when performing the
> introduction
> protocol.
>

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.

The distributing user could try to misbehave by issuing multiple keys with
the same serial number HMAC_k(i || y) and HMAC_k(i || y'), but the server
would then only accept the first one it sees. I don't see any real problem
here.

There *might* be a privacy issue if the serial numbers are given out
non-randomly to contacts, but there's an easy enough fix if users just
ensure they hand out serial numbers randomly, in which case this is
identical to the proposal of storing the full HMAC.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140528/32f0ecfe/attachment.html>