From: Hal <hfinney@shell.portal.com>
Date: Fri, 8 Mar 1996 05:36:51 +0800
To: cypherpunks@toad.com
Subject: Re: Square pegs in round holes, matchmaking, corporate mailservers
Message-ID: <199603071824.KAA17363@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


-----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-----