[Cryptography] Anonymous rendezvous (was Business opportunities in crypto)

[Jerry Leichter]

>>>> Anonymous rendezvous is a vexing problem.
>>> When you put it that way, it sounds pretty impossible.
>> Sounds pretty much reducible to PSSK.
> 
> Excuse my ignorance, but can you spell out PSSK?
I believe he was referring to Pre-Shared Secret Key, though we usually just use PSK.

> Anonymous rendezvous is not entirely impossible. During the discussion in the DNSSD working group, we saw one plausible proposal. Assume that each of the parties has a public/private key pair, that authorized peers know the public key of the party with which they want to rendezvous, and that this public key is otherwise kept hidden from third parties. In short, the public key is treated as a shared secret between parties authorized to discover the owner of the key pair....
Talking about the cryptography hides the fundamental underlying problem:  If Alice wants to establish a secure connection to Bob, she needs to know *something* about Bob that lets her identify him.  If "Bob" is just a three-character sequence to Alice and she knows absolutely nothing else about him, Mallory walking up to her and saying "Hi, I'm Bob" cannot, even in principle, be distinguished from one from Bob walking up to here and saying exactly the same thing.  And further, if everything that Alice knows about Bob is also known to Mallory, the same applies (and certainly if everything about Bob is public).

Much of the discussion about asymmetric cryptography fails to consider this.  Sure, if Bob has a public key that Alice knows, she can send him a message only he an apply to.  But that just pushes the problem back a level:  How did Alice know that the public key corresponds to the "Bob" that she wishes to talk to, if she knows nothing at all about Bob to begin with?

At some point, Alice needs either to (a) have access to secret information shared only by her and Bob; or (b) trust some third party who already knows who the "right" Bob is and who can give her appropriate identifying information (Bob's known-correct public key; or a Kerberos-style secret that the third party hands to her and Bob).  And how did that third party get to know which the right "Bob" is?  We haven't actually solved the problem, just pushed it around.

There is a real-world alternative which actually ends up just reducing to this:  The classic spy trope in which a dollar bill is ripped in half, with a half going to each participant.  You can view this as like a Kerberos ticket (with the implicit assumption that a torn half of a dollar bill can't be accurately duplicated, which works for a physical object but for a set of bits which can always be duplicated you need secrecy); or by saying that Alice doesn't really know that she has a connection to "the right Bob"; what she can really say is that she has a connection to "the holder of the other half of of this dollar bill."  Binding that notion of identity to "Bob" requires another step - typically by the third party who gave the bills to them.

                                                        -- Jerry