短可否认环签名：固定大小与低开销

### 短可否认环签名：固定大小与低开销 #### 1. 相关工作回顾 在环签名领域，前人已经做出了不少努力。Komano等人引入了交互式可否认环签名，但这类签名并不流行。Park等人提出了非交互式可抵赖环签名方案，能通过非交互式算法生成签名否认，但未考虑抵赖不可伪造性，且签名算法的时间复杂度很高。Lin等人提出的对数大小可拒绝签名方案改进了上述问题，但仍有提升空间。 2004年，Liu等人提出了首个可链接环签名方案，Tsang等人利用累加器和知识签名技术实现了固定签名大小的可链接环签名，Au等人对短签名技术进行了安全优化，Wang等人将短关联环签名技术应用于可编辑区块链。然而，这些方案都未满足环签名的最新要求——可抵赖性。 #### 2. SRRS方案介绍 为解决上述问题，我们提出了基于动态累加器和SPK的可否认环签名方案SRRS。该方案结合了短关联环签名和可抵赖环签名的构造，包含七个算法，具体如下： 1. **SRRS.Setup(1λ) →(G, q, g, H)**：输入安全参数，根据参数选择一个生成元为g、阶为q的GDH组G，哈希函数H是(0, 1)∗到G的单向映射。 2. **SRRS.Gen(G, q, g, H) →(pki, ski)**：输入系统参数，根据安全参数选择一个随机数ski，生成公钥pki = gski，输出用户的公私钥对(pki, ski)。 3. **SRRS.Sign(R, m, skπ) →(σR(m))**： - 计算集合中所有元素的累积值： \[v = f(u, R) = u\prod pki \mod N\] - 生成证据证明pkπ属于公钥环R： \[wπ = f(u, R/{pkπ}) = u\prod_{i\neq\pi} pki \mod N\] - 计算知识签名： \[SPK\{(pkπ, skπ) : v = wπ pki \mod N \land pki = gski\}(m)\] - 证明双离散对数关系： \[v = wπ g^{skπ}\] - 随机选择k个数r1, r2, …, rk ∈ Zp，计算变量c和s： \[c = H(m||u||N||g||t1|| … ||tn)\] 其中 \[ti = wπ g^{ri} \mod N\] \[si = ri - c[i] * skπ\] - 改进链接标签：计算h = H(R)，链接标签为 \[\tilde{y}π = h^{wπ}\] - 最终得到SRRS签名： \[\sigmaπ(m) = (c, s1, s2, …, sk, v, \tilde{y}π)\] 4. **SRRS.Verify(R, m, σ(m)) →(0 or 1)**： - 计算累积值： \[v = u\prod pki \mod N\] - 若上式不成立，拒绝签名；否则继续计算c′： \[c′ = H(m||u||N||g||t1|| … ||tn||\tilde{y}π)\] 其中 \[ti = \begin{cases} wπ g^{si} & \text{if } c[i] = 0 \\ vπ g^{si} & \text{otherwise} \end{cases} \] - 若c = c′，接受签名；否则拒绝。 5. **SRRS.Repudiate(skD, m, R, σπ(m)) →ξ(σD(m), σπ(m))**： - 生成公钥环成员证据： \[wD = f(u, R/{pkD}) = u\prod_{i\neq D} pki \mod N\] - 计算知识签名： \[SPK\{(pkD, skD) : v = wπ pkD \mod N \land pkD = gskD\}(m)\] - 证明双离散对数关系： \[v = wD g^{skD}\] - 随机选择k个数r1′, r2′, …, rk′ ∈ Z∗p，计算： \[cD = H(m||u||N||g||t1|| … ||tn)\] 其中 \[tj = wD g^{rj} \mod N\] \[sDj = rj - cD[i] * skD\] - 得到SRRS否认签名： \[\sigmaD(m) = (cD, sD1, sD2, …, sDk, v, \tilde{y}D)\] - 得到否认签名ξ = (σD(m), σπ(m))。 6. **SRRS.VerRepu(ξ(σπ(m)), v) →(0 or 1)**： - 验证累积值： \[v = u\prod pki \mod N\] - 若不成立，拒绝否认；否则继续计算： \[cD′ = H(m||u||N||g||t1|| … ||tn)\] 其中 \[ti = \begin{cases} wgsi_D & \text{if } cD[i] = 0 \\ vgsi & \text{otherwise} \end{cases} \] - 若cD′ = cD且wD ≠ wπ，认为否认正确。 7. **SRRS.Link(˜y1, ˜y2) →(0 or 1)**：输入两个签名的链接标识符，若相等输出1，否则输出0。 #### 3. SRRS方案流程图示 ```mermaid graph TD; A[Setup] --> B[Gen]; B --> C[Sign]; C --> D[Verify]; C --> E[Repudiate]; E --> F[VerRepu]; C --> G[Link]; ``` #### 4. SRRS方案性能分析 由于SRRS方案是对RRS方案的改进，我们将两者的性能进行了比较。使用n表示环成员数量，Te、TH和Tm分别表示执行指数运算、群乘法运算和哈希运算的时间开销，忽略耗时较少的操作，对两个方案的签名生成、验证和抵赖阶段进行分析