安全多方计算的起源与基础简介

安全多方计算（secure multiparty computation）是密码学研究的一个重要分支。它可以让多个数据所有者在联合的数据上进行协同计算以提取数据的价值，而不会泄露每个数据所有者的原始数据。伴随着云计算、人工智能、物联网等多种技术的快速发展以及数据隐私安全问题的日益突出，当前不同领域（比如金融、医疗健康、电子商务等）对安全多方计算均有着大量的实际需求，安全多方计算在现实中的作用变得越来越重要。

安全多方计算起源于20世纪80年代由姚期智教授提出的百万富翁问题（millionaire problem）：两个富翁想知道谁拥有更多的财富，但是又不想把各自的财富告诉对方，这在没有一个可信的第三方参与的情况下应该如何进行？概括地说，安全多方计算所要解决的问题是：持有秘密数据的两方或者多方，在缺乏一个可信第三方的情况下，希望共同计算某个函数并得到各自的输出，在整个计算过程中，每个参与者除了自己的数据和应该得到的函数输出（以及该输出推导出的信息）之外，不能获得任何额外的信息。

安全多方计算协议在执行过程中可能会受到来自外部或者内部敌手的攻击，因此，安全多方计算的安全模型中定义了一个可以控制腐化的（corrupted）参与方子集的敌手，以涵盖外部攻击、内部攻击以及各类合谋攻击的场景。在安全多方计算中，常用的敌手行为模型有半诚实行为模型（semihonest model）和恶意行为模型（malicious model）。在半诚实行为模型中，假设敌手会诚实地参与安全多方计算的具体协议，遵照协议的每一步进行，只是想通过从协议执行过程中获取的内容来推测他方的隐私；而在恶意行为模型中，敌手可以不遵循协议，采取任意的行为获取他方的隐私。

安全多方计算的安全性是通过一种理想世界/现实世界的模型来定义的。在该模型中，首先定义了一个存在可信第三方的理想世界。每个参与方将各自的秘密数据通过安全信道提供给可信第三方，由第三方在联合的数据上进行函数的计算。在完成计算后，可信第三方把输出发给各个参与方。与理想世界相对应的是现实世界。现实世界中不存在可信的第三方，各参与方通过直接和对方交互执行协议来实现在联合数据上的函数计算。如果任何现实世界中的攻击都可以在理想世界中被模拟，那么我们说这个多方计算协议是安全的。具体来说，对于现实世界中的任意一个敌手，在理想世界中均存在一个敌手，其在理想世界执行中的输入/输出联合分布与现实世界执行中敌手的输入/输出联合分布计算不可区分。