当前位置:网站首页>在充分保护隐私的前提下,如何知道两位“马爸爸”谁更富有?

在充分保护隐私的前提下,如何知道两位“马爸爸”谁更富有?

2020-12-08 12:28:58 本体Ontology

安全多方计算(Secure Multi-party Computing,(s)MPC), 是由图灵奖获得者姚期智先生通过百万富翁问题引出的一个数据隐私保护方面的重要领域。姚氏百万问题可表述为:Alice 和 Bob 是两个百万富翁,他们想知道谁更富有,但他们都又不想把关于自己财富的任何信息透露给对方。在这样一种情况下,双方都不想透露自己真实信息,比较两个人的财富多少,并给出可信证明。

图片来源于网络

简单地来说,多方计算就是多方参与者协作来共同计算某个函数的过程。而安全两字意味着这些参与者在得到结果的同时,不能得到任何其他信息。稍显形式化地讲,在安全多方计算中,假定个参与者分别拥有秘密,并以此共同计算

在这计算过程中,任意一个参与方唯一获得的是关于结果的某些信息,而对其他用户的秘密输入和结果一无所知。一般情况下,有两种表现形式:

即所有用户都知道计算结果;

即所有用户共享计算结果。

安全多方计算不仅需要保证输出结果的正确性和安全性,即参与方输入数据的隐私性,还要体现公平性。即对于所有参与方来说,要么大家一起得到输出值,要么大家都得不到结果。另外要强调的是,多方计算仅保证整个计算过程不泄露额外信息,而对于计算函数本身的信息泄露却不会保证。

图片来源于网络

假如存在一个可信任的中心,这个问题很好解决。每个用户把秘密值发送给可信中心,由可信中心来执行函数的计算,并把计算结果返回给用户。实际情况中,很难建立一个所有参与者都信任的可信中心,因此多方计算就是考虑在没有这样一个可信中心的情况下,如何达到有这样一个可信中心存在的情况下的效率和安全性。

在本文中,我们以 Damgar 等人提出的 SPDZ 方案为例,简单说明一下安全多方计算协议中的计算过程。在该方案中,计算结果采用的是第二种表示方式,即经多方计算后,每个参与者拥有,满足。要注意地是,该方案在后期经过了很多优化和改进的后续工作,在这里我们仅仅描述原始方案,以说明这类方案中的大致原理。

1.1 安全模型

在早期的大多数安全多方计算方案中,只有攻击者是半诚实的(会根据掌握信息推断其他参与方秘密输入的攻击者)或只有少数恶意攻击者(根据自己利益会破坏协议运行的攻击者)的情况下才能满足一些安全特性。一个更为实际的敌手模型是“dishonest majority”,即恶意敌手模型,大部分参与者不诚实。而方案要达到的安全性,应等同于有信任中心参与的情况。

1.2 电路选择

一般来说,计算电路有布尔电路和算术电路两种。

图片来源于网络

在布尔电路中,所有运算都可以用异或门实现;而在算术电路中,所有运算可以使用加和乘两种运算来实现。有很多多方计算协议构造在布尔电路上,例如姚期智先生的百万富翁问题。而算术电路可以更简单高效地表达整数等运算,因此也有重要的应用价值。在该文中,我们讨论的是基于算术电路模型的多方计算。

下一期我们将主要介绍计算过程,解析如何保证正确计算。


未完待续......

▿点击阅读原文了解更多

本文分享自微信公众号 - 本体研究院(ontologyresearch) ,作者:0x6d78

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间: 2020-11-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

版权声明
本文为[本体Ontology]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/1757874