网络无关的统计安全多方计算协议解析

### 网络无关的统计安全多方计算协议解析 #### 1. 相关工作与开放性问题 在网络无关协议的研究中，大多数现有工作都考虑了阈值对手模型。例如，有工作提出了网络无关的密码学安全原子广播协议，也有研究针对多阈值的状态机复制协议。还有一些工作利用特定条件设计了网络无关的近似协议和分布式密钥生成协议等。 不过，目前仍存在一些开放性问题。例如，对于网络无关的完美安全多方计算，条件 \(3t_s + t_a < n\)（或 \(Q(3,1)(P, Z_s, Z_a)\)）是否必要并不明确。现有的工作主要关注无条件安全的网络无关多方计算的可能性，将这些协议的效率提升到最先进的半诚实安全多方计算（SMPC）和主动安全多方计算（AMPC）协议的水平，还需要大量的研究工作。此外，设计针对阈值对手的具有统计安全性和多项式复杂度的网络无关多方计算协议，以及针对一般对手且复杂度与 \(n\) 成多项式关系（而非与 \(|Z_s|\) 相关）的网络无关多方计算协议，都是具有挑战性的开放问题。 #### 2. 预备知识与定义 - **通信模型**：采用成对安全信道模型，参与方 \(P\) 之间通过成对安全信道连接。通信网络可以是同步或异步的，参与方不清楚网络的具体行为。同步网络中，消息在已知时间 \(\Delta\) 内送达；异步网络中，消息会有任意但有限的延迟，最终都会送达。 - **对手模型**：存在恶意（拜占庭）对手 \(Adv\)，可以在协议执行开始时决定腐败 \(P\) 中的一部分参与方。对手在同步和异步网络中分别可以从 \(Z_s\) 和 \(Z_a\) 中选择腐败的参与方子集，且对手结构是单调的。同时，\(Z_s\) 和 \(Z_a\) 分别满足 \(Q(2)(P, Z_s)\) 和 \(Q(3)(P, Z_a)\) 条件，且 \(Z_a \subset Z_s\)，还满足 \(Q(2,1)(P, Z_s, Z_a)\) 条件。 - **计算域**：所有计算都在有限域 \(F\) 上进行，其中 \(|F| > n^5 \cdot 2^{s_{sec}}\)，\(s_{sec}\) 是统计安全参数，以确保多方计算协议的错误概率上限为 \(2^{-s_{sec}}\)。 - **输入与计算目标**：每个参与方 \(P_i\) 有输入 \(x_i \in F\)，参与方希望安全地计算一个函数 \(f: F^n \to F\)，该函数由有限域 \(F\) 上的算术电路 \(ckt\) 表示，电路包含线性和非线性（乘法）门，有 \(c_M\) 个乘法门和乘法深度 \(D_M\)。 - **基础设施**：假设存在无条件安全的公钥基础设施（PKI）用于无条件安全的签名方案，即伪签名。使用 \(|\sigma|\) 表示伪签名的比特大小。为简化，不指定子协议的终止条件，多方计算协议的终止条件将确保所有子协议实例的终止。还会使用现有的随机化异步拜占庭协议（ABA），该协议能保证诚实参与方几乎肯定（概率为 1）最终获得输出，且这种特性会传递到使用 ABA 作为构建块的“更高级”协议中。 #### 3. 网络无关的拜占庭协议 设计了网络无关的拜占庭协议 \(\Pi_{BA}\)，它在同步和异步网络中都能满足拜占庭协议的要求。在同步网络中，诚实参与方在时间 \(T_{BA} = (t + 33)\Delta\) 内获得输出，其中 \(t\) 是对手结构 \(Z_s\) 中最大子集的基数；在异步网络中，诚实参与方几乎肯定最终获得输出。 在设计 \(\Pi_{BA}\) 的过程中，还设计了特殊的拜占庭协议 \(\Pi_{PW}\)，它是通过对经典的 Dolev - Strong（DS）拜占庭协议进行推广，以应对非阈值对手，并基于伪签名设置实现。同时，设计了网络无关的可靠广播协议 \(\Pi_{BC}\)，允许指定的发送方 \(Sen\) 向所有参与方可靠地发送消息 \(m \in \{0, 1\}^{\ell}\)。在协议中，存在指定的本地时间 \(T_{BC} = (t + 4)\Delta\)，此时所有诚实参与方有输出，输出情况根据网络类型和发送方的腐败状态而定： |网络类型|发送方状态|输出情况| | ---- | ---- | ---- | |同步网络|诚实发送方|所有诚实参与方输出 \(m\)| |同步网络|腐败发送方|所有诚实参与方输出一个共同的 \(m^{\star} \in \{0, 1\}^{\ell} \cup \{\perp\}\)| |异步网络|诚实发送方|每个诚实参与方输出 \(m\) 或 \(\perp\)| |异步网络|腐败发送方|每个诚实参与方输出一个共同的 \(m^{\star} \in \{0, 1\}^{\ell}\) 或 \(\perp\)| 协议 \(\Pi_{BC}\) 还为在时间 \(T_{BC}\) 输出 \(\perp\) 的参与方提供了一个选项，如果在 \(T_{BC}\) 之后继续运行协议且满足某些“条件”，可以将输出切换为某个 \(\ell\) 位字符串。这个切换功能在设计 \(\Pi_{BA}\) 时未使用，但在 VSS 协议中广播值时很有用。 #### 4. 网络无关的信息检查协议 网络无关的信息检查协议（ICP）由两个子协议 \(\Pi_{Auth}\) 和 \(\Pi_{Reveal}\) 组成，分别实现认证和揭示阶段。该协议具有以下性质（除了概率至多为 \(\epsilon_{ICP} = \frac{nt}{|F| - 1}\) 的情况，其中 \(t = \max\{|Z| : Z \in Z_s\}\)）： - **诚实参与方情况**： - **同步网络（\(Z_s\) - 正确性）**：在 \(\Pi_{Auth}\) 阶段，每个诚实参与方在时间 \(T_{Auth} = \Delta + 4T_{BC}\) 将 \(authCompleted(S,I,R)\) 设置为 1；在 \(\Pi_{Reveal}\) 阶段，接收方 \(R\) 在时间 \(T_{Reveal} = \Delta\) 输出 \(s\)。 - **异步网络（\(Z_a\) - 正确性）**：每个诚实参与方最终在 \(\Pi_{Auth}\) 阶段将 \(authCompleted(S,I,R)\) 设置为 1，接收方 \(R\) 最终在 \(\Pi_{Reveal}\) 阶段输出 \(s\)。 - **隐私性**：无论网络类型如何，对手的视图与 \(s\) 无关。 - **不可伪造性**：如果 \(S\) 和 \(R\) 诚实，\(I\) 腐败，且 \(R\) 在 \(\Pi_{Reveal}\) 阶段输出 \(s' \in F\)，则 \(s' = s\)。 - **发送方腐败情况**： - **同步网络（\(Z_s\) - 不可抵赖性）**：接收方 \(R\) 在 \(\Pi_{Reveal}\) 阶段输出