[messaging] Message delivery and revocation in Pond etc

[Trevor Perrin]

We've been discussing introductions in "unlinkable" aka "unobservable"
messaging systems like Pond [1] or Petmail [2].

After the introduction completes, we want Alice to be able to send
messages to Bob's server (and vice versa), such that:
 - Bob's server learns the message is for Bob
 - Bob's server doesn't learn who the message is from
 - Bob's server can't recognize messages from the same sender
 - Bob's server can't tamper with messages (e.g. can't make it appear
that Alice is sending garbage)
 - Bob can recognize who the message is from
 - Bob can revoke any sender (e.g., if Alice starts spamming him)

(The messages are also encrypted, but those details aren't important here.)

In Pond, this is done with "BBS group signatures" [3,4]:  Alice can
sign messages that the server can verify using the "group public key",
but only Bob is able to "trace" the signature to Alice.  Bob can also
update the group public key, and publish revocation data to the server
that lets every other user (except the revoked one) update their
signing key.

One downside:  After a revocation, the server can learn how many
contacts Bob has by counting how many times someone tries to deliver a
message signed with the old group key.


Here's a proposed alternative (explained to me by someone else):

Bob and his server share an HMAC key k.  Bob distributes to each of
his contacts a bunch of pairs (x, HMAC(k,y)) where (x,y) are a
signature keypair (y=g^x).

Contacts then send (msg, y, HMAC(k,y), sig(msg, x)) to the server,
which records used values of HMAC(k,y) and rejects them in future.

Bad:

 * Since the (x, HMAC(k,y)) pairs are one-time use, there must be
periodic replies to a contact to refresh its store of pairs.

 * The server's storage of used values is unlimited over time, but
grows at a small rate, and could possibly be scoped by introducing
more complexity (e.g. rotating epochs).

Good:

 * Revoking Alice is just a matter of telling the server Alice's y
values, and doesn't put non-revoked users through a rejection/update
process.

 * Less computation than the pairing-based BBS signatures.


Thoughts?


Trevor

[1] https://pond.imperialviolet.org/
[2] https://github.com/warner/petmail
[3] https://pond.imperialviolet.org/tech.html
[4] http://www.robotics.stanford.edu/~xb/crypto04a/groupsigs.pdf