一种新颖的洗牌证明：原理、性能与未来展望

### 一种新颖的洗牌证明：原理、性能与未来展望 #### 1. 基本定义 在密码学的相关研究中，有几个重要的定义需要明确： - **完备性（Completeness）**：设 $(P, V)$ 如定义 1 所述，当且仅当对于所有 $(x, y) \in R$，有 $\Pr (\langle P(x, y), V (y)\rangle = 1) = 1$ 时，我们称 $(P, V)$ 实现了完备性。 - **特殊可靠性（Special soundness）**：设 $(P, V)$ 如定义 1 所述，当且仅当存在一个多项式时间提取算法 $Ext$ 时，我们称 $(P, V)$ 实现了特殊可靠性。其中，$Ext$ 以声明 $y \in Y$ 以及两个接受的转录本 $(a, e, z)$、$(a, e', z')$（其中 $e \neq e'$）作为输入，并输出见证 $x$ 使得 $(x, y) \in R$。 - **特殊诚实验证者零知识（Special honest verifier zero - knowledge）**：设 $(P, V)$ 如定义 1 所述，当且仅当存在一个概率多项式时间模拟器算法 $Sim$ 时，我们称 $(P, V)$ 实现了特殊诚实验证者零知识。$Sim$ 以声明 $y \in Y$ 和挑战 $e$ 作为输入，并输出一个接受的转录本 $(a, e, z)$，使得 $Sim(y, e) = trans(\langle P(x, y), V_e(y)\rangle)$ 成立，即模拟器的输出 $Sim(y, e)$ 与 $P(x, y)$ 和选择挑战 $e$ 的 $V(y)$ 之间的转录本具有相同的分布。 #### 2. 洗牌兼容的 Sigma 协议（SCSP） 洗牌兼容的 Sigma 协议（SCSP）是与洗牌证明兼容的 $\Sigma$ - 协议。其主要特征在于，公共声明 $y$ 可以表示为 $y = (prm, c_0, c_1)$，其中 $c_0$ 是洗牌的“输入”元素，$c_1$ 是“输出”元素。对于给定的挑战 $e \in \{0, 1\}$，验证者最终检查的输入可以限制为部分公共声明 $(prm, c_e)$ 以及转录本 $(a, e, z)$。 SCSP 是一对概率多项式时间交互式图灵机 $(P, V)$，具体信息如下： - 证明者 $P$ 以见证 - 声明对 $(x, (prm, c_0, c_1)) \in R$ 作为输入。 - 验证者 $V$ 以声明 $y = (prm, c_0, c_1)$ 作为输入，并返回 0 或 1。 - $P$ 和 $V$ 之间的交互结构如下： 1. $P$：计算 $(a, \alpha) \leftarrow Com(x, y)$ 并将承诺 $a$ 发送给 $V$。 2. $V$：计算挑战 $e \overset{r}{\leftarrow} \{0, 1\}$ 并将 $e$ 发送给 $P$。 3. $P$：计算响应 $z \leftarrow Resp(x, y, (a, \alpha), e)$ 并将 $z$ 发送给 $V$。 4. $V$：输出 $0/1 \leftarrow Check((prm, c_e), (a, e, z))$。 同时，SCSP 保证了完备性、特殊可靠性以及洗牌兼容的特殊诚实验证者零知识。当且仅当 $V$ 输出 1（即 $Check((prm, c_e), (a, e, z)) = 1$）时，我们称 $(a, e, z)$ 是一个接受的转录本。 #### 3. 通用的正确洗牌 $\Sigma$ 协议 $\Sigma_{Shuffle}$ 我们提出了一个通用的正确洗牌 $\Sigma$ 协议 $\Sigma_{Shuffle}$，它可以调用任何如定义 5 中指定的 SCSP。要证明的形式关系为： $R_{Shuffle} = \{(((x_j)_{j\in[\tau]}, \pi), (prm, (c_j^0)_{j\in[\tau]}, (c_j^1)_{j\in[\tau]})): \forall j \in [\tau]: (x_j, (prm, c_{\pi(j)}^0, c_j^1)) \in R\}$ 其中 $R$ 是底层洗牌兼容 $\Sigma$ 协议的关系。 我们提供了两个证明来表明 $\Sigma_{Shuffle}$ 是关系 $R_{Shuffle}$ 的 $\Sigma$ 协议： - 第一个证明是使用 Coq 进行的机器检查证明。Coq 编码的转换由模块 $ProofOfShuffle$ 给出，该模块定义了如上述所述的洗牌证明，并证明它是关系 $\Sigma_{Shuffle}$ 的 $\Sigma$ 协议。 - 第二个证明是一个密码学证明，具体内容