安全多方计算
考虑以下场景：
Alice认为她得了某种遗传疾病，想验证自己的想法。正好她知道 Bob有一个关于疾病的 DNA模型的数据库。如果她把自己的 DNA样品寄给 Bob，那么 Bob可以给出她的 DNA的诊断结果。但是 Alice又不想别人知道，这是她的隐私。所以，她请求 Bob帮忙诊断自己 DNA的方式是不可行的。因为这样 Bob就知道了她的 DNA及相关私人信息。
这个例子有两个典型特点：①有多个实体参与基于各自私密输入的计算；②参与各方都不希望其他方知道自己的输入信息。即在保护输入数据私密性的前提下实现协同计算。
当前，解决上述问题的策略是假设有可信任的服务提供者或是假设存在可信任的第三方。大家把各自的输入秘密地交给这个可信方，由可信方来计算出结果，然后将相应的结果返回给参与计算的各方。但是在目前多变和充满恶意的环境中，这是极具风险的，很难找到这样的可信第三方。因此，可以支持联合计算并保护参与者私密的协议变得日益重要，这就导致了安全多方计算问题的研究。
安全多方计算（Secure Multi-Party Computation，SMC），是解决一组互不信任的参与方之间保护隐私的协同计算问题，SMC要确保输入的独立性，计算的正确性，同时不泄露各输入值给参与计算的其他成员。
现有的许多密码工具都是安全多方计算的基础，SMC的关键技术涉及到秘密分享与可验证秘密分享、门限密码学、零知识证明等多方面的内容，协议中应用的基本密码算法包括各种公钥密码体质，特别是语义安全的同态公钥加密系统。下面对 SMC的几个基本协议及相关的低层密码算法进行概括。
（1）秘密分享与可验证秘密分享
秘密分享（ Secret Share）是一种分发、保存和恢复秘密的方法，是实现安全多方计算的一种重要工具。 (, )tn门限秘密分享是昀常见的秘密分享体制，秘密 s的分片 {,s1 s2,, sn} 存放于 n个成员{,P1 P2,, Pn} 处，至少需要 t个成员才能重构 s，即使有 t1 个成员联合起来也不能得到关于 s的任何信息，而当 t个或者多于 t个分片可用时，就能够唯一、高效地重构 s。
早期的方案中均假设所有参与方是诚实的，即秘密分享者 Pi(1≤i≤n)所提供的秘密分片都是正确的，因此不能够抵抗恶意攻击者的欺骗行为。为此，在秘密分发的过程中，增加验证协议使各成员Pi(1≤i≤n)能够对分发的秘密分片的正确性进行验证（ Verify）实现了可验证秘密分享（Verifiable Secret Sharing）。如果系统中任何成员（包括外部成员）都可以验证秘密分片 si的正确性，则称可公开验证秘密分享。
（2）同态公钥密码体制
在 SMC技术所采用的各种密码算法中，一个重要的密码体制是具有同态性质的公钥密码体制。现有的几类同态加密方案的安全性都是基于数论中的著名计算难解问题，主要包括 r阶剩余假设、素数群中离散对数假设等。
设 S为一公钥密码体制， k为其安全参数。以 X表示消息空间， C表示密文空间， X为 Abel加法群， C为 Abel乘法群，{0,1}k表示位长为 k的随机位串； Ek,Dk分别表示其公开加密函数和解密函数。
定义 5-2语义安全的同态公钥密码体制

在 SMC协议中可以利用同态加密机制实现不解密地对加密后的数据进行“+”和“×”运算，实现安全求和、安全求积。
（3）零知识证明
零知识证明（ Zero Knowledge Proof-ZKP）是密码学中的一个基本方法，目的是使证明者 P向验证者 V证明自己拥有某个秘密，同时 P又不会向 V泄露该秘密的任何其他有用的信息。按证明者和验证者之间是否需要交互作用， ZKP分为交互式和非交互式零知识证明协议，下面给出交互式证明系统的简单定义。
定义 5-3交互式证明系统（Interactive Proof System）



一对交互式系统 (P,V )称为语言 L的一个交互式零知识证明，如果 P和V间通过多P次交互作用， P以很高的概率向V证明“断言 x∈L成立”，并且不泄露任何其他知识给 V。其中， x是 P和V都知道的一个公共输入， L是某种关系 R指定的一种语言。根据零知识证明过程中系统的安全性和攻击者模型的不同，需要进一步研究完备零知识、统计零知识、计算零知识和诚实验证者的零知识（ Honest Verifier Zero-knowledge）等协议，以适应不同领域的 SMC计算的需要。
（4）混合网协议
混合网（ Mixnets/Mix Network）是实现匿名发送的基本密码协议， 1981年 Chaum D首次提出混合网的概念。混合网由服务网的集合构成，原始信息输入混合网，通过多次秘密置换后再输出，隐藏了输出消息与发送方的关系，实现匿名消息发送。表 5-5给出了混合网协议的原理。

经过 Mixnets输出的密文表是输入密文表的随机置换，攻击者无法确定它们的对应关系。加密消息的长度和用户计算量与 Mixnets服务器的个数成正比，当用户很多时，效率极低。对 Chaum D混合网协议效率的改进，也一直是 SMC基础协议研究的热点。