<div>My thoughts are along the same lines as Tom's.<br></div><div><div><br></div><div>The following model seems interesting: A and B are non-empty sets (each element having sufficient entropy for the desired security strength). Alice knows A, Bob knows B. Eve knows E ⊂ A ∪ B.</div>
<div><br></div><div>Suppose that everyone knows that A ∩ B ≠ ∅, C-E ≠ ∅, and C ∩ E ≠ ∅ . Is there an (efficient) protocol that Alice and Bob can execute that provides computational (unconditional?) security even if they don't know A ∩ B or E?</div>
<div><br></div><div><br></div><div>Perhaps using a 'fuzzy extractor' on email corpuses might work; I suspect something more complicated is needed, though.</div><div><br></div><div>Leonid Reyzin has a good page on some of his work with Yevgeny Dodis on fuzzy extractors:</div>
<div><a href="http://www.cs.bu.edu/~reyzin/fuzzy.html">http://www.cs.bu.edu/~reyzin/fuzzy.html</a> (Code even.)</div></div><div><br></div><div>-David</div><div><br>On Friday, July 25, 2014, Tom Ritter <<a href="mailto:tom@ritter.vg">tom@ritter.vg</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 24 July 2014 16:01, Joseph Bonneau <<a href="javascript:;" onclick="_e(event, 'cvml', 'jbonneau@gmail.com')">jbonneau@gmail.com</a>> wrote:<br>
> Thoughts?<br>
<br>
This assumes Earl and Layton have a perfect record of all emails<br>
between them. In practice, I remove sensitive emails from the server<br>
to prevent an attacker who compromises the server from retroactively<br>
getting all the good stuff[0]. Also in practice, my parents use POP3<br>
instead of IMAP[1]. Also in practice, companies have a policy of<br>
archiving emails after N months into long-term difficult-to-access<br>
storage. By hearsay, I think some people aggressively delete emails<br>
instead of filing them away somewhere.<br>
<br>
The general idea of establishing a source of high-entropy, shared,<br>
secret data between two people is the hard one. Figure that out, and<br>
that entropy can be used in near _any_ protocol to achieve [long term]<br>
[ratcheting] [key exchange] [symmetric cryptography] [whatever]. It's<br>
why there's Key Extractors in TLS: agreeing on key material is hard,<br>
let's use this other key material we agreed on already.<br>
<br>
But it occurs to me the SMTP message-id approach is not completely<br>
sunk because of the assumptions - we just need to open it up to lots<br>
more messages. This problem is essentially trying to perform set<br>
intersection. I have a bunch of 'secret' bitstrings I think you share<br>
some of, let's figure out if we do in fact share some. If we do, that<br>
bitstring can be used as keying material to authenticate a longer-term<br>
key.<br>
<br>
>From an algorithm point of view, the work being done in Bitcoin to<br>
minimize P2P data transfer seems relevant[2]. From a security point of<br>
view, I don't believe they're trying to protect the bitstrings - but<br>
if they are in fact random bitstrings, it seems safe to hash them and<br>
as long as you can't invert the hash you can't learn the bitstring.<br>
<br>
-tom<br>
<br>
<br>
[0] Obviously there are degrees of compromise - an attacker who gets<br>
my IMAP password is less strong than one who has root on a machine<br>
with the disks.<br>
[1] They apparently carry the state of {emails I've read, emails I've<br>
responded to, emails I need to reread, etc} in their heads at all<br>
times as they move between phone, laptop, and desktop.<br>
[2] <a href="http://sourceforge.net/p/bitcoin/mailman/bitcoin-development/thread/CAPkFh0thLcaAPaa7Xswu2vSxossRDziMCoStzTDWw%2Be0c3WqTw%40mail.gmail.com/" target="_blank">http://sourceforge.net/p/bitcoin/mailman/bitcoin-development/thread/CAPkFh0thLcaAPaa7Xswu2vSxossRDziMCoStzTDWw%2Be0c3WqTw%40mail.gmail.com/</a><br>
But those algorithms are also interactive. (At least some of them, I<br>
think they also talk about non-interactive ones).<br>
_______________________________________________<br>
Messaging mailing list<br>
<a href="javascript:;" onclick="_e(event, 'cvml', 'Messaging@moderncrypto.org')">Messaging@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/messaging" target="_blank">https://moderncrypto.org/mailman/listinfo/messaging</a><br>
</blockquote></div>