17
$\begingroup$

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for a company that Alice is applying to, also has a number in mind: the maximum acceptable salary that he is willing to pay to fill the position—let's call this value B.

  • Bob wants be sure that at least B >= A is true before spending the time to interview Alice.
  • Bob does not want Alice to know the exact value of B, because then she would be in a superior position to negotiate a salary as close to B as possible.
  • Alice would also like to know if B >= A is true, for the same reasons as Bob.
  • Likewise, Alice does not want Bob to know the exact value of A, because then Bob would be in a superior position to negotiate a salary as close to A as possible.

I'm curious if there is a known cryptographic protocol that would allow Alice and Bob to exchange some information and conclusively determine the result of B >= A, without revealing any additional information about the actual value of B to Alice or the value of A to Bob.

Caveats:

  • The use of a third party is not allowed.
  • Ignore the fact that the repeated use of such an algorithm with different values of A would allow Alice could learn the approximate value of B. Assume that neither party is allowed to change their value.

Does such an algorithm exist? If not, is such a solution even possible?

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ See Yao's Millionaires' Problem, and more generally the class of problems and protocols which fall under the heading of Secure Multiparty Computation. $\endgroup$
    – sju
    Commented Nov 5, 2015 at 3:44
  • $\begingroup$ @sju but that would need multiple queries, for Alice to come close to B's number. $\endgroup$
    – sashank
    Commented Nov 5, 2015 at 4:07
  • 1
    $\begingroup$ @sashank I'm sorry, I don't follow. Alice being able to approximate $b$ is not desired, and further Alice's ability to approach it with arbitrarily many queries would be a consequence of any solution to the problem (at least within the problem space of salary negotiations). The original question noted that computation of the inequality would be limited to one occurance, so as to ignore that case. $\endgroup$
    – sju
    Commented Nov 5, 2015 at 4:30
  • 1
    $\begingroup$ @sju There is not much to add, but it would be nice to have that answer in an actual answer instead of the comments. $\endgroup$
    – tylo
    Commented Jul 21, 2016 at 9:55
  • 2
    $\begingroup$ You might be interested in the Myerson-Satterhwaite theorem in Mechanism Design which implies that there is no set of rules for this negotiation such that Bob will always hire Alice when B>=A and such that neither party ever has incentive to back out of the resulting deal. en.wikipedia.org/wiki/Myerson%E2%80%93Satterthwaite_theorem $\endgroup$
    – CommonerG
    Commented Jul 21, 2016 at 13:54

1 Answer 1

Reset to default
18
$\begingroup$

Solutions to Yao's Millionaire's Problem should suffice for this computation. In that setup, there are two parties each with an input. The output reveals whose input is larger, and nothing else.

So Alice and Bob just run the protocol with their respective inputs A and B.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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