From: Dimitris Tsapakidis <dimitrt@dcs.rhbnc.ac.uk>
Date: Sun, 10 Mar 1996 06:06:44 +0800
To: cypherpunks@toad.com
Subject: Re: Square pegs in round holes, matchmaking, corporate mailservers
Message-ID: <199603092150.VAA08613@alice.cs.rhbnc.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain


Let's stick one thread this time. I lost track when the Subject header
was changed. Twice! :-)

The original definition of the problem:

>>Bob must find out whether Alice has declared (commited) her interest
>>in him, if and only if he has declared (commited) his interest in her.
>>Before he does so, he can at most know that a girl is interested in
>>him. Another description: Bob and Alice can have a date if they both
>>commit to each other. If only one commits, nobody will ever find out
>>about it.

(PADGETT@hobbes.orl.mmc.com) wrote:

>Instead of using a binary assymetric key, why not a triple ? (Just
>because I do not know of any does not mean that one does not exist).
>Given a triple (tertiary ?) function each individual would only need
>their receive key and a "post office" transmit key. On sending a
>message, it would be encrypted with a session key and the session key
>encrypted with the post office key.

You got me confused. Does this thing exist, or you would like it to
exist? :-)


Bill wrote:

>If Bob wants to talk to Alice, he sends Trent B = g**b, marked
>"For Alice", optionally anonymously. Trent calculates
>X = B**t == g**bt, and sends it to Alice. Alice calculates
>K = X**a == g**bat, calculates H = Hash(K) and posts it anonymously,
>or sends it to Trent to post or mail to Bob. If Alice wants to talk
>to Bob, she calculates A = g**a mod p, sends it to Trent, optionally
>anonymously, marked "For Bob". Trent calculates Y = A**t == g**at ,
>and sends it to Bob. Bob calculates K' = Y**b == g**abt, calculates
>H' = Hash(K') and notices that it's the same as the H he pulled off
>the net earlier. Bob says "Oh, wow! Alice wants to talk to me!",
>encrypts some lame drivel of a message M with key K'==K, and mails
>it to Alice if he knows her address or posts it with Subject: H',
>which Alice receives.

on which Hal commented:

>I don't think this satisfies the requirements. Once Bob calculates H'
>and sees that it matches H, he knows that Alice likes him, but Alice
>doesn't know that he likes her. The whole point of the protocol was to
>be fair. Bob must only learn that Alice likes him if Alice is
>guaranteed to learn that he likes her.

Correct. I believe my hash_k is equivalent to your **t (which I thought
as well, but preferred to use hash_k in my original description). Hence,
my "mediated off-line" protocol can also be written as:

- Bob, who likes Alice, sends [g**ab, pseudo(B)] to Trend who posts
  [g**abt, pseudo(B)]. Alice learns nothing at this point.
- If she ever decides she likes Bob, she sends [g**ab, pseudo(A)] to
  Trend, who posts [g**abt, pseudo(A)].

So Bob and Alice notice
g**abt, pseudo(B) and
g**abt, pseudo(A)
being posted so they know they have a match.

Somebody who knows t can only find out who is interested in them.
Nothing more.

T could possibly be replaced by n T(i)'s each of whom has a secret
key t(i). But this is another thread.


Hal added:

>The easiest formulation is pairwise:
>Alice and Bob mutually engage in the calculation of "Alice loves Bob"
>AND "Bob loves Alice". Each inputs his feelings as an input bit, and
>the output will be true only if they have mutual feelings.
>Each pair of potential lovers would then go through the protocol with
^^^^^^^^^^
>each other.

Assuming we have a fair AND protocol, Alice cannot initiate it with
Bob, because this would demontrate her interest. Solutions:

1) You can force all possible pairs to execute the protocol, as you
said, but is not very practical.

2) Alice could initiate the protocol even if she is not interested,
in order to "hide" the cases when she is genuinely interested. Not
very practical, either.

3) My proposal (protocol 3 in my previous posting) is that Alice
approaches Bob anonymously. But they can't execute the AND gate,
because Bob doesn't know who she talks to. What they compare is:
Alice's number: g**ab and Bob's number: g**bx where x is the
girl he likes.

>This problem is solved in "Multiparty Computations Ensuring Privacy of
>Each Party's Input and Correctness of the Result", by Chaum, Damgard,
>and van de Graaf, in the proceedings of the Crypto 87 conference. They
>even discuss this application directly: "Note that this AND-gate
>computation, where both parties want to hide their input from each
>other, has a meaningful application: consider the situation where Alice
>and Bob have just met, and each considers dating the other. Neither
>wishes to lose face in the following sense: if Alice wants a date but
>Bob doesn't, Alice does not want to let Bob know that she wanted the
>date. And the same holds for Bob. In other words: if a party does not
>want the date it does not find out the other party's decision."

Thanks, I will have a look. This will only work if there is a law
forcing newly met pairs of people to enter the protocol, as in
(1) above, right?

  Dimitris


-- 
Dimitris Tsapakidis               PGP keyID: 735590D5
dimitrt@dcs.rhbnc.ac.uk           MSc in Information Security,
This space reserved               Royal Holloway, University of London
for future use.                   Origin: Thessaloniki, Macedonia, Hellas