想象一下爱丽丝正在申请一份新工作。爱丽丝（Alice）有一个她愿意接受的最低薪水的概念-将此值称为A。鲍勃，爱丽丝正在申请的一家公司的招聘经理，还牢记一个数字：他愿意为填补该职位而愿意支付的最高可接受薪水-我们将此值称为B。


鲍勃（Bob）希望在花时间采访爱丽丝之前至少要确保B >= A是真实的。
出于与鲍勃相同的原因，爱丽丝还想知道B是否为真。
爱丽丝也不希望鲍勃知道B的确切值，因为这样鲍勃（Bob）会处于优势地位，以协商尽可能接近B >= A的薪水。

我很好奇是否存在一种已知的加密协议，该协议将允许爱丽丝（Alice）和鲍勃（Bob）交换一些信息并最终确定A的结果，而不会透露有关实际值的任何信息

注意：


不允许使用第三方。
忽略重复使用具有不同A值的这种算法的事实将使Alice可以学习B >= A的近似值。假设任何一方都不允许更改其值。

是否存在这样的算法？如果没有，那么这样的解决方案是否可能？

评论

请参阅姚的百万富翁问题，更常见的是属于安全多方计算的问题和协议类别。
@sju，但这需要多个查询，以使Alice接近B的数字。
@sashank对不起，我没有关注。爱丽丝不希望能够近似$ b $，并且进一步爱丽丝能够任意处理许多查询的能力将是对该问题的任何解决方案的结果（至少在薪金谈判的问题空间之内）。最初的问题指出，不等式的计算将仅限于一种情况，从而忽略了这种情况。
@sju没有太多要添加的内容，但是最好将其包含在实际答案中而不是注释中。
您可能会对机制设计中的Myerson-Satterhwaite定理感兴趣，这意味着该协商没有一套规则，以使Bob总是在B> = A时聘用Alice，并且任何一方都没有动机退出该规则。由此达成的交易。 zh.wikipedia.org/wiki/Myerson%E2%80%93Satterthwaite_theorem

#1 楼

姚的百万富翁问题的解决方案应足以进行此计算。在该设置中，有两个参与者，每个参与者都有一个输入。输出显示出谁的输入更大，什么都没有。

所以Alice和Bob只是使用各自的输入A和B运行协议。