[messaging] Message delivery and revocation in Pond etc

[Joseph Bonneau]

As a minor improvement to Trevor's original proposal (or whomever explained
it to Trevor), the server could a Bloom filter of previously-seen tokens.
This gets you down to about 1 byte of storage per token with a 2% false
positive rate. So 1MB of storage per user at the server lets each user have
1M outstanding tokens. Something around that much is probably enough that
nearly all users would never need to refresh in the lifetime of the
system.-you could arguably never have to go into an epoch change.

2% of legitimate message sending attempts would be reject by the server due
to the false positives, but that's okay. Senders can simply re-send in that
case with a different token, with negligible impacts on performance.

This allows allows very efficient revocation if Bob is savvy to the Bloom
filter parameters: he can just send to the server a list of bits to flip in
the bloom filter and instantly revoke an arbitrary number of tokens.

With performance hacks like this I think this system is workable and
probably more efficient in practice than using a pairing-based cryptosystem.

On Thu, Apr 3, 2014 at 7:20 PM, Trevor Perrin <trevp at trevp.net> wrote:

> On Thu, Apr 3, 2014 at 4:11 PM, Michael Rogers <michael at briarproject.org>
> wrote:
> >
> > in Pond, does the
> > recipient have some trapdoor information that the server doesn't have,
> > allowing the recipient to tell which contact made the group signature?
>
> Yes:
>
> http://www.robotics.stanford.edu/~xb/crypto04a/groupsigs.pdf
>
> Pond's group signatures are actually very cool, and (according to
> Boneh) VLR group signatures are also worth taking a look at, since
> they handle revocation better:
>
> http://cseweb.ucsd.edu/~hovav/dist/preteripsistic.pdf
>
>
> Trevor
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140404/c225b81e/attachment.html>