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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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