Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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
1  
@user24215 You should clarify that in the question. –  cpast May 1 at 0:32
7  
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

1 Answer 1

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.

share|improve this answer
    
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 2 days ago
    
@TruthSerum Yes, all operations are performed in (Z/pZ)* according to the Wikipedia article. –  user24215 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.