百万富翁问题

介绍

• 姚期智(2000年图灵奖获得者)
• 1982年姚期智提出百万富翁问题
• 问题描述

A 资产i亿元,B 资产j亿元,其中,通过一个规则比较两个人的财富但是不会告诉彼此的财富值

• 有十个箱子，每个箱子都有锁。(锁是公钥,钥匙是私钥)
  • A有钥匙,可以打开箱子
  • B没有钥匙,但是可以关上箱子的锁（B没有私钥,但是有公钥）
  • A的财富为i亿元,找到第i个箱子，并将i之前的箱子都装数值0，i以及i之后的箱子全部装数值1，B的资产为j亿元,B找到第j个箱子,并拿出这个箱子交给A同时将j之外的其他箱子烧毁，A有钥匙打开箱子，出现两种结果
    • 箱子里面的值为0，
    • 箱子里面的值为1,

具体比较步骤

• B(有公钥,没有私钥)的操作

  • B选取一个大数字X，通过

    • 公钥加密得到结果K,即
    • 私钥解密

  • 计算 ,把m这个数字传给A

• A(有公钥,有私钥)的操作

  • 计算
  • 解密 并且
    • 对应得到
  • 取模==，其中p为质数==
    • 对应得到
  • A的资产为i亿元，令数值不变,将每个数值加上1并所有值传给B

• B最终检验A传递过来的值

  • B只需要关注,因为
  • 将B一开始选取的大数字X对P进行取模运算,即
  • 如果，说明并没有进行+1操作,所以为前一部分不变数值的范围中的数值,所以
  • 如果，说明进行+1操作,所以为后一部分数值的范围中的数值,所以