通用协议（一）

今天药忘吃喽~ 2023-06-12 08:42 113阅读 0赞

# 协议 #

协议：  
协议的本质就是执行一个任务，在密码这个领域有时也称一个协议就是为了计算一个函数，即为求一个函数值，但是这任务或者说求函数值，往往不是有一方来单独计算的，而是由多个参与方合作完成的任务，或者合作计算的值。

举个例子，TCP|IP 的握手协议其实目的就是完成一个认证的任务，由两方来联和执行。又比如，在密码学中的一个经典问题：百万富翁问题；多个富翁聊天，想要知道到底谁最有钱，但是他们又都不愿意泄露自己有多少钱，所以需要一方法，既能比较出哪个富翁最有钱，并且不泄露每个人自己的私有财产。（姚期智解决了这个问题，并且由于他在量子计算机理论和密码学上的贡献，他获得了图领奖）

# 密码学中的协议 #

现代密码学中一个重要问题就是，如何设计一个安全的协议来计算和完成预定的任务，特别是最好能够探索到一种通用的方法学，设计能够实现通用任务的协议。密码学协议是密码学中一个独立的组成部分，它不同于使用那些使用单向函数的具体的加密解密方案，它本质上就是联合各方在符合预期的条件下，完成预定的任务。也可以成为就是安全多方计算（Multi-party computation）或者安全函数计算（SFE）。

# 密码学中的通用协议 #

一个通用的多方（m方）参与的密码学问题主题一般包括以下的三部分：  
1.m个输入：即为各个参与方的本地输入。  
2.m个输出：即为经过协商后的各方输出。  
3.一个特定的随机过程：描述的是计算过程本身。

如果以上的m个参与方互相信任，那么这个问题就非常好解决，即各个参与方将自己的数据发送到信任的参与方身上，然后由受信任的参与方来计算结果，最后将得到的数据发送给其他参与方即可，哪怕大家信任的是外部的参与方。这里存在一个关键的密码学问题是这个可信的参与方在多大程度上能够被互相不信任的参与方模拟。

如下图所示：在多大程度上真实模型能够模拟理想模型  
![一个例子][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]  
但是在现实中，存在各种各样的模型。这些模型依赖于不同的假设，不同的信道设置，以及不同的敌手行为，还有不同的可信方的设计，所以接下来将在不同的情况下，讨论这种模拟是否成立。

### 基本定义与一些模型 ###

模拟范式：一个协议是安全的，当一个可行的敌手在攻击这个协议后所能获得的任意内容均可以在一个理想的情况下获得。在零知识中，任何验证者可以从与证明者交互后获得的内容，都可以通过断言本身获得。在安全多方计算的场景下，我们主要考虑和比较敌手的影响在真实执行过程中和理想的有可信第三方帮助的情况下执行的影响。

如果敌手能够在真实设置中获得的信息也能够在理想的环境下获得，那么这个协议真实的设置就能模拟一个理想的设置，即为模拟一个可信方。并且是绝对安全的。这意味着这些属性在理想情况下满足也能通过一个安全的协议在真实的情况下模拟执行。

上文中的安全往往意味着，各个参与方的私有数据得到保护，并且诚实方收到的数据是安全的。上文的定义可以应用在各个方面。

### 一些安全模型中的参数 ###

Set-up assumptions：在算法的初始化阶段，没有任何的假设，除非用户的特殊说明。但是和我们平时所用的方案类似，在set up 中，一些公共的参数往往是已知的，例如椭圆曲线中的参数，和其他算法中的参数设置。

The communication channels：通信信道的设计主要关注的是通信信道的隐私性和可靠性（privacy & reliablity）。其中一个标准的假设是，敌手可以监听到通信内容（即是是在两个可信的通信方之间）；也就是说信道并不保证隐私性。同时，如果需要假设用户无法获得用户之间可以获得的诚实方之间信息，这个就称之为私有信道（private-channel model）.  
对于标准假设的信道来说，敌手不能获取，修改，复制或者放出信息在通信信道上，其实就是说此处的敌手只能进行监听，即半诚实行为。当然广播信道也存在上述的假设，至少在一定程度上标准的假设可以保证信道上的消息的真实性。

Computational limitations：一般情况下我们考虑PPT敌手（概率多项式时间敌手），然而在私有信道上也允许考虑无限计算能力敌手。个人觉得这是一种折中，因为在私有信道上，敌手不能获得其他额外的信息，只能通过进一步扩大他的计算能力在扩张其能力。

Restricted adversarial behavior：在文献中被提及的最一般的敌手就是那些能腐败参与方的敌手，并且能在协议执行到当下，并进一步决定腐败哪一个参与者基于潜在的信息。换句话说，就是这类敌手，能够腐败其中的参与方，从而达到破坏协议的目的。

non-adptive:  非适应性的敌手，即在协议开始前，不诚实方的集合是固定的（当然，诚实方是并不知道的）。
    adptive: 适应性的敌手，即在协议开始前，不诚实方的集合是不固定的，随着协议的执行会有一些被腐败的参与方参与进来。
    但是一旦被腐败则不能再变回好的参与方。
    passive: 消极的敌手也称为以下的一些名字，semi-honest, passive,honest-but-curious.
    active: 积极的敌手也称为malicious.

Restricted notions of security: 有一些协议是可以容忍的不公平的执行过程的，但是可以被不诚实的参与方检测并终止；并且在终止之后，不诚实的参与方不能比不终止获得的信息更多。这个协议一种可能的结果是，一些诚实的参与方没有获得自己想要的结果，但是宁愿终止这个过程，这种安全被叫做（allows abort）允许中断的，也称之为（allows premature suspension of the execution）。

Upper bounds on the number of dishonest parties：在一些安全多方计算模型中，当且仅当大多数参与方诚实才能保证安全，有的协议也称之为三分之二。

Mobile adversary：移动敌手，极为这个敌手是可移动的，他可能会抓住一个参与方腐败他，然后进一步，可能会释放这个敌手，这就是一个移动的敌手。

### 一个例子：在一个多方协议中存在大多数的诚实方 ###

##### 现在假设存在一个MPC协议，及有m个输入，以及有m个输出，然后计算一个既定的过程; #####

我们考虑的第一个问题是这样的：在一个多方的协议中，每一方在输入之前都是有可能修改自己的输入的，因为这个输入其实是本地的内容，但是这并不被认为是影响安全，这是不可避免的问题。在MPC中的有一个潜在的原语，即多方计算中的情况在真实模型下发生的也能发生在理想模型中。在定义一个安全多方协议的时候，我们需要准确的指出什么是不可避免的情况，在理想的情况下。

一个理想的模型各方执行如下：

1.  第一步，不诚实的少数可以和其他诚实方一样，将输入发送给可信方。
2.  第二步，可信方收到来自各方的数据后，计算确定的输出，然后将输出发送到相应的地方。
3.  第三步， 当接受到输出后，诚实方将这个接受到的值作为输出，不诚实的参与方会根据当亲自己的输入和接受的输出选择自己的输出值。

这种少数的参与方的行为是不可避免的在任何协议的执行过程中（即使是在有可信方存在情况下）。这就是为什么要如此定义理想模型的原因。现在，一个安全多方计算协议要去模拟这样一个理想的过程。就是说，任何可能敌手的影响在真实环境中，都可以被一个敌手在理想的环境下模拟。

### 所有这里有一个重要的问题，为什么理想协议要这样设计？ ###

我尝试总计下，对于MPC，SMPC，SFE来说，本质上其实都是在执行一个任务，或者需要联和计算一个函数值。对于理想的协议来说，最重要的一定安全，这个是毋庸置疑的，肯定的。好的，我们就假定有一个可信的第三方，直接引入这个比较强的安全方，任何敌手不能用任何方法攻破这个可信方，但是我们依然要深入考虑还有没有什么问题，其实任务或者函数已经安全了，唯一的问题就是这些通信方和可信方的通信问题了，经过上文的描述，我们已经发现了，唯一就是这个不可避免的交互方式，所以一个理想的协议（模型）就这样设计了。

### 还有一个更加本质的问题，为什么要这样做？ ###

答案应该在\[GMW86\] 里边，等我看了，我在填补这个答案。

#### 以上内容参考《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/20191111150038561.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4,size_16,color_FFFFFF,t_70