Please scratch my previous message, there is a much simpler and better scheme: Embed a serial number in each token.
Bob distributes tokens (x, HMAC_k(i,y)) to his contacts for i in [1,N]. Now the server just needs to store a bitmap of length N to track spent tokens. This is optimal space-wise and has no false positives. If you really start running low on tokens you can probably compact the set of unspent tokens down to a list and then issue a new block of serial numbers. 1 M tokens per user now means 125kB of storage. Given the latency already present you could run a mail server for millions of users on a cheap hard drive-far more than 1 server could probably support anyways. Worth noting the storage requirements for each contact here are much higher, but for the server this seems pretty easy to deal with.
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
