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