simulation

How To Simulate It – A Tutorial on the Simulation Proof Technique

本文将介绍如何通过模拟的思想去证明一个密码学系统的安全性。

文档原文：https://eprint.iacr.org/2016/046.pdf

Introduction

首先，我们需要理解什么是模拟–simulation。

原文是这样描述的：

Simulation is a way of comparing what happens in the “real world” to what happens in an “ideal world” where the primitive in question is secure by definition. 

也就是说，模拟是一种比较方式，将ideal world和real world进行比较。

所谓的理想世界 (ideal world) 是一个理论模型，用于描述一个安全协议在理想条件下的行为。在这个模型中，存在一个被称为理想函数的抽象实体，它能够完美地执行协议应有的功能，而不会泄露任何额外的信息。同时，还有一个模拟器 (simulator)，它尝试模拟真实世界中敌手可能观察到的行为，但又不会使用任何真实的秘密信息。

**现实世界（real world）**就是指我们设计和实施密码学协议的环境。现实世界中，协议需要与潜在的攻击者（Adversary）进行交互。

这两个概念出现在UC（Universally Composable）安全框架中。在UC框架中，如果现实世界的协议能够被证明与理想世界中的理想功能等效，那么我们就可以说该协议是安全的。这意味着，即使在面对现实世界中的攻击者时，协议也能保持与理想功能相同的安全性。

在理想世界中，既然对手什么也学不到，这就意味着在现实世界中，当对手收到密文时，也什么也学不到。

原文提到了模拟器必须做的三个任务：

1.	It must generate a view for the real adversary that is indistinguishable from its real view;
2.	It must extract the effective inputs used by the adversary in the execution; and
3.	It must make the view generated be consistent with the output that is based on this input.

我们逐个分析一下：

1. 它必须为真实对手生成一个与其真实视图无法区分的视图。

这里的“对手的视图”指的是对手通过分析交互过程中获得的信息所构建的关于系统状态的认知。简而言之，就是对手能够观察到的所有信息的集合。

2. 它必须提取对手在执行过程中使用的有效输入。

有效输入是指对手为了达到其目的而输入到系统中的数据，这些数据可能会影响系统的行为或输出。

3. 必须使生成的视图与基于该输入的输出保持一致。

这意味着模拟器生成的对手视图必须与对手在真实世界中根据其输入所期望的输出相匹配。

Preliminaries and Notation

$S\subseteq \{0,1\}^*$：有限集合 $S$，表示集合S是由0和1组成的所有可能字符串的子集。如果我们有一个集合S，它包含的元素是由0和1组成的字符串，那么这个集合S就可以被认为是$\{0,1\}^*$的子集。这里的“有限集合”意味着集合中的元素数量是可数的，也就是说，我们可以数出集合中有多少个元素。

举几个例子：

• S = {0, 1}：这个集合包含两个元素，分别是字符串"0"和"1"。
• S = {00, 01, 10, 11}：这个集合包含所有长度为2的由0和1组成的字符串。
• S = {ε, 0, 01, 110, 1110}：这个集合包含空字符串ε（表示没有任何字符），以及其他几个由0和1组成的字符串。

$x\in_R S$：表示 x 在集合 S 上均匀分布。

具体来说，对于 {0,1}ⁿ，这个集合包含了所有可能的长度为 n 的二进制字符串。如果我们从这个集合中随机选择一个字符串，每个字符串被选中的概率都是 1/2ⁿ，因为总共有 2ⁿ 个可能的字符串。

例如，如果 n=2，那么集合 {0,1}² 包含以下四个字符串：00、01、10 和 11。在均匀分布 U₂ 下，选择这四个字符串中的任何一个的概率都是相同的，即 1/4。

再比如，如果 n=3，那么集合 {0,1}³ 就包含以下八个字符串：000、001、010、011、100、101、110 和 111。在均匀分布 U₃ 下，选择这八个字符串中的任何一个的概率都是相同的，即 1/8。

$\mu(\cdot)$：一个表示概率上可忽略函数

$p(\cdot)$：正多项式

$\lambda$：空字符串

计算不可区分性（Computational Indistinguishability）：

概率集合$X={X(a,n)}_{a\in\{0,1\};n\in N}$是以$a\in\{0,1\}^*$和$n\in N$为索引的随机变量的无限序列。$a$代表各方的输入，$n$代表安全参数。

有点抽象，举两个例子：

假设我们有一个概率实验，它可以产生一个二进制字符串，比如抛硬币序列。对于每个二进制字符串

$a$

和每个自然数

$n$

，我们定义一个随机变量

$X(a,n)$

它可能代表在这个实验中得到字符串

$a$

的概率，或者在

$n$

次实验中得到字符串

$a$

的次数。

例如，如果我们抛一枚硬币两次，可能得到的二进制字符串有

$00,01,10,11$

对于每个字符串和每个自然数

$n$

我们可以定义一个随机变量来表示在

$n$

次实验中得到该字符串的次数。所以，如果我们把

$n$

设为2，那么

$X(00,2)$

可能表示在两次实验中都得到正面的次数，

$X(01,2)$

表示得到一次正面一次反面的次数，以此类推。

让我们考虑一个与天气相关的概率集合的例子。

假设我们有一个随机变量 $X(a,n)$，其中$a$是一个描述特定天气状况的字符串（例如 “晴天”、“雨天”、“多云” 等），而$n$是一个自然数，表示我们观察这种天气状况的天数。例如，如果我们关注的是 “晴天”，那么$a$就是 “晴天”，而$n$可以是任何自然数，比如 30。那么$X('Sunny',30)$就代表在观察的 30 天内，出现 “晴天” 的天数。这个概率集合$X$就包含了所有这些随机变量的无限序列，每个序列都与一个特定的天气状况和观察天数索引相关联。

假设有两个这样的概率集合：

$X={X(a,n)}_{a\in\{0,1\};n\in N}$

$Y={Y(a,n)}_{a\in\{0,1\};n\in N}$

如果对于每一个非统一多项式时间算法$D$，存在一个可忽略的函数$\mu(\cdot)$，使得对于每一个$a∈\{0,1\}^*$和每一个$n∈N$，都可以说$X\stackrel{c}{\equiv}Y$在计算上是无差别的，用$X\stackrel{c}{\equiv}Y$表示：

$|Pr[D(X(a,n))=1]-Pr[D(Y(a,n))=1] \le \mu(n)|$

原文中强调了：

All parties are assumed to run in time that is polynomial in the security parameter.

这段话强调了在设计密码学算法时，需要考虑算法的效率和安全性，确保算法在可接受的时间内运行，同时保持足够的安全性。

非均匀性（Non-uniformity）：

如果对于每一个非均匀多项式时间算法$D$和每一个多项式$p(\cdot)$都存在一个$\N\in N$，使得对于每一个$n > N$ 和每一个$a\in\{0,1\}^*$都存在一个$\N\in N$，那么$X\stackrel{c}{\equiv}Y$

$|Pr[D(X(a,n))=1]-Pr[D(Y(a,n))=1]|<\frac{1}{p(n)}$

在计算机科学和密码学中，非均匀性（non-uniformity）指的是算法或计算模型可以访问与输入大小相关的额外信息或建议。这些额外信息通常以“建议字符串”（advice strings）的形式存在，它们不是由算法本身生成的，而是由外部提供。

非均匀性意味着即使是非均匀的多项式时间算法（也就是可以访问建议字符串的算法），也不能有效地区分两个分布集合。

这是一种更加强大条件的计算不可区分性。

此外，原文还给出了另一个极端条件下的式子：

存在一个$D$和一个多项式$p(\cdot)$，对于无限多个$n$，存在一个$a\in \{0,1\}^∗$ ，其中

$|Pr[D(X(a,n))=1]-Pr[D(Y(a,n))=1]|\ge \frac{1}{p(n)}$

这两个定义看似矛盾，实际上描述了两种极端情况。第一个定义描述了当两个分布是计算不可区分的时候的情况，即没有算法能够有效地区分它们。第二个定义描述了当两个分布是可区分的时候的情况，即存在至少一个算法能够有效地区分它们。这两个定义之间的矛盾表明，计算不可区分性是一个非常强的属性，它要求对于几乎所有的输入大小和建议字符串，都没有算法能够区分两个分布。

非均匀性算法的例子：

一个典型的例子是在密码学中的非一致性敌手模型（non-uniform adversary model）。在这个模型中，敌手（即攻击者）可以利用一些额外的信息来增强其攻击能力。这些额外的信息可能是之前的攻击经验、特定的密码学结构的弱点，或者是通过某些方式预先计算出的有用信息。

例如，考虑一个简单的加密方案，其中使用了一个伪随机函数（PRF）来生成密钥。在一个均匀的敌手模型中，敌手只能使用多项式时间的算法来尝试破解密钥。然而，在一个非一致性敌手模型中，敌手可能拥有一个与输入大小相关的建议字符串，这个字符串可能包含了一些关于伪随机函数内部结构的信息，从而使得敌手能够更有效地破解密钥。

另一个例子是彩虹表攻击（rainbow table attack）。彩虹表是一种预先计算出的数据结构，它可以用来逆向工程哈希函数的输出。在一个非一致性敌手模型中，敌手可以使用彩虹表作为建议字符串，这样他们就可以快速地找到哈希函数的输入，即使哈希函数设计为均匀的算法也无法防止这种攻击。

虽然非均匀性定义了一个更强大的安全模型，但在实际应用中，密码学算法和协议一般都是均匀性的，以确保它们在广泛的环境和条件下都能安全有效地工作。

最后一段话还强调了在定义计算不可区分性时，量词的顺序非常重要。正确的定义要求对于所有的$a$，存在一个统一的可以忽略的函数，而不是对于每个$a$都有一个可能不同的可以忽略的函数。这保证了计算不可区分性的定义在密码学中的实用性和强度。

The Basic Paradigm – Semantic Security

Nothing is learned about the plaintext from the ciphertext.

这句话很难形式化，但也是接下来的工作。

首先，语义安全的定义允许明文的长度取决于安全参数，并允许明文的任意分布，此外，还允许信息的辅助函数$h$存在。

对手的目的是从密文和所提供的辅助信息中学习明文的某个函数$f$。

根据该定义，仅从辅助信息（以及明文的长度）而不从密文中学习相同的信息应该是可能的。

一个私钥加密方案$(G,E,D)$的安全性， 如果对于每个非统一概率多项式时间算法$\mathcal{A}$，存在一个非统一概率多项式时间算法$\mathcal{A}^\prime$，使得对于每个概率集合$\{X_n\}_{n\in N}$，$|Xn| ≤ poly(n)$，每一对多项式有界函数$f,h ： \{0,1\}*→\{0,1\}^∗$，每个正多项式$p(\cdot)$和所有足够大的$n$：

$\underset{k\leftarrow G(1^n)}{Pr}[\mathcal{A}(1^n,E_k(X_n),1^{|X_n|},h(1^n,X_n))=f(1^n,X_n)]\lt Pr [\mathcal{A}(1^n,1^{|X_n|},h(1^n,X_n))=f(1^n,X_n)] + \frac{1}{p_n}$

这一段话其实阐明了一个道理：$\mathcal{A}$（在给定密文的情况下）可以知道的任何信息都可以被$\mathcal{A}^\prime$（在不给定密文的情况下）知道。

从模拟的角度来说，$\mathcal{A}^\prime$就是处在一个理想的世界，因为它所学到的任何东西都只来自辅助信息和明文长度，但是根据定义，我们知道$\mathcal{A}^\prime$和$\mathcal{A}$能学习的东西一样多。

这里提供了一个基于模拟器的证明过程：

$Simulator\ \mathcal{A}^\prime$：输入$1^n,1^{|X_n|},h=h(1^n,X_n)$，算法$\mathcal{A}^\prime$如下运行：

1. $\mathcal{A}^\prime$运行$G(1^n)$得到密钥$k$
2. $\mathcal{A}^\prime$计算$c=E_k(0^{|X_n|})$作为加密垃圾
3. $\mathcal{A}^\prime$运行$\mathcal{A}(1^n,c,1^{|X_n|},h)$并且输出$\mathcal{A}$输出的。

在这个模拟证明中，“垃圾”加密的定义是指一个看起来像有效加密的数据，但实际上是无意义的。这种加密的目的是测试算法 ($\mathcal{A}$) 是否能够区分真正的加密和无意义的加密。如果 ($\mathcal{A}$) 不能区分这两者，那么我们可以说加密算法是安全的，因为即使攻击者得到了加密数据，他们也无法确定它是否包含有用的信息。

Secure Computation – Simulation for Semi-Honest Adversaries

Background

在密码学中，半诚实的敌手（也称为被动敌手或静态敌手）是指在两方计算中，控制一方的攻击者。这种敌手遵循协议的规定执行所有步骤，但会尝试通过分析它接收到的消息记录和内部状态来获取更多信息。这是一个相对较弱的敌手模型，因为它不会主动破坏协议，只是被动地收集信息。

半诚实的敌手模型的特点包括：

• 静态：敌手在计算开始时就确定，并且在整个计算过程中控制同一方。
• 遵循协议：敌手精确地按照协议规定的步骤执行，不会做出任何违反规定的行为。
• 信息收集：敌手的目标是通过观察通信过程中的消息来学习额外的信息，而不是直接破坏协议。

尽管这是一个弱敌手模型，但如果协议能在半诚实敌手的存在下保证安全，那么它至少可以保证没有无意的信息泄露。这种安全性对于那些基本信任对方但又想确保自己的输入不会被记录的场景是足够的。此外，为半诚实敌手设计的安全协议通常是构建更强安全性协议的第一步。

Defining Security for Semi-Honest Adversaries

两方计算

两方计算允许两个参与方（通常称为Alice和Bob）协作计算某个函数，而无需泄露各自的输入信息。

原文这样定义了两方计算：

$f:\{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^* \times \{0,1\}^*, where\ f = (f_1, f_2), x,y \in \{0,1\}^n$

其中一方输入$x$，输出$f_1(x,y)$

另一方输入$y$，输出$f_2(x,y)$

隐私通过模拟（Privacy by Simulation）

如果参与协议的一方可以计算的任何内容都只能根据协议的输入和输出来计算，那么该协议就是安全的。

在这个定义中，模拟器将会被给予参与方一方的输入与输出（之所以是输入与输出，而不仅仅是输入，是因为，我们想要证明的是即使在协议执行过程中，参与方也无法学到任何超出其输入和预定输出之外的信息。为了做到这一点，模拟器需要重现参与方在协议执行中的视图，这包括了它们的输入和它们从协议中获得的输出。）

值得注意的是，参与计算的双方都是半诚实的。在半诚实模型中，因为参与方遵循协议并使用他们的真实输入，所以输出 ( $f(x,y)$ ) 是可以预先定义的。这意味着模拟器可以被给予 ( $f(x,y)$ ) 这个值来生成参与方的视图，而不需要考虑对手可能的行为。

与此相反的是，恶意敌手（malicious adversaries）。半诚实参与方和恶意敌手的主要区别在于他们对协议的遵守程度。半诚实参与方会遵循协议规则，使用真实的输入，这使得输出是可预测和明确定义的。而恶意敌手可能会违反规则，使用不同的输入，这使得输出不再是固定的，而是取决于敌手的选择。

Definition of security

• 函数$f=(f_1,f_2)$，双方协议$\pi$
• $view_i^\pi(x,y,n)$表示第$i$方执行协议$\pi$的视图，参数为(x,y,n)，其等同于$(w,r^i;m_1^i,...,m_t^i)$，$w\in\{x,y\}$，$r^i$代表第$i$方的磁带，$m_j^i$代表其收到的第$j$条消息
• 第$i$方的输出表示为$output_i^\pi(x,y,n)$，两方的联合输出表示为$output^\pi(x,y,n)=(output_1^\pi(x,y,n),output_2^\pi(x,y,n))$

Definition 4.1: $f=(f_1,f_2)$，如果存在概率多项式时间算法$S_1$和$S_2$，我们说协议$\pi$能够安全计算$f$，即使在静态半诚实敌手的情况下：

$\{(S_1(1^n,x,f_1(x,y)),f(x,y))\}_{x,y,n}\stackrel{c}{\equiv} \{(view_1^\pi(x,y,n),output^\pi(x,y,n))\}_{x,y,n}\\ \{(S_2(1^n,y,f_2(x,y)),f(x,y))\}_{x,y,n}\stackrel{c}{\equiv} \{(view_2^\pi(x,y,n),output^\pi(x,y,n))\}_{x,y,n}$

其中$x,y\in\{0,1\}^*,|x|=|y|,n\in N$

模拟器的输出和功能输出$f(x,y) = (f_1(x,y),f_2(x,y))$的联合分布必须与$(view_i^\pi(x,y,n),output^\pi(x,y,n))$不可区分

现在，我们来考虑一个更简单的安全定义，它只将模拟器生成的分布与对手的观点（而不是联合分布）进行比较：

$\{(S_1(1^n,x,f_1(x,y))\}_{x,y,n}\stackrel{c}{\equiv} \{(view_1^\pi(x,y,n)\}_{x,y,n}\\ \{(S_2(1^n,x,f_2(x,y))\}_{x,y,n}\stackrel{c}{\equiv} \{(view_2^\pi(x,y,n)\}_{x,y,n}\\$

根据这一定义，上述安全计算双方相同输出的协议是安全的。这是因为每一方的视图都是由$x\bigcup y$的随机样本组成的，而这个视图是可以模拟的。

A simpler formulation for deterministic functionalities：

该定义有两个要求：(a) 正确性，即各方的输出都是正确的；

(b) 私密性，即各方的观点都可以（单独）模拟。

从形式上看，正确性要求存在一个可忽略的函数$\mu$，使得对于每个$x,y\in \{0,1\}^*$和每个$n$，

$Pr[output^\pi(x,y,n)\ne f(x,y)]\le \mu(n)$

隐私性要求，存在概率多项式时间算法$S_1,S_2$

$\{(S_1(1^n,x,f_1(x,y))\}_{x,y\in\{0,1\}^*;n\in N}\stackrel{c}{\equiv} \{(view_1^\pi(x,y,n)\}_{x,y\in\{0,1\}^*;n\in N}\\ \{(S_2(1^n,x,f_2(x,y))\}_{x,y\in\{0,1\}^*;n\in N}\stackrel{c}{\equiv} \{(view_2^\pi(x,y,n)\}_{x,y\in\{0,1\}^*;n\in N}\\$

区分者为了得到集合的索引$x,y$，可以自己计算$f(x,y)$，从而有

$\{(S_1(1^n,x,f_1(x,y))\}_{x,y\in\{0,1\}^*;n\in N}\stackrel{c}{\equiv} \{(view_1^\pi(x,y,n)\}_{x,y\in\{0,1\}^*;n\in N}\\ \{(S_1(1^n,x,f_1(x,y)),f(x,y))\}_{x,y\in\{0,1\}^*;n\in N}\stackrel{c}{\equiv} \{(view_1^\pi(x,y,n),f(x,y))\}_{x,y\in\{0,1\}^*;n\in N}\\$

正确性要求保证输出$output^\pi(x,y,n)$与$f(x,y)$在计算上无差别，这意味着

$\{(view_1^\pi(x,y,n),f(x,y))\}_{x,y\in\{0,1\}^*;n\in N}\stackrel{c}{\equiv} \{(view_1^\pi(x,y,n),output^\pi(x,y,n\}_{x,y\in\{0,1\}^*;n\in N}\\$

因此，我们有：

$\{(S_1(1^n,x,f_1(x,y)),f(x,y))\}_{x,y\in\{0,1\}^*;n\in N} \stackrel{c}{\equiv} \{(view_1^\pi(x,y,n),output^\pi(x,y,n\}_{x,y\in\{0,1\}^*;n\in N}\\$

Triviality for semi-honest adversaries

我们注意到，在半诚信对手的情况下，许多问题都变得微不足道。例如，零知识，“承诺”，抛掷硬币问题

Auxiliary information

辅助输入在定义中是隐含的，因为针对非均匀对手的计算不可区分性是必需的，运行协议的对手无需提供任何辅助信息，因为它是半诚实的，因此无论有无辅助输入，都会遵循完全相同的指令。

Oblivious Transfer for Semi-Honest Adversaries

不经意传输（OT, oblivious transfer）

$f((b_0,b_1),\sigma)=(\lambda,b_{\sigma}),where\ b_0,b_1,\sigma\in\{0,1\}$

P1：$(b_0,b_1)$，没有任何输出

P2：$\sigma$

抽象地讲，就是A给B发消息，A却不知道B收到的是啥，一般的思路就是A要多发一些消息然后让B去选择有需要的，如果是这样的话，同时还应该保证B不会多知道他本不应该知道的消息。

增强型陷门排列（enhanced trapdoor permutations）：一种特殊的双射函数，随机取样的函数很难在随机取样值上反转，然而存在一个陷门，可以在给定情况下有效反转。

陷门排列集合是$\{f_\alpha\}_\alpha$的集合，包括四个概率多项式函数$I,S,F,F^{-1}$

$I(1^n)$：随机选取n比特下标为$\alpha$的排列$f_\alpha$

$S(\alpha)$：随机采样$S(\alpha;r)$

$F(\alpha,x)=f_\alpha(x)$

$F^{-1}(\tau,y)=f_\alpha^{-1}(y)$

加强陷门排列：

$Pr[\mathcal{A}(1^n,\alpha,r)=f_\alpha^{-1}(S(\alpha;r))]\le \mu(n)$

敌手$\mathcal{A}$将拥有$\alpha,r$，可以计算$y=S(\alpha;r)$，其主要目的是反转$y$

硬核谓词$B$

$Pr[\mathcal{A}(1^n,\alpha,r)=B(\alpha,f_\alpha^{-1}(S(\alpha;r)))]\le \frac{1}{2}+\mu(n)$

前一个公式表示敌手逆转的可能微乎其微，后一个公式表示敌手逆转后，判断自己的结果是否正确与猜测（$\frac{1}{2}$）无异

不经意传输的步骤：

Inputs:$P_1:b_0,b_1\in\{0,1\};P_2:\sigma \in\{0,1\},(I,S,F,F^{-1})$

Protocol:

1. $P_1$运行$I(1^n)$得到$(\alpha,\tau)$，把$\alpha$发送给$P_2$
2. $P_2$运行$S(\alpha)$两次，得到$x_\sigma,y_{1-\sigma}$，计算$y_\sigma=F(\alpha,x_\sigma)=f_{\alpha}(x_\sigma)$，发送$y_0,y_1$给$P_1$
3. $P_1$计算$x_0=F^{-1}(\alpha,y_0)=f_{\alpha}^{-1}(y_0),x_1=F^{-1}(\alpha,y_1)=f_\alpha^{-1}(y_1)$

计算掩码$\beta_0=B(\alpha,x_0)\oplus b_0,\beta_1=B(\alpha,x_1)\oplus b_1$

$P_1$发送$(\beta_0,\beta_1)$给$P_2$

4. $P_2$计算$b_\sigma=B(\alpha,x_\sigma)\oplus\beta_\sigma$

Theorem

Assume that $(I,S,F,F^{-1})$ constitutes a family of enhanced trapdoor permutations with a hard-core predicate $B$. Then, Protocol securely computes the functionality $f((b_0,b_1),σ) = (λ,b_σ)$ in the presence of static semi-honest adversaries.

Proof

模拟器：$S_1,S_2$

首先考虑 P1 被破坏的情况。

$P_1$没有输出，因此我们只需要证明模拟器可以生成$P_1$收到的传入信息的视图。协议中，$P_1$输入$(y_0,y_1)$，$S_1$输入$(b_0,b_1,1^n)$并按照以下步骤工作：

1. $S_1$为$P_1$选择一个均匀分布的随机磁带$r$（比特序列）
2. $S_1$运行$(\alpha,\tau)\leftarrow I(1^n;r)$
3. $S_1$运行$S(\alpha)$两次，采样值分别为$y_0,_1$
4. $S_1$输出$((b_0,b_1),r;(y_0,y_1))$

由于$S_1$不知道$P_2$的输入$\sigma$，因此无法像诚实的$P_2$那样对$y_0,y_1$进行采样。尽管如此，根据陷阱门排列集合的定义，$S(\alpha)$输出的值几乎均匀分布在$f(\alpha)$的域（域等于范围，因为它是排列）中。根据定义，$F(α,S(α))$ 的分布在统计上接近于 $S(α)$ 的分布。这意味着：

${(F(\alpha,x_0),y_1)}\stackrel{c}{\equiv}{(y_0,y_1)}\stackrel{c}{\equiv}{(y_0,F(\alpha,x_1))}$

其中 $a \in I$，$x_0,x_1,y_0,y_1$都是$S(\alpha)$的采样

当$P_2$的输入为$\sigma = 0$时，$P_1$看到的正是一对$(F(\alpha,x_0),y_1)$

$(y_0,y_1)$是模拟器生成的视图

当$P_2$的输入为$\sigma = 1$时，$P_1$看到的正是一对$(y_0,F(\alpha,x_1))$

因此，对于每一个$\sigma \in \{0,1\}$

$\{S_1(1^n,(b_0,b_1))\}\stackrel{c}{\equiv}\{view_1^\pi((b_0,b_1),\sigma)\}$

接下来，我们讨论$P_2$被破坏的情况。

我们需要构建一个视图，使该视图定义的输出等同于协议的真实输出。$S_2$接收$P_2$的输入和输出，因此能够实现上述功能。在本协议中，实现这一点的方法是让 S2 设置$\beta_\sigma=B(\alpha,x_\sigma)\oplus b_\sigma$，就像真正的$P_1$一样。相比之下，$S_2$无法正确计算 $\beta_{1-\sigma}$

$S_2$的输入包括$1^n$和$P_2$的输入和输出$(\sigma,b_\sigma)$

1. 为保证随机性，$S_2$ 运行$S(\alpha)$两次
2. $S_2$运行$I(1^n)$得到$(\alpha,\tau)$
3. $S_2$计算$s_\sigma=S(\alpha;r_\sigma),y_{1-\sigma}=S(\alpha;r_{1-\sigma}),x_{1-\sigma}=F^{-1}(\tau,y_{1-\sigma})$
4. $S_2$计算$\beta_\sigma=B(\alpha,x_\sigma)\oplus b_\sigma$，其中$b_\sigma$来自于$P_2$的输出
5. $S_2$计算$\beta_{1-\sigma}=B(\alpha,x_{1-\sigma})$
6. $S_2$输出$(\sigma,r_0,r_1;\alpha,(\beta_0,\beta_1))$

如果把$\sigma$放在第一位，那么$P_2$的视图可以写作：

$view_2^\pi((b_0,b_1),\sigma)= (\sigma,r_0,r_1;\alpha,(B(\alpha,x_{1-\sigma})\oplus b_{1-\sigma}))$

模拟器的输出会被写作：

$S_2(1^n,\sigma,b_{\sigma})=(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})))$

当$b_{1-\sigma}=0$时，对于每一个$\sigma,b_\sigma \in\{0,1\}$和每一个$n$：

$S_2(1^n,\sigma,b_{\sigma}) \equiv \{view_2^\pi((b_0,b_1),\sigma)\}$

因此，我么们只需要证明在$b_{1-\sigma}=1$的情况下，$view$是不可区分的，二者的唯一区别在于$\beta_{1-\sigma}=B(\alpha,x_{1-\sigma})$, or $\beta_{1-\sigma}=B(\alpha,x_{1-\sigma})\oplus 1$，因此，我们需要证明$\sigma, b_\sigma\in\{0,1\}$：

$\{(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})))\} \stackrel{c}{\equiv} \\ \{(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})\oplus 1))\}$

这个式子的左边是$S_2$生成的分布，式子的右边是$b_{1-\sigma}$所处的真实世界。

假设存在一个非统一概率多项式时间区分器$D$、一个多项式$p(\cdot)$和一个无穷序列的元组$(\sigma,b_\sigma,n)$，使得

$Pr[D(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})))=1]\\ -Pr[D(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})\oplus 1))=1]\\ \ge \frac{1}{p(n)}$

在不失一般性的前提下，我们假设对于无穷多个$n$，$D$在接收到$B(\alpha,x_1-\sigma)$时输出 1 的概率大于或等于接收到$B(\alpha,x_1-\sigma)\oplus 1$时输出 1 的概率

我们构建一个算法$\mathcal{A}$

$\mathcal{A}$的输入包括$\sigma,b_\sigma,(1^n,\alpha,r)$，其目标是猜出$B(\alpha,f_\alpha^{-1}(S(\alpha;r)))$

首先通过设置$r_{1-\alpha}=r$，计算出$x_{1-\alpha}=f_\alpha^{-1}(S(\alpha;r))$

接下来$\mathcal{A}$选取一个随机值$r_\sigma$并且计算$x_\sigma=S(\alpha;r_\sigma),\beta_\sigma=B(\alpha,x_\sigma)\oplus b_\sigma$

最后$\mathcal{A}$选取随机值$\beta_{1-\sigma}$，输入$(\sigma,r_0,r_1;\alpha,(\beta_\sigma,\beta_{1-\sigma}))$进算法$D$中，并且输出$\beta_{1-\sigma}$如果$D$输出1，否则输出$1-\beta_{1-\sigma}$

观察到，如果$\mathcal{A}$正确地猜出$\beta_{1-\sigma}$，那么就会在$D$上输入$(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})))$，否则会在$D$上输入$(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})\oplus 1))$

因此，如果$\mathcal{D}$输出1，可以认为$\mathcal{A}$猜对了$\beta_{1-\sigma}$

设置$x=x_{1-\sigma}$，我们有：

$Pr[\mathcal{A}(1^n,\alpha,r)=B(\alpha,x)] \\ =\frac{1}{2}\cdot Pr[\mathcal{A}(1^n,\alpha,r)=B(\alpha,x) | \beta_{1-\sigma}=B(\alpha,x)]\\ + \frac{1}{2}\cdot Pr[\mathcal{A}(1^n,\alpha,r)=B(\alpha,x) | \beta_{1-\sigma}\ne B(\alpha,x)]\\ =\frac{1}{2}\cdot Pr[D(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})))=1]\\ + \frac{1}{2}\cdot Pr[D(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})\oplus 1))=0] \\ = \frac{1}{2}\cdot Pr[D(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})))=1] \\ + \frac{1}{2}\cdot (1-Pr[D(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})\oplus 1))=1])\\ =\frac{1}{2} + \frac{1}{2}\cdot Pr[D(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})))=1]\\ -\frac{1}{2}\cdot Pr[D(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})\oplus 1))=1]\\ \ge \frac{1}{2} + \frac{1}{2p(n)}$

因此，可以说$S_2$的输出与$P_2$在实际执行中的视图在计算上是无差别的。

Discussion这个协议是一个很好的例子，说明了在半诚实对手存在的情况下，如果被破坏的一方行为不完全诚实，那么安全性就得不到任何保证。如果$P_2$通过选择$x_0,x_1$并计算$y_0 = F(\alpha,x_0), y_1 = F(\alpha,x_1)$来生成 $y_0,y_1$，那么它将同时学习到$b0,b1$。$P_1$根本无法检测到这一点。