Alice and Bob's crush

Suppose Alice and Bob both want to determine whether the other has a crush on him/her, but they only wish to share the information if the crush is mutual. Is there a cryptographic protocol that makes this possible without using trusted third parties? It is safe to assume that they will not lie during their "encrypted announcement" to the other.

-
Impossible. If bob says "yes" and alice says "no" then they learn that their answers are not the same, so the other person's must be the opposite. So they know the other person's. –  mikeazo Apr 30 at 23:55
@mikeazo But what if their answers are dependent somehow on, say, their personal private keys? Bob's answer for "no" would then be different than Alice's answer for "no", so Alice would not learn anything about Bob's answer it is different than hers. –  user24215 May 1 at 0:01
If Bob has a crush on Alice, and they go through this protocol, he either learns that there's a mutual crush (which is fine) or that there's no mutual crush (in which case he knows Alice doesn't have a crush on him). Basically, the only way "there's no mutual crush" doesn't mean "you don't have a crush on me" is if I don't have a crush on you. –  cpast May 1 at 0:26
@user24215 You should clarify that in the question. –  cpast May 1 at 0:32
Lets just ask the obvious here, @user24215 who do you have a crush on, and does she/he know enough about cryptography to participate in the scheme we are trying to figure out? :P –  Vincent Advocaat May 1 at 8:57

Covert two-party/multi-party computation provides exactly what you're looking for. The two-party case was introduced by von Ahn, Hopper, and Langford, and a more formal definition and multi-party protocol was given by Chandran, Goyal, Ostrovsky and Sahai.

Covert secure computation even hides whether or not the parties participated in the computation at all, unless the result of the computation determines that it should be revealed. For Alice and Bob, their inputs would be one bit each, indicating whether each is romantically interested in the other, and the function to be computed on these bits is AND. If the function output is 1, then that fact is revealed to both of them and they live happily ever after. Otherwise, they don't even learn whether the other even played the protocol. So if Bob likes Alice but not vice-versa, Alice won't even learn that Bob participated at all, thus saving him from eternal embarrassment in her presence.

The von Ahn et al paper gives many more applications of the concept, e.g., two undercover spies from allied countries who may want to collaborate.

-

You could ask Alice and Bob to rate their "affection" for one another using some scale, then apply a protocol for the Socialist Millionaire's Problem (a variant of Yao's Millionaire's Problem) to determine whether the values are equal.

If the scale is finite (say, in the range from 1-10), then a party can learn some information about the other's value by selecting the max or min. Using an open-ended scale would eliminate this problem, but might make "crush equality" a remote possibility.

-
So, if I understand it, Alice computes h^a (her affection), Bob computes h^b (his affection), then they both compute h^ab = h^ba, and they can then compare for equality without revealing their affection to eachother. I could not see the requirement that these operations be carried out modulo a prime number on the Millionaire's problem wiki page. Can you confirm that this is necessary for the scheme to be secure? –  TruthSerum May 1 at 22:54
@TruthSerum Yes, all operations are performed in (Z/pZ)* according to the Wikipedia article. –  user24215 May 1 at 23:24
Sociallist's millionaire problem is wrong in this case, because it answers the function $x=y$. If both input no, they shouldn't be informed that their input was equal. Even worse: This reveals both inputs to both parties: They know their own input, and they learn if their input was equal. So in either case, the other input can be derived. –  tylo May 4 at 12:20
This idea depends on Alice and Bob using a scale with more than two values to "rate their affection" for one another. In this case, they only learn if their selected values are equal. –  rphv May 4 at 14:58
@tylo You could always first map the yes/no into integers, associating 0 to 'yes' and a random number to 'no' before applying the SMP so that with high probability no information is leaked if both wish to answer 'no'. –  eltrai May 19 at 15:22

Ah, cryptographically secure tinder

If Alice and Bob also broadcast messages to many other with non-yes answers then the other party wouldn't be able to tell the difference between a "no" and a "did not choose"

In this case, the "yes" does get a "no" (atleast, "not interested") from the other party, but the "no" doesn't know the other party chose yes.

However, we really want the two "yes" votes to be revealed simultaniously.

Or, maybe have a way that if Alice says yes but Bob says no, then Alice can change her yes to no before bob can read it... but somehow, we need a way that Alice can't change a yes to no if bob also answers yes.

Another approach might be to for Alice and Bob to send their yeses before they reveal their identity?

-

If Alice and Bob express their interest in the other party as a single bit (say 1 for 'crush' and 0 for 'not crush'), essentially what you want is for Alice and Bob to privately compute the logical AND of their two bits.

If you also assume they will not lie in their interaction (i.e., they are at most passively corrupted), then there is a simple solution using Oblivious Transfer. The solution is described in this answer: crypto.stackexchange.com/questions/20864/secure-multiparty-computation-of-conjunction/20871#20871

-