基于仿射行列式程序的多方非交互密钥交换方案解析

### 基于仿射行列式程序的多方非交互密钥交换方案解析 在密码学领域，密钥交换是一项至关重要的技术。多方非交互密钥交换（NIKE）方案能够让 N 个用户以非交互的方式安全地交换一个秘密密钥 K。传统上，NIKE 方案的构建往往依赖于不可区分混淆（iO）等复杂的概念。本文将介绍一种新的 NIKE 方案实例，它通过使用仿射行列式程序（ADP）来简化原本基于 iO 的构造。 #### 1. 背景知识 在深入探讨新的 NIKE 方案之前，我们需要了解一些必要的背景知识。 - **随机编码**：随机编码方案 RE 用于函数 $f: \{0, 1\}^n \to Y$，由随机分布 R、编码函数 Encode 和译码函数 Decode 组成。它需要满足正确性和安全性要求。正确性指对于任何输入 $M \in \{0, 1\}^n$，$Pr_{R \leftarrow R}[Decode(Encode(M; R)) = C(M)] = 1$；安全性则要求对于所有 $M, M' \in \{0, 1\}^n$ 且 $C(M) = C(M')$，当 $R \leftarrow_R$ 时，$Encode(M; R)$ 和 $Encode(M'; R)$ 的分布相同。安全性定义可以放宽为 $(s, \delta)$ - 安全性，即对于大小至多为 s 的任何电路 $C: \{0, 1\}^{\ell} \to \{0, 1\}$，$Pr_{R \leftarrow_R}[C(Encode(M; R)) = 1] - Pr_{R \leftarrow_R}[C(Encode(M'; R)) = 1] \leq \delta$。 - **多方非交互密钥交换**：NIKE 方案由三个多项式时间算法（Setup、Publish、KeyGen）组成。 - $pars \leftarrow_R Setup(1^{\lambda}, N)$：根据安全参数 $\lambda$ 和参与方数量 N 生成公共参数 pars。 - $(pk(u), sk(u)) \leftarrow_R Publish(pars, u)$：每个参与方 u 生成自己的公钥 $pk(u)$ 和私钥 $sk(u)$，私钥保密，公钥公开。 - $K \leftarrow_R KeyGen(pars, u, sk(u), pk(u), pk(v \in S))$：参与方 u 使用自己的私钥和其他参与方的公钥生成共同密钥 K。 正确性要求任意两个参与方 u 和 v 生成的密钥相同，即 $\forall (u, v) \in [N] \times [N] : Pr[K_u = K_v | K_u \leftarrow_R KeyGen(pars, u, sk(u), pk(v \in [N])) \land K_v \leftarrow_R KeyGen(pars, v, sk(v), pk(u \in [N]))] \in 1 - Negl(\lambda)$。安全性方面，任何概率多项式时间（ppt）有界的对手在特定游戏中获胜的优势是可忽略的。 - **仿射行列式程序**：ADP 由两个 ppt 算法组成。 - $Prog \leftarrow_R ADP.Setup(1^{\lambda}, C)$：根据电路描述 C 输出一个程序 Prog，它由 n + 1 个方阵 $T_i$ 组成，这些矩阵对应于函数 $C: \{0, 1\}^n \to \{0, 1\}$。 - $b \leftarrow ADP.Eval(Prog, M)$：根据程序 Prog 和输入 M，通过计算子集和 $T_0 + \sum_{i = 1}^{n} T_{M_i}^i$ 的行列式得到输出值 b。 ADP 需要满足正确性和安全性要求。正确性指对于所有 $M \in \{0, 1\}^n$，$Pr[C(M) = ADP.Eval(Prog, M) | Prog \leftarrow_R ADP.Setup(1^{\lambda}, C)] = 1$；安全性要求对于特定类别的电路 $C_{\lambda}$ 中的任意 $C_1, C_2$，如果 $\forall M \in \{0, 1\}^{\lambda}, C_1(M) = C_2(M)$，则 $|Pr[b \leftarrow_R A(1^{\lambda}, Prog) | b \leftarrow_R \{0, 1\} \land Prog \leftarrow_R ADP.Setup(1^{\lambda}, C_b)] - \frac{1}{2}| \in Negl(\lambda)$。 #### 2. 先前的 NIKE 工作 Boneh 和 Zhandry 提出的基于 iO 的 NIKE 协议是一个简单的多方非交互密钥交换方案。假设 N 个参与者可以访问一组公共参数 pp。每个参与者计算并发布指定给其余 N - 1 个实体的项。