A wants to buy a company from B. Before A and B enter negotiations, they want to make sure that there actually is a zone of potential agreement. Obviously, they don't want to communicate their reservation prices to the other party (A only buys for less than 100m, B only sells for at least 90m). So they both communicate their reservation price to a trusted mediator who then tells them whether or not negotiations makes sense.

Is there a protocol that A and B can use to find out the same thing without having to trust the other and any third parties?

  • 3
    $\begingroup$ I think you're looking for a zero-knowledge proof (w/o trusted third parties) whether $a\geq b$ with $a,b$ staying secret. This is exactly Yao's Millionaire's Problem $\endgroup$ – SEJPM Jan 6 '16 at 16:08
  • $\begingroup$ This would actually be multi-party computation, rather than just zero-knowledge proofs. ​ ​ $\endgroup$ – user991 Jan 6 '16 at 17:03
  • $\begingroup$ @SEJPM Please remember to “use comments to ask for more information or suggest improvements. Avoid answering questions in comments. Thanks $\endgroup$ – e-sushi Jan 6 '16 at 17:13
  • $\begingroup$ Heh, not only is there a solution but I was thinking of making fully oblivious "negotiation" a couple years back using oblivious (MPC) SAT solvers. The idea is to allow each party to enter their bargaining positions as logical terms (boolean formulas). The oblivious SAT solver would operate over a conjunction of the parties terms to find a satisfying assignment. In your case you'd just want to know that a satisfying assignment was found. $\endgroup$ – Thomas M. DuBuisson Jan 6 '16 at 21:51
  • 1
    $\begingroup$ A somewhat related problem would be how to eliminate the risk of collusion. Suppose A is working with C, who is the "real" prospective buyer from B. A proposes a maximum price that is lower than what C is prepared to pay, and communicates the result to C, before C and B executes the protocol. This way C is able to start the negotiation with an offer that leads to a final price that is closer to B's minimum. $\endgroup$ – Henrick Hellström Jan 6 '16 at 23:45

Is there a protocol that A and B can use to find out the same thing without having to trust the other and any third parties?

There is. Even more than one.
Your problem actually is equivalent to Yao's Millionaire's Problem.
You have two numbers which two parties want to keep secret and you want both parties to find out whether the one is larger than the other, i.e. compare $a\geq b$ with $a$ being the maximal price willing to be paid by A and $b$ being the least price for which B would sell.

The secure multiparty protocols (credit goes to Ricky for pointing that out) to solve this are various. Because they aren't easy and it's better if you get them from source I'll quickly name three (better protocol suggestions are welcomed):

  • $\begingroup$ Why are you proposing these? The best is generic Yao, but this citation to Yao won't give any information. Also, it is possible to do this very efficiently even for malicious adversaries using modern solutions. $\endgroup$ – Yehuda Lindell Jan 7 '16 at 9:01
  • $\begingroup$ @YehudaLindell, I proposed these, because they were the first ones I found. I've now linked to a full version of Yao's text. Would you mind sharing the "very efficient [...] modern solutions" (as per "better protocol suggestions are welcomed") or posting an answer on your own? $\endgroup$ – SEJPM Jan 7 '16 at 11:33
  • $\begingroup$ I have posted an extension to your answer; thanks. $\endgroup$ – Yehuda Lindell Jan 7 '16 at 14:35

This is an extension of @SEJPM's answer. I want to expand on what protocols are best to use (I apologize ahead of time for self citations). First, for details on Yao's protocol, see A Proof of Security of Yao's Protocol for Two-Party Computation. However, to do this very efficiently, you need to have two very efficient components:

  1. A fast garbling scheme: see JustGarble and this alternative. Code for garbling can be found in the open source SCAPI library on Github.

  2. Fast oblivious transfer: when you need to run many, then oblivious transfer extensions should be used. See this paper for the fastest current protocol. (It's implementation can also be found at SCAPI.)

Another alternative is to run the GMW protocol based on oblivious transfer extensions. See GMW vs Yao and here.

The above all relates to semi-honest adversaries. If you want security for malicious adversaries, then you need to work much harder. Here it depends if you want a single execution of multiple executions (where you prepare ahead of time). For a few choices see: here, here and here. The last of these also has code at SCAPI.

This is a very biased list (which I really apologize for) and there are lots of other alternatives out there. However, I've tried to give you things that also have available code and support. You can find citations to lots of other work inside the papers I've pointed to.


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.