Secure Multi-Party Computation (MPC)

使用 Secret Sharing 技术可以把某个秘密值“分散地”保存到多人手中，多个凑在一起时通过某种运算可恢复出原始秘密值。

随机预言机（Random Oracle）对任何的输入都返回一个“均匀随机”的输出，对相同的输入返回相同的输出。 对于两个输入 \(x_1\) 和 \(x_2\) ，随机预言机产生两个输出 \(y_1\) 和 \(y_2\) ，除非向随机预言机查询一下，否则别人没有任意办法知道哪个输出对应于哪个输入。 可以把随机预言机当作是一个“非常安全的哈希函数”。

在密码学中，“预言机”（Oracle Machine）用于表示一个可以实现某功能的黑盒子，如图 2 所示。

一个系统，如果把里面的哈希函数替换为 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).

参考：https://en.wikipedia.org/wiki/Oblivious_transfer

参考：https://en.wikipedia.org/wiki/Commitment_scheme

参考：https://en.wikipedia.org/wiki/Zero-knowledge_proof

在 Game-Based 模型下，首先定义 Game，这个 Game 有两个角色：Adversary (or Attacker) 和 Challenger。如果在多项式时间内，Adversary 不能赢得 Game，则我们就说该协议在 Game-Based 模型下是安全的。

对于一个加密系统来说，可以采用下面的方式来定义 Game：

1. Challenger 随机选择一个明文 \(m\) ，加密后得到密文 \(c\) ，把密文发送给 Adversary；
   
2. Adversary 收到密文 \(c\) 后，发送一个消息 \(m'\) 给 Challenger；
   
3. Challenger 如果发现 \(m=m'\) ，则认为 Adversary 赢得了 Game。
   

对于 IND-CPA，其 Game 的定义如下：

1. The challenger C generates a private key PK and a secret key SK and gives PK to an adversary A.
   
2. A may perform any number of encryptions or other operations.
   
3. A submits two distinct chosen plaintexts \(m_0\), \(m_1\) to C.
   
4. C flips a fair binary coin \(b\) and encrypts \(m_b\) with the public key.
   
5. A performs arbitrary operations and gives back a guess of \(b\).
   

如果 Adversary A 赢得 Game（即猜对 \(b\) ）的概率是 \(1/2\) ，则认为加密协议满足 IND-CPA 安全。

根据 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

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 这种术语。