Secure Multi-Party Computation (MPC)
Table of Contents
1. MPC 简介
2. Basic Primitives and Building Block
从零开始构建一个 MPC 协议比较麻烦,在构建 MPC 时往往借助一些基本原语和现成构建块,下面将介绍它们。
2.1. Secret Sharing
使用 Secret Sharing 技术可以把某个秘密值“分散地”保存到多人手中,多个凑在一起时通过某种运算可恢复出原始秘密值。
2.2. Random Oracle
随机预言机(Random Oracle)对任何的输入都返回一个“均匀随机”的输出,对相同的输入返回相同的输出。 对于两个输入
在密码学中,“预言机”(Oracle Machine)用于表示一个可以实现某功能的黑盒子,如图 2 所示。
Figure 2: Oracle (A Blackbox)
一个系统,如果把里面的哈希函数替换为 Random Oracle 后,可以证明该系统是安全的,则称这个系统在随机预言机模型(Random Oracle Model)下是安全的。 比如,RSA-FDH 在随机预言机模型下是安全的。
不过需要注意的是,一个系统在“随机预言机模型下是安全是”并不是一个很强的安全(因为现实中没有真正的随机预言机),当然它会比没有任何安全证明要好些。
令人悲观的是,没有真正的 Random Oracle:
According to the Church–Turing thesis, no function computable by a finite algorithm can implement a true random oracle (which by definition requires an infinite description because it has infinitely many possible inputs, and its outputs are all independent from each other and need to be individually specified by any description).
2.3. Oblivious Transfer
2.4. Commitment
2.5. Zero-Knowledge Proof
3. 安全定义和敌手模型
3.1. 安全的定义
3.1.1. Perfect Secrecy
1949 年,信息论奠定人 Shannon 在论文 Communication Theory of Secrecy Systems 中对加密系统提出了“Perfect Secrecy”的概念。
Shannon defines perfect secrecy for secret-key systems and shows that they exist. A secret-key cipher obtains perfect secrecy if for all plaintexts x and all ciphertexts y it holds that Pr(x) = Pr(x|y). In other words, a ciphertext y gives no information about the plaintext.
摘自:http://cryptowiki.net/index.php?title=Perfectly-secret_ciphers_and_Shannon%27s_theory
One-time pad 是满足“Perfect Secrecy”的加密方案,但是 One-time pad 要求 key 的长度至少和明文一样长,且 key 仅能使用一次,这使得 One-time pad 不是很实用。
3.1.2. Semantic Security
1984 年,Shafi Goldwasser 和 Silvio Micali 在论文 Probabilistic Encryption 中提出了“Semantic Security”的概念:一个加密系统,如果在多项式时间内,通过密文无法找到明文有价值的信息,则满足 Semantic Security。一般地,明文的长度不属于“有价值”的信息。
3.2. Game-Based Security
在 Game-Based 模型下,首先定义 Game,这个 Game 有两个角色:Adversary (or Attacker) 和 Challenger。如果在多项式时间内,Adversary 不能赢得 Game,则我们就说该协议在 Game-Based 模型下是安全的。
对于一个加密系统来说,可以采用下面的方式来定义 Game:
- Challenger 随机选择一个明文
,加密后得到密文 ,把密文发送给 Adversary; - Adversary 收到密文
后,发送一个消息 给 Challenger; - Challenger 如果发现
,则认为 Adversary 赢得了 Game。
对于 IND-CPA,其 Game 的定义如下:
- The challenger C generates a private key PK and a secret key SK and gives PK to an adversary A.
- A may perform any number of encryptions or other operations.
- A submits two distinct chosen plaintexts
, to C. - C flips a fair binary coin
and encrypts with the public key. - A performs arbitrary operations and gives back a guess of
.
如果 Adversary A 赢得 Game(即猜对
根据 Adversary 的不同攻击能力,可以有下面这些方案:
- IND-CPA (INDistinguishability under Chosen Plaintext Attack) ,也就是说 “攻击者可以获得他选择的明文所对应的密文”。在公钥场景中,这个攻击一般是不可避免场景。 如果一个系统具备 IND-CPA 属性,则这个系统同时具备语义安全(Semantic Security)属性。
- IND-CCA1 (INDistinguishability under Chosen Ciphertext Attack),选择密文攻击(也称为“非适应性选择密文攻击”)。假设存在“解密机”,攻击者可以向解密机询问某个(某一些)密文所对应的明文。但有个限制:得到解密结果后,不能再使用解密机。也被称为“午餐攻击”。
- IND-CCA2 (INDistinguishability under adaptive Chosen Ciphertext Attack),“适应性选择密文攻击”。和上面的“非适应性选择密文攻击”类似,不过攻击者功能更强,攻击者可以在得到解密机返回的结果后,接着使用解密机。
目前,满足 IND-CCA2 的协议才被认为是安全的。
参考:
https://en.wikipedia.org/wiki/Ciphertext_indistinguishability
http://mahdiz.com/crypto/basics/page-14.htm
3.3. Simulation-Based Security (Real-Ideal Simulation Paradigm)
Simulation-Based Security 的思想如下:
The Real World/Ideal World Paradigm states two worlds: (i) In the ideal-world model, there exists an incorruptible trusted party to whom each protocol participant sends its input. This trusted party computes the function on its own and sends back the appropriate output to each party. (ii) In contrast, in the real-world model, there is no trusted party and all the parties can do is to exchange messages with each other. A protocol is said to be secure if one can learn no more about each party's private inputs in the real world than one could learn in the ideal world. In the ideal world, no messages are exchanged between parties, so real-world exchanged messages cannot reveal any secret information.
参考:https://en.wikipedia.org/wiki/Secure_multi-party_computation#Security_definitions
Real-Ideal Simulation Paradigm 思想起源于 Shafi Goldwasser 和 Silvio Micali 在 1984 发表的论文 Probabilistic Encryption,该论文第一次采用这种方式来定义和证明安全,不过并没有采用 Real-Ideal 这种术语。
3.4. 敌手模型
3.4.1. Semi-Honest (Passive) Adversaries
半诚实模型是指:各个参与者会按照协议的要求参与计算,但是参与者可能保留交互时得到的信息。 对于想要协作完成计算并得到正确结果的参与方来说,该模型符合实际的情况。半诚实模型的敌手行为是“被动”的,它只是收集交互信息,这些信息可能用于分析以试图从中得到一些私有信息。
Semi-Honest Security 形式化的定义如图 3 所示。
Figure 3: Definition of Semi-Honest Security
3.4.2. Malicious (Active) Adversaries
恶意敌手可以进行任何的操作(具备更“主动”的行为),包含但不限于:用任意非法值进行输入,在任意时间终止执行协议等。如果协议可以抵抗恶意敌手,则说它具备 Malicious Security 安全。 显然,具备 Malicious Security 的协议要比具备 Semi-Honest Security 的协议要更安全。
Malicious Security 具备较高的安全性:
The only thing that an adversary can do in the case of dishonest majority is to cause the honest parties to “abort” having detected cheating. If the honest parties do obtain output, then they are guaranteed that it is correct. Their privacy is always preserved.
摘自:https://en.wikipedia.org/wiki/Secure_multi-party_computation#Security_definitions
Malicious Security 形式化的定义如图 4 所示。
Figure 4: Definition of Malicious Security
3.4.3. Covert Adversaries
隐蔽敌手模型(Covert Adversaries)。在这种模型下,攻击者担心恶意行为被协议检测出来而受惩罚,攻击者把它的恶意行为混淆在正常行为中,只能以一定的概率被检测到。
4. Semi-Honest MPC
表 1(摘自 A Pragmatic Introduction to Secure Multi-Party Computation 第 3 章 Fundamental MPC Protocols)是一些在半诚实模型下安全的协议。
Protocol | Parties | Rounds | Circuit |
---|---|---|---|
Yao's Garbled Circuit | 2 | constant | Boolean |
GMW | many | circuit depth | Boolean or arithmetic |
BGW | many | circuit depth | Boolean or arithmetic |
BMR | many | constant | Boolean |
GESS | 2 | constant | Boolean formula |
5. Malicious MPC
表 2(摘自 A Pragmatic Introduction to Secure Multi-Party Computation 第 6 章 Malicious Security)是一些在恶意敌手模型下安全的协议。
Protocol | Parties | Rounds | Based on |
---|---|---|---|
Cut-and-Choose | 2 | constant | Yao's GC |
GMW Compiler | many | (inherited) | any semi-honest |
BDOZ & SPDZ | many | circuit depth | preprocessing |
Authenticated Garbling | many | constant | BMR |
6. Majority Assumption
在 MPC 协议中,经常看到下面两个概念:
- Honest Majority,是指诚实参与者占大多数的情况下,隐私数据不会被泄露。Honest Majority 的言外之意是:诚实参与者如果只占少数,隐私数据可能被泄露。
- Dishonest Majority,是指恶意参与者占大多数情况下,隐私数据也不会被泄露。当然,这时协议往往会中止。
显然, Dishonest Majority 协议会比 Honest Majority 协议具有更高的安全性。
需要说明的是,协议需要保护的是诚实参与者的隐私数据,或者整体的隐私数据,而恶意参与者的隐私数据并不是关注重点。比如“恶意参与者 1”的隐私数据让“恶意参与者 2”知道了,这个并不算“隐私数据被泄露”。