其他
一起学MPC:(一)百万富翁问题
问题描述:Alice有亿元,Bob有亿元,为方便描述,我们限定。现在想在不暴露和的情况下,比较和的大小。
解决思路:假设有10个宝箱,编号为1到10,Alice可以打开这10个箱子,而Bob不能。第一步:Alice找到编号为的箱子,并将编号为1到的箱子里都放个纸条"no",编号为到的箱子里放个纸条"yes",然后锁上箱子。第二步:Bob根据自己的资产选择编号为的箱子,并把这个箱子的编号撕掉并返回给Alice。(撕掉编号是为了让Alice也不知道Bob到底选了哪个箱子)第三步:Alice把Bob发的箱子打开,看一下里面的纸条,如果是"no"就说明, "yes"就说明。由此可以在互不知道对方财产的前提下,比较二人的财富。
当然上述描述的是一种实际的解决方法,下面将用数学过程来描述。
数学过程:
我们假设Alice手里有一对密钥,并把公钥发给Bob。
第一步:Bob选择一个大数,并利用公钥进行加密得到 ,接着计算,并把发送给Alice。第二步:Alice通过可以计算,并对每个计算结果都通过私钥进行解密,即得到,,...
。再将上面10个结果对素数p进行模运算,得到,,...。然后Alice让到都不变,让到都加1,再把这十个数都发送给Bob。(类似于在箱子里写纸条)最后:Bob进行"开箱操作",拿到,如果等于则说明,若不等于则说明。
上述表达如果有误请在留言区指出,欢迎交流。
往期推荐
学术报告|Trustworthy Machine Learning
隐私保护机器学习中,应用MPC进行实验碰到的常见问题与解答
为什么不可以直接在实数上进行秘密分享?隐私计算岗高薪酬冲上热搜!