Ask HN: Cryptographic salary negotiation protocol? | Hacker News Reader

Ask HN: Cryptographic salary negotiation protocol?

15 pointstwp6 comments

This is a maths/crypto problem. Is there some means by which an interviewer (potential employer) and interviewee (potential employee) can establish whether they have overlapping salary ranges, without revealing the actual ranges to each other?

If possible, this would be a useful first filter to check for employment compatibility, without leaking information for the actual salary negotiations.

More formally, if interviewer Alice has a secret number X (the maximum salary that she is willing to pay), and interviewee Bob has a secret number Y (the minimum salary that he is prepared to accept), is there an exchange of information that allows both parties to establish if X >= Y without revealing Y to Alice or X to Bob? Given that Alice already knows X, and Bob already knows Y, it should not be possible to determine the difference between X and Y from the exchange of information.

This is obviously trivial to solve with the use of a trusted third party. Is it possible to solve without the use of a trusted third party?

I get the nerdy fun of this, but I don't see the benefit. Consider the game theory. If there's no range overlap, it doesn't matter what your signaling is, because the deal isn't going to clear. You're equally well off as an candidate by revealing your ceiling, and as an employer by revealing your floor. Meanwhile, the cryptographic exchange simply defers the real problem of who's going to reveal a number first, because someone has to cough something up to move the protocol forward.

Check out Yao's Millionaires' Problem[1]. It's exactly what you're describing and does not require a third party.

[1]: http://en.wikipedia.org/wiki/Millionaire%27s_Problem

One approach would be for offeror to encode the same "you're hired" message multiple times, using standard salary numbers for the encryption keys, and randomizing their order. If applicant is able to decode one of the encrypted messages with his desired standard salary (and somehow barred from trying multiple times with different numbers) then there'd be no third party necessary.

Preventing multiple attempts would be the challenge with this approach. Alternatively, the "you're hired" message could itself be encrypted such that the applicant could send it back to the offeror to be decrypted. The challenge there is verifying the offeror didn't encode "$50,000" instead of "pay within range". The offeror encoding "no" and "yes" values and sending those two values (but not saying which is which) ahead of time would mitigate that problem, but again not if the applicant is able to run multiple numbers through the system (noting at which point the value changes).

The best solution would be an algorithmic third party search engine which doesn't even mention the job or candidate to each other if there's no overlap in salary, taking less tangible things like years of work experience, education into account.

Great idea. Even if you could solve it with out a thirdparty it seems to me like a thirdparty solution is the way to go in terms usability. What would you name such a thing?

"Hi, I am happy to attend an intervjuv but before I do I need to make sure you can pay with in my range. Please go to www.dowefitinsaleryterms.com/X12xs2 ho is a third party. " Would that work?

This type of problem is called secure two party computation. Tasty looks like a good framework to use for this kind of problems.

http://code.google.com/p/tastyproject/

Won't this just encourage both parties to choose arbitrarily wide ranges, which would cause the first filter to always pass? This would just get us back to where we started, where someone has to say a number first.

Reply on news.ycombinator.com