-----BEGIN PGP SIGNED MESSAGE----- Dimitris Tsapakidis <dimitrt@dcs.rhbnc.ac.uk> wrote:

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.

To avoid a trusted intermediary, the problem can be thought of as a secure multi-party communication problem with private inputs, which is much studied in the literature. 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. 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." The solution is reasonably practical, involving scrambled truth tables and bit commitments, and is related to some of Chaum's work on zero-knowledge. The paper is a bit theoretical and hard to read, though. I can write up the protocol if anyone is interested. Hal -----BEGIN PGP SIGNATURE----- Version: 2.6 iQBVAwUBMT8p4RnMLJtOy9MBAQHUAQIAv6tTbhLvTnbxX+7BlSIQcxCBfF+FhL1E mR57Ks8Rklg2PxEotSl9BDEtKWVFoqXg8UdNhsj6d3ASFzdQe0B6Hg== =tCch -----END PGP SIGNATURE-----