<div dir="ltr">Here's a protocol sketched over lunch today with Ian Goldberg and Nik Unger:<div><br></div><div>Goal: Earl (an early adopter) downloads and installs the newest SecureChatApp, which creates a new public key for Earl and uploads this to the SecureChatApp servers. Later on, Earl's friend Layton (a late adopter) downloads SecureChatApp which, recognizing Earl in Layton's contact book, fetches Earl's key from the SecureChatApp servers. Of course we want not only for the servers to not learn that Earl and Layton are friends, but not to learn that Earl and Layton are using the app at all (which may require the communication all happens over Tor for high assurance). So the app shouldn't learn any identifying info about Earl, even though Layton has to later be able to find Earl. Also, Layton doesn't want to bother all hundred of his contacts by asking if they're using SecureChatApp, or maybe actively doesn't want to broadcast that he's using it except to people already using it.</div>

<div><br></div><div>Non-solution: Have Earl upload a hash of his phone number, email address, or other known identifier. These can be searched over.</div><div><br></div><div>Potential solution: Use shared entropy Earl and Layton already both know. Suppose they're already communicated over SMTP. Earl takes the most recent email message he sent to Layton and uses this to derive a master key K. We're assuming here the email has enough entropy (should hold, esp. with the Message-ID) that it can't be searched over.</div>

<div><br></div><div>Using this key K, Earl encrypts and MACs his public key and other addressing info (maybe an ID) and posts it to the server. When Layton signs up, he derives the same key K by hashing the most recent email received from Earl and checks to see if this exists at the server. This can be done in a few ways: downloading the whole (or part of) the database, PIR, or generating a lookup index by another hash of K. If K exists, Layton can decrypt Earl's info and they can now talk.</div>

<div><br></div><div>Efficiency improvement: Obviously, Layton may have a more recent received email from Earl by the time he signs up. Solution: Layton scans forward from the beginning of time and hashes every email received from Earl. Derive K from the email with the lowest hash. If that K doesn't exist, it may simply mean Earl joined before that email was sent. So, recursively do this for all earlier emails than that. This should take lgN queries at most if N emails have been received.</div>

<div><br></div><div>Security improvement: This is vulnerable to Earl and Layton's email providers. You could also design this over SMS. Perhaps you can use both (if available) to make it harder for anybody but Earl/Layton to derive K.</div>

<div><br></div><div>Thoughts?</div></div>