<div dir="ltr"><p>On May 26, 2014 5:28 PM, "Adam Langley" <<a href="mailto:agl@imperialviolet.org" target="_blank">agl@imperialviolet.org</a>> wrote:<br></p><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">


Rather than using group signatures, a user and their home server share a HMAC<br>
key, k. During the introduction protocol, a number of pairs are exchanged.<br>
Each pair contains a private key, x, and HMAC(k, y), where y is the public<br>
key for x.<br>
<br>
Delivery attempts contain (msg, y, HMAC(k,y), sig(msg, x)). The server can<br>
check the HMAC because it holds the HMAC key. The recipient can find who<br>
sent a message because they know who a given public key was given to. A<br>
sender's pool of pairs is refreshed in the normal exchange of messages.<br>
<br>
Once accepted, a server records HMAC(k, y) and rejects it in the future.<br>
<br>
Now a revocation involves sending a list of HMAC(k, y) values to the server<br>
to be "crossed off". This storage grows without bound, but very slowly. All<br>
the problems with messages bouncing and needing to be resigned are solved. So<br>
is the problem of having pending revocations when performing the introduction<br>
protocol.<br></blockquote><div><br></div><div>There's a space optimization for the server I proposed here: <a href="https://moderncrypto.org/mail-archive/messaging/2014/000292.html">https://moderncrypto.org/mail-archive/messaging/2014/000292.html</a> </div>

<div><br></div><div>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.</div>

<div><br></div><div>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.</div>

<div><br></div><div>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. <br>

</div></div>
</div>