非交互式随机消息盲签名技术解析

### 非交互式随机消息盲签名技术解析 #### 1. 引言 在密码学领域，非交互式盲签名（NIBS）是一项重要的技术，它在保障信息安全和隐私方面有着独特的优势。然而，相关的不可能结果给其发展带来了挑战，但也存在一些绕过这些结果的方法，如使用复杂度杠杆。同时，NIBS的一些特性和应用场景与标准盲签名有所不同，引发了一系列值得探讨的问题。 #### 2. 预备知识 ##### 2.1 符号、双线性群和假设 - **符号表示**： - \(y ←A(x)\) 表示算法 \(A\) 以 \(x\) 为输入，输出为 \(y\)。 - \(r ←$ S\) 表示 \(r\) 是从集合 \(S\) 中均匀随机选取的元素。 - \(1_G\) 表示群 \(G\) 中的单位元，\([n]\) 表示集合 \(\{1, \ldots, n\}\)。 - \(A^O\) 表示算法 \(A\) 可以访问预言机 \(O\)。 - **双线性群定义**： - 考虑素数阶 \(p\) 的循环群 \(G_1\)、\(G_2\)、\(G_T\)，\(g_1\)、\(g_2\) 分别是 \(G_1\) 和 \(G_2\) 的生成元。若 \(e : G_1 × G_2 →G_T\) 是一个双线性映射（配对），需满足： - 双线性性：\(\forall(S, T) \in G_1 × G_2\)，\(\forall a, b \in Z_p\)，有 \(e(S^a, T^b) = e(S, T)^{a·b}\)。 - 非退化性：\(e(g_1, g_2) \neq 1\) 是群 \(G_T\) 的生成元。这里考虑的是 Type - 3 配对，即 \(G_1\) 和 \(G_2\) 之间不存在高效可计算的同构。 - **逆判定性 Diffie - Hellman 假设（InvDDH）**：对于所有 PPT 敌手 \(A\)，给定元素 \((g_1^{\alpha}, g_1^{\beta}) \in G_1^2\)，很难判定 \(\beta = \alpha^{-1} \mod p\) 还是 \(\beta ←$ Z_p^*\)。用 \(Adv_{invDDH}(A)\) 表示敌手 \(A\) 解决此问题的优势。 - **强判定性 Diffie - Hellman 假设（sDDH）**：对于所有 PPT 敌手 \(A\)，给定元素 \((g_1^{\alpha}, g_1^{\beta}, g_1^{\beta^{-1}}, g_1^{\gamma}) \in G_1^4\)，很难判定 \(\gamma = \alpha·\beta \mod p\) 还是 \(\gamma ←$ Z_p^*\)。用 \(Adv_{sDDH}(A)\) 表示敌手 \(A\) 解决此问题的优势。 ##### 2.2 签名方案 一个签名方案 \(SIG\) 由三个 PPT 算法 \((KeyGen, Sign, Verify)\) 组成，具体如下： |算法|输入|输出| | ---- | ---- | ---- | |KeyGen(\(\lambda\))|安全参数 \(\lambda\)|公钥和私钥对 \((pk, sk)\)| |Sign(sk, m)|私钥 \(sk\) 和消息 \(m\)|签名 \(\sigma\)| |Verify(pk, m, \(\sigma\))|公钥 \(pk\)、消息 \(m\) 和签名 \(\sigma\)|0 或 1| 签名方案需满足以下性质： - **正确性**：对于任意安全参数 \(\lambda \in N\) 和任意消息 \(m\)，若 \((pk, sk) ← SIG.KeyGen(\lambda)\)，\(sig ← SIG.Sign(sk, m)\)，则 \(SIG.Verify(pk, m, sig) = 1\)。 - **选择消息攻击下的存在不可伪造性（EUF - CMA）**：每个 PPT 敌手 \(A\) 在以下实验中的优势至多是可忽略的。 ```plaintext EUF - CMA_{A,SIG}(\lambda) Q := ∅ (sk, pk) ← SIG.KeyGen(\lambda) (m^*, \sigma^*) ← A^{O_1(sk,·)}(pk) return m^* \neq m \forall m \in Q ∧ SIG.Verify(pk, m^*, \sigma^*) = 1 O_1(sk, m) \sigma ← SIG.Sign(sk, m) Q := Q ∪ {m} return \sigma ``` 敌手 \(A\) 的优势定义为 \(Adv_{SIG}(A) = Pr[EUF - CMA_{A,SIG}(\lambda) = 1]\)。 ##### 2.3 双模见证不可区分证明 在通用构造中，使用 Groth - Sahai（GS）提出的双模非交互式见证不可区分证明系统。该系统的主要特点是存在一个公共参考字符串（crs），可以处于“绑定”或“隐藏”模式，不同模式下满足不同的性质。 - **证明系统算法**： - \(Setup(\lambda, binding)\)：输入安全参数，输出绑定的公共参考字符串 \(crs\) 和陷门 \(td_{Ext}\)。 - \(Setup(\lambda, hiding)\)：输入安全参数，输出隐藏的公共参考字符串 \(crs\)。 - \(Prove(crs, x, w)\)：输入公共参考字符串 \(crs\)、陈述 \(x\) 和见证 \(w\)，输出证明 \(\pi\)。 - \(Verify(crs, x, \pi)\)：输入公共参考字符串 \(crs\)、陈述 \(x\) 和证明 \(\pi\)，输出 0 或 1。 - \(Extract(td_{Ext}, x, \pi)\)：输入提取陷门 \(td_{Ext}\)、陈述 \(x\) 和证明 \(\pi\)，输出见证 \(w\)。 - **证明系统性质**： - **模式不可区分性**：对于所有 \(\lambda\)，定义敌手 \(A\) 针对模式不可区分性的优势为 \(Adv_{modeIND,A}(\lambda) = \left| Pr\left[\begin{array}{l}mode = mode^*:\\mode ←$ \{binding, hiding\};\\(crs) ← Setup(\lambda, mode);\\mode^* ← A(\lambda, crs)\end{array}\right] - \frac{1}{2}\right|\)，若对于所有 PPT 敌手 \(A\)，该优势是可忽略的，则称证明系统是模式不可区分的。 - **两种模式下的完美完备性**：对于所有安全参数 \(\lambda \in N\)、所有陈述 \(x \in L_R\) 和所有满足 \(R(x, w) = 1\) 的见证 \(w\)，当 \(crs ← Setup(\lambda, binding)\) 且 \(\pi ← Prove(crs, x, w)\) 时，有 \(Verify(crs, x, \pi) = 1\)；对于 \(crs ← Setup(\lambda, hiding)\) 同样成立。 - **绑定模式下的完美可靠性**：对于所有敌手 \(A\)，有 \(Pr\left[\begin{array}{l}(crs, td_{Ext}) ← Setup(\lambda, binding) : Verify(crs, x, \pi) = 1\\(x, \pi) ← A(crs) ∧ x \notin L_R\end{array}\right] = 0\)。 - **绑定模式下的可提取性**：对于任意 \((x, \pi)\)，有 \(Pr\left[\begin{array}{l}(crs, td_{Ext}) ← Setup(\lambda, binding) : Verify(crs, x, \pi) = 1\\w ← Extract(td_{Ext}, x, \pi) \Rightarrow R(x, w) = 1\end{array}\right] = 1\)。 - **隐藏模式下的完美见证不可区分性**：对于所有敌手 \(A\)，若 \(A\) 的输出满足 \(R(x, w_0) = R(x, w_1) = 1\)，则 \(\left| Pr\left[\begin{array}{l}crs ← Setup(\lambda, hiding) : \hat{b} ← A(crs, \pi^*);\\(x, w_0, w_1) ← A(crs);\\b ←$ \{0, 1\};\\\pi^* ← Prove(crs, x, w_b)\end{array}\right] - \frac{1}{2}\right| = 0\)。 ##### 2.4 可验证随机函数（VRF） 一个可验证随机函数 \(VRF = (Gen, Eval, P, V)\) 由以下 PPT 算法组成，输入长度为 \(n(\lambda)\)，输出长度为 \(m(\lambda)\)： |算法|输入|输出| | ---- | ---- | ---- | |Gen(\(\lambda\))|安全参数 \(\lambda\)|秘密密钥 \(sk_{VRF}\) 和公共验证密钥 \(pk_{VRF}\)| |Eval(\(sk_{VRF}, x\))|秘密密钥 \(sk_{VRF}\) 和输入值 \(x \in \{0, 1\}^{n(\lambda)}\)|输出值 \(y \in \{0, 1\}^{m(\lambda)}\