<div dir="ltr">Please scratch my previous message, there is a much simpler and better scheme: Embed a serial number in each token. <div><br></div><div>Bob distributes tokens <span style="font-size:13px;font-family:arial,sans-serif">(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. </span><span style="font-family:arial,sans-serif;font-size:13px">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.</span></div>

<div><br></div><div><span style="font-size:13px;font-family:arial,sans-serif">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.</span></div>

<div><font face="arial, sans-serif"><br></font><div class="gmail_extra"><span style="font-family:arial,sans-serif;font-size:13px">Worth noting the storage requirements for each contact here are much higher, but for the server this seems pretty easy to deal with.</span></div>

</div></div>