[messaging] Proposal for anonymous contact discovery

[David Leon Gil]

My thoughts are along the same lines as Tom's.

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.

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?


Perhaps using a 'fuzzy extractor' on email corpuses might work; I suspect
something more complicated is needed, though.

Leonid Reyzin has a good page on some of his work with Yevgeny Dodis on
fuzzy extractors:
http://www.cs.bu.edu/~reyzin/fuzzy.html (Code even.)

-David

On Friday, July 25, 2014, Tom Ritter <tom at ritter.vg> wrote:

> On 24 July 2014 16:01, Joseph Bonneau <jbonneau at gmail.com <javascript:;>>
> wrote:
> > Thoughts?
>
> This assumes Earl and Layton have a perfect record of all emails
> between them. In practice, I remove sensitive emails from the server
> to prevent an attacker who compromises the server from retroactively
> getting all the good stuff[0]. Also in practice, my parents use POP3
> instead of IMAP[1]. Also in practice, companies have a policy of
> archiving emails after N months into long-term difficult-to-access
> storage. By hearsay, I think some people aggressively delete emails
> instead of filing them away somewhere.
>
> The general idea of establishing a source of high-entropy, shared,
> secret data between two people is the hard one. Figure that out, and
> that entropy can be used in near _any_ protocol to achieve [long term]
> [ratcheting] [key exchange] [symmetric cryptography] [whatever].  It's
> why there's Key Extractors in TLS: agreeing on key material is hard,
> let's use this other key material we agreed on already.
>
> But it occurs to me the SMTP message-id approach is not completely
> sunk because of the assumptions - we just need to open it up to lots
> more messages.  This problem is essentially trying to perform set
> intersection.  I have a bunch of 'secret' bitstrings I think you share
> some of, let's figure out if we do in fact share some. If we do, that
> bitstring can be used as keying material to authenticate a longer-term
> key.
>
> From an algorithm point of view, the work being done in Bitcoin to
> minimize P2P data transfer seems relevant[2]. From a security point of
> view, I don't believe they're trying to protect the bitstrings - but
> if they are in fact random bitstrings, it seems safe to hash them and
> as long as you can't invert the hash you can't learn the bitstring.
>
> -tom
>
>
> [0] Obviously there are degrees of compromise - an attacker who gets
> my IMAP password is less strong than one who has root on a machine
> with the disks.
> [1] They apparently carry the state of {emails I've read, emails I've
> responded to, emails I need to reread, etc} in their heads at all
> times as they move between phone, laptop, and desktop.
> [2]
> http://sourceforge.net/p/bitcoin/mailman/bitcoin-development/thread/CAPkFh0thLcaAPaa7Xswu2vSxossRDziMCoStzTDWw%2Be0c3WqTw%40mail.gmail.com/
>  But those algorithms are also interactive. (At least some of them, I
> think they also talk about non-interactive ones).
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org <javascript:;>
> https://moderncrypto.org/mailman/listinfo/messaging
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140725/b7b2ff97/attachment.html>