百科问答小站 logo
百科问答小站 font logo



姚期智院士有哪些学术贡献? 第1页

  

user avatar   wdwind 网友的相关建议: 
      

Yao's Millionaires' Problem 是一个有趣但复杂的问题,其描述如下:两个富翁如何能够在不暴露具体资产的情况下,比比谁更壕呢?

类似场景还有:公司同事想在不暴露具体工资的情况下看看谁挣得更多;闺蜜们想在不暴露体重的情况下比比谁更瘦;基友们想在不暴露具体数据的情况下比比谁更长。。。凡此种种,都属于 Yao's Millionaires' Problem。

形式化一下这个问题:爱丽丝为,鲍勃为,谁更大?即,是否有?


==============

我们先看一下问题的简化版:不比较的相对大小,只看二者是否相等,即是否有?

对于简化版问题,Twisted Oak 给出了一个非常直观的理解。

假设且,鲍勃首先需要准备4个密码箱并打上标记:

之后鲍勃丢弃掉除标有的箱子之外的所有钥匙(因为对于鲍勃,)。

之后鲍勃把所有箱子给爱丽丝,由于,爱丽丝向标有的箱子内投入纸条YES,向其他箱子投入纸条NO,并将箱子返还给鲍勃。

这时鲍勃用自己仅有的一把钥匙打开标有的箱子,显然里面的纸条是NO,则此时鲍勃知道了,同时不清楚的具体数值。

注意这只是一个非常直观的解释,可以帮助人理解算法的大体流程和原理,实际的细节要复杂很多。比如“密码箱”其实代表着非对称加密算法,而上文加粗的一句话“鲍勃丢弃钥匙”更代表着算法的核心思想:如何让鲍勃只能打开一个箱子(Oblivious Transfer)?


==============

回到原始问题,爱丽丝为,鲍勃为,是否有?

让我们仍旧假设且,相对于简化版问题,算法会复杂一些。基本思想如下:

首先鲍勃生成一个随机数,这里不妨令,鲍勃将 (即)发给爱丽丝。

由于,因此爱丽丝并不知道和的具体数值,他需要做的是,对每个,令 ,并将所有发回给鲍勃。显然,在本例下,。

鲍勃这时只需要查看返回数组中的第2个数,如果,则说明,反之有。


很明显上面的原理是 naive 的,仍旧会暴露的具体数值,这是由于实数域的有序性和加减的可逆性。Yao 转换数域并用加密算法包装了上面 naive 的过程,避免了多余信息的暴露。具体如下:

  1. 鲍勃生成一个-bit 随机数,并令,其中为非对称加密算法中的一个密钥。
  2. 鲍勃将发送给爱丽丝。
  3. 爱丽丝生成一组数,其中,其中为里的第个数,为非对称加密算法中的另一个密钥。
  4. 爱丽丝生成一组数,其中,而为一个-bit 的质数来保证中数值至少相差。
  5. 爱丽丝生成一组数,其中 。
  6. 爱丽丝将发回给鲍勃。
  7. 鲍勃计算,并将其与比较,如果,则显然,反之有。




聪明的知友们,现在理解 Yao's Millionaires' Problem 了吗?




  

相关话题

  如何用 IT 业者能听懂的话介绍量子计算的原理? 
  什么是函数式编程思维? 
  量子退相干到底是什么意思? 
  如何看待 2021 年图灵奖授予美国计算机科学家 Jack J. Dongarra? 
  如何看待 2021 年图灵奖授予美国计算机科学家 Jack J. Dongarra? 
  计算复杂性理论是否具有足够的现实意义,如今有哪些比较「现实」的应用? 
  姚期智院士有哪些学术贡献? 
  Yann LeCun、Geoffrey Hinton或Yoshua Bengio能得图灵奖吗? 
  姚期智院士有哪些学术贡献? 
  请问自旋为二分之一粒子有俩个态-1/2,1/2。自旋为1的粒子有三个态1,0,-1。是怎么求出来的? 

前一个讨论
突然想到一个问题:0.9999999… 真的等于 1 吗?
下一个讨论
怎么证明这个积分不等式?





© 2025-04-04 - tinynew.org. All Rights Reserved.
© 2025-04-04 - tinynew.org. 保留所有权利