通用协议（四）半诚实模型

ゝ一纸荒年。 2023-06-13 06:12 20阅读 0赞

## The Semi-Honest Model 半诚实模型 ##

半诚实的参与方，遵循了协议的执行，但是却保存了协议的中间计算状态，实际上，半诚实的参与方，只要保存内部的掷硬币过程（产生随机数的过程）和所有从其他参与方接收到的消息就行了。特别是，一个半诚实的参与方会选择随机数和根据预定的程序进行操作，即根据预定的程序公平的产生随机数和执行输入与输出。值得注意的是，一个半诚实参与方相当于是零知识中的诚实验证者。

既然积极的恶意敌手更有攻击能力，那么我们到底为什么还要考虑攻击能力更弱的半诚实模型？即半诚实的敌手模型的必要性在哪里？其实在一般情况下，发动主动攻击要比监听整个计算过程在攻击复杂的多，原因是，对于一个运行在计算机上程序，主动的攻击需要用一些非常复杂的程序去攻击他，但是对于单纯的获取计算过程中的数据而言，这是比较容易的，所以半诚实敌手模型在实际的生产生活中更加的普遍存在，就是单独考虑半诚实敌手的必要性。

接下来我们主要探讨在安全半诚实模型中的两个等价的公式，  
1.第一个公式直接推广了零知识的定义的一般性，进一步定义了半诚实模型下的安全性。  
2.第二种来源于之前定义的“real VS ideal”方法学。

两种方法都是遵循“模拟范式”，第一种直接来源于零知识的定义，第二种来源于“退化的通用真实-理想模型”  
ps:模拟范式（“simulation paradigm”）可能来源于GMW86，这个没看过，还需要确定。

### 从零知识的角度看半诚实模型 ###

简单的来说，如果一个协议能够保密的计算函数 f , 那么凡是能够从一个参与方视图获得的内容，都能够完全从这个参与方的输入输出获得。

为了描述方面，这里定义一些半诚实的行为：  
计算的函数 f : \{0,1\}\* x \{0,1\}\* - > \{0,1\}\* x \{0,1\}\* , 计算结果为 f( x , y）；  
其中第一方的计算结果：f1(x , y) 为计算结果的第一个元素；  
其中第一方的计算结果：f2(x , y) 为计算结果的第二个元素；  
协议PI，是一个两方协议用来计算函数f；  
第一方和第二方的视图 VIEW(x, y ) ;(x, r , m1,m2,…,mt), 其中r是一方随机输出，m 为第t次的输出消息。  
协议执行完成之后的输出定义为OUTPUT（x,y）

#### deterministic case 对于确定性的例子 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]  
确定性的例子即为，输入确定，则输出时不会变化的。所以只需要考虑模拟器的视图和协议执行的视图即可。

#### general case 对于确定性的例子 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]  
对于通用的例子来说，其实就是，对于概率性的算法，每次的输出可能是不相同的，所以需要对比模拟器的视图和协议执行者的视图。其中式子右边的这个四部分内容都是相关的随机数，被定义来源于相同的随机过程，特别是，OUTPUT完全是相应的由视图VIEW定义。

#### 基于零知识原语的模拟 ####

首先考虑一个确定性的例子，由式子7.8 7.9 来看，能够都有效的模拟，完全取决于他自己的输入和输出。也就是说参与方能够从执行过程中获得所有的信息本质上都包含在他本身的输入和输出中。对于确定的函数来说，存在以下的内容：  
![在这里插入图片描述][20191114170154744.png]  
协议的输出和函数的输出相等。

和确定性函数相反的情形就是通用的情形，涉及到随机的计算过程时，输出不一定要满足上图中，协议的输出和函数的输出相等的关系。因为每一方都是输随机的，确实，这两个随机的值必须是分布相同的或者分布相似的，但是这并不能完全这样断言。如下有这样一个反例：  
![在这里插入图片描述][20191114190836771.png]  
r 是均匀分布在字符串\{1,0\}中，P1先选择一个随机数r, 然后发送给P2 ，然后P2 在输出这个值，就是如此简单的计算一个函数值。但是这个式子只满足7.8 但是却不满足7.10。当模拟者S2输出一个随机的r时。原因在于模拟器应当输出一个可能的输出结果，而此处的模拟器随便输出的值，本身就不符合应当输出值的随机性。这是因为，在一方的输出和另一方视图在同一个协议的执行过程，要求保存这个关系存在于模拟过程中。所以在模拟中，模拟者的视图应该也是和对方的输入有关系，并要保持这个关系，但是问题是，在上个反例中，模拟器随机的输出一个值破坏了这个关系。这是模拟安全的核心，我们应该模拟一个半诚实方真实可能的输出，而不仅仅是一个分布相同的值。

进一步的，式子7.9 、7.10要求参与方的被模拟视图应该和实际输出相匹配，为了演示这个问题，我们描述如下情况，P1选择一个随机的字符串s, 并且输出r = F(s) ，F是一个单项函数，再一次这个协议相当于继续执行了当前的协议，但是并不清楚这个计算是不是保密的。（因为P1学习到了F输出的前象内容）注意，一个模拟器S1（1^n,r）选择一个均匀的值s ,并且输出（s, F(s））满足7.7 但是不满足7.9. 因为模拟器的随机选择破坏了之前的随机选择。但是我们认为这个问题要比上一个问题宽松一些，可以使用下面的这个公式来代替7.7 和 7.9.  
![在这里插入图片描述][20191114195024847.png]  
上式解决了第一项提出的问题，但是没有解决当前的问题，其实上式的设计是，用来比较最后的对方的输出，即只要保证第二方的协议输出和函数输出同分布即可，即只要求模拟器的视图和执行的视图以及对应模拟器方的输出和真实对应于被模拟器的输出相对应，比之7.9放宽了条件。对于式子7.9 和 7.11而言最大的不同是，亲着强制要求模拟的视图和模拟器的输出向匹配，但是这并没有在7.11中得到保证。确实，对于7.11 来说S1中的视图可能和S1的模拟输出不匹配，但是被模拟的视图却能和诚实的P2输出相对应。这个不一定是真正的事实，但是我们在实践中倾向于使用一种更加严格的方式来定义这个问题。

### non-uniform families of polynomial-time VS PPT ###

###### 以上内容参考《Foundations.of.Cryptography.Volume.2.Basic.Applications(Oded.Goldreich)》 ######

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191114164157341.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191114164512579.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4,size_16,color_FFFFFF,t_70
[20191114170154744.png]: https://img-blog.csdnimg.cn/20191114170154744.png
[20191114190836771.png]: https://img-blog.csdnimg.cn/20191114190836771.png
[20191114195024847.png]: https://img-blog.csdnimg.cn/20191114195024847.png