2
$\begingroup$

I am very interested to know in the general sense how two parties who know each other are able to continue a conversation IF and ONLY IF they both earn the same salary. For example, we have a person X who earns 75000USD, but they only want to continue speaking to person Y IF and ONLY IF person Y also earns 75000USD. They do not really know how much person Y earns but much rather they get a bit of some sort similar to a signature where b=0 if personXSalary != personYSalary and b=1 if personXSalary == personYSalary. Only if b=1, then does person X know the actual salary of person Y

My question is, how would one instantiate such a public key encryption scheme to ensure this? I was thinking of something along the lines of Zero Proof Knowledge but then MACs also was another thought

$\endgroup$
  • 2
    $\begingroup$ Socialist Millionaires $\endgroup$ – kelalaka Aug 21 '19 at 0:21
  • 2
    $\begingroup$ Actually, if they're trying to negotiate and want to succeed only if their salary is the same, any PAKE (Password Authenticated Key Exchange) protocol (with the salary as the password) works nicely... $\endgroup$ – poncho Aug 21 '19 at 1:46
  • $\begingroup$ @poncho thanks for your suggestion. the only thing is person X who only knows their salary can only go by the bit b that is sent back by person Y. So if the salary of person X & person Y are the same, then b=1. If person X receives the b bit = 1 then they will continue communications. Otherwise the protocol is ended. How could I go about designing it $\endgroup$ – usr7337x987986985 Aug 21 '19 at 6:22
  • $\begingroup$ @kelalaka thanks for your suggestion. the only thing is person X who only knows their salary can only go by the bit b that is sent back by person Y. So if the salary of person X & person Y are the same, then b=1. If person X receives the b bit = 1 then they will continue communications. Otherwise the protocol is ended. How could I go about designing it $\endgroup$ – usr7337x987986985 Aug 21 '19 at 12:39
  • 1
    $\begingroup$ @usr7337x987986985 poncho's suggestion does exactly what you want. A PAKE will report success (the code may return b=1 in response) only if the inputs are identical, which also covers the case of if the salary numbers are identical or not. $\endgroup$ – Natanael Aug 21 '19 at 12:52
1
$\begingroup$

By using SPAKE2, we can achieve this as Poncho said in comments.

  • Let $s_a$ be the salary of Alice
  • Let $s_b$ be the salary of Bob
  • Let we have Ed25519 curve with the base point G.

Exchange part;

  1. Alice pics a random scalar $x$ and calculates $X = x\cdot G$ and $T = s_1\cdot M+X$, where $M$ is another point on ECC and sends the value $T$ and $M$ to Bob (pake message).

  2. Bob pics a random scalar $y$ and calculates $Y= y\cdot G$ and $S = s_2\cdot N + Y $, where $N$ is another point on ECC and sends the value $S$ and $N$ to Alice.

Key calculation part:

  • $Key_{Alice} = x ( S - s_a \cdot N) = x ( s_b N + Y - s_a N ) = x(s_b - s_a)+xyG $
  • $Key_{Bob} = y ( S - s_b \cdot M) = x ( s_a M + X - s_b M ) = x(s_a - s_b)+xyG $

if $s_a = s_b$ then we will have a cancelation to $xyG$ on both sides. Now, two sides can assume that they have a key agreement, without knowing the equality. They can encrypt pre-agreed plaintexts and sent each other, after this, they can conclude that their salaries are the same if the decryptions are successful, they conclude otherwise if not successful.

After the conclusion of success, one can convert the result into a bit $b$ by;

if p1 == Dec(xyG,c1)
   return 1
else
   return 0
|improve this answer|||||
$\endgroup$
  • $\begingroup$ How would I incorporate the bit b? $\endgroup$ – usr7337x987986985 Aug 23 '19 at 2:15
  • 1
    $\begingroup$ if $( p_1 == Dec( xyG, c_1)$ then return 1, isn't enough? $\endgroup$ – kelalaka Aug 23 '19 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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