盲签名方案BSR的安全性分析

### 盲签名方案BSR的安全性分析 #### 1. 引言 在密码学领域，盲签名方案在保护用户隐私和数据安全方面起着重要作用。本文将详细分析盲签名方案BSR的安全性，主要关注其恶意签名者盲性和一次性不可伪造性。 #### 2. BSR签名验证流程 - **基本验证**： - 若存在 $i \in [K]$ 使得 $e(pk_{i,1}, g_2) \neq e(g_1, pk_{i,2})$，则返回 0。 - 对于每个 $i \in [K]$，计算 $\mu_i := H_{\mu}(m, \phi_i)$。 - 当且仅当 $e(\overline{\sigma}, g_2) = \prod_{i = 1}^{K} e(H(\mu_i), pk_{i,2})$ 时，返回 1。 - **流程总结**： ```mermaid graph TD; A[开始] --> B{是否存在i使e(pki,1, g2) ≠ e(g1, pki,2)}; B -- 是 --> C[返回0]; B -- 否 --> D[计算μi = Hμ(m, ϕi)]; D --> E{是否e(¯σ, g2) = ∏ e(H(μi), pki,2)}; E -- 是 --> F[返回1]; E -- 否 --> C; ``` #### 3. 安全性分析准备 - **引理1**：对于任意 $pk_1 \in G_1$ 和 $pk_{i,1} \in G_1$，$i \in [K]$ 且 $\sum_{i = 1}^{K} pk_{i,1} = pk$，以下两个分布 $D_1$ 和 $D_2$ 相同： - $D_1 := \left\{(pk_1, (pk_{i,1})_{i \in [K]}, (pk_{i,1}')_{i \in [K]}) \mid r_1, \ldots, r_{K - 1} \leftarrow \mathbb{Z}_p, r_K := -\sum_{i = 1}^{K - 1} r_i; \forall i \in [K] : pk_{i,1}' := pk_{i,1} \cdot g_1^{r_i}\right\}$ - $D_2 := \left\{(pk_1, (pk_{i,1})_{i \in [K]}, (pk_{i,1}')_{i \in [K]}) \mid \forall i \in [K] : pk_{i,1}' \leftarrow G; pk_{K,1}' := pk_1 \cdot \prod_{i = 1}^{K - 1} pk_{i,1}'^{-1}\right\}$ #### 4. 恶意签名者盲性证明 - **定理1**：设 $H_r, H_{\mu} : \{0, 1\}^* \to \{0, 1\}^{\lambda}$ 和 $H_{\alpha} : \{0, 1\}^* \to \mathbb{Z}_p$ 为随机预言机，则 BSR 满足恶意签名者盲性。具体而言，对于任何最多分别向 $H_r, H_{\mu}, H_{\alpha}$ 进行 $Q_{H_r}, Q_{H_{\mu}}, Q_{H_{\alpha}}$ 次查询的算法 $A$，有 $Adv_{A, BS}^{blind}(\lambda) \leq \frac{KNQ_{H_{\mu}}}{2^{\lambda - 2}} + \frac{KQ_{H_r}}{2^{\lambda - 2}} + \frac{KQ_{H_{\alpha}}}{2^{\lambda - 2}}$。 - **证明过程（游戏序列）**： - **游戏 $G_{0,b}$**：定义为 $G_{0,b} := BLIND_{A, b, BS}(\lambda)$。对手 $A$ 输出公钥 $pk$ 和两条消息 $m_0, m_1$，并可访问两个交互式预言机 $O_0$ 和 $O_1$，分别模拟 $U(pk, m_b)$ 和 $U(pk, m_{1 - b})$。 - **游戏 $G_{1,b}$**：若 $A$ 对某些 $i \in [K]$ 和 $j \in [N] \setminus \{J_i\}$ 进行 $H_{\mu}(\cdot, \phi_{i,j})$ 形式的查询，则游戏中止。$|Pr [G_{0,b} \Rightarrow 1] - Pr [G_{1,b} \Rightarrow 1]| \leq \frac{KNQ_{H_{\mu}}}{2^{\lambda - 1}}$。 - **游戏 $G_{2,b}$**：若 $A$ 对某些 $i \in [K]$ 进行 $H_r(r_{i,J_i})$ 或 $H_{\alpha}(\gamma_{i,J_i})$ 查询，则游戏中止。$|Pr [G_{1,b} \Rightarrow 1] - Pr [G_{2,b} \Rightarrow 1]| \leq \frac{KQ_{H_r}}{2^{\lambda - 1}} + \frac{KQ_{H_{\alpha}}}{2^{\lambda - 1}}$。 - **游戏 $G_{3,b}$**：改变最终签名计算方式，通过暴力搜索计算 $\overline{\sigma}''$ 使得 $e(\overline{\sigma}'', g_2) = \prod_{i = 1}^{K} e(H(\mu_{i,J_i}), pk_{i,2}')$，并将其包含在最终签名中。$Pr [G_{2,b} \Rightarrow 1] = Pr [G_{3,b} \Rightarrow 1]$。 - **游戏 $G_{4,b}$**：不再运行 $ReRa$ 算法，而是通过新鲜共享计算 $pk_{i}'$。$Pr [G_{3,b} \Rightarrow 1] = Pr [G_{4,b} \Rightarrow 1]$。 - **游戏 $G_{5,b}$**：采样随机向量 $\hat{J}_L \leftarrow [N]^K$ 和 $\hat{J}_R \leftarrow [N]^K$，若后来 $\hat{J}_L \neq J_L$ 且 $\hat{J}_R \neq J_R$，则游戏中止。$Pr [G_{5,b} \Rightarrow 1] = \frac{1}{N^{2K}} \cdot Pr [G_{4,b} \Rightarrow 1]$。 - **游戏 $G_{6,b}$**：改变 $\mu_{i,j}$ 的计算方式，对于 $i \in [K]$ 和 $j \in [N] \setminus \{\hat{