Intro to Ring Signature

基于RSA的方案描述

1. 核心数学构件

在 RSA 环签名方案中，我们需要定义三个关键的数学组件：

A. 陷门单向置换

对于环中的每个用户 $i$ ，我们使用 RSA 公钥 $(e_{i}, n_{i})$ 定义一个陷门单向置换 $g_{i}$ 。对于输入 $x \in Z_{n_{i}}$ ，定义为：

g_{i} (x) = x^{e_{i}} (\mod n_{i})

其逆运算（只有拥有私钥 $d_{i}$ 的人才能计算）为：

g_{i}^{- 1} (y) = y^{d_{i}} (\mod n_{i})

注意：为了统一不同用户的模数 $n_{i}$ ，我们可以引入公共的大整数 $b$ ，使得 $2^{b} > max (n_{i})$ ，将运算域统一映射到 $[0, 2^{b})$ 区间。

B. 带密钥的组合函数

这是环签名的灵魂。我们需要一个函数 $C_{k, v} (y_{1}, y_{2}, \dots, y_{r})$ ，它满足两个关键性质：

环状结构： 输入是环中每个成员的输出值 $y_{i}$ 。
可逆性： 给定密钥 $k$ 、初始值 $v$ 和除 $y_{s}$ 以外的所有 $y_{i}$ ，可以高效地解出 $y_{s}$ 。

Rivest 提出的构造是基于对称加密（如 AES 或 SHACAL）的加密链：

C_{k, v} (y_{1}, \dots, y_{r}) = E_{k} (y_{r} \oplus E_{k} (y_{r - 1} \oplus \dots \oplus E_{k} (y_{1} \oplus v) \dots))

其中：

$k$ 是密钥（通常由消息 $m$ 的哈希生成，即 $k = h (m)$ ）。
$v$ 是随机初始向量（IV）。(这里可以联想到分组密码的CBC模式)
$E_{k}$ 是对称加密算法。
$\oplus$ 是异或运算。

C. 环方程

签名的目标是找到一组值 $y_{1}, \dots, y_{r}$ ，使得组合函数的输出等于初始值 $v$ ：

C_{k, v} (y_{1}, y_{2}, \dots, y_{r}) = v

2. 签名算法

假设签名者是环中的第 $s$ 个用户，拥有私钥 $d_{s}$ 。环成员公钥集合为 $L = {p k_{1}, \dots, p k_{r}}$ 。( $p k$ 既加密用的 $e$ )

步骤 1：生成密钥与随机数

计算对称密钥 $k = h (m)$ 。
随机选择一个初始值（胶水值） $v \in {0, 1}^{b}$ 。

步骤 2：填充诱饵 对于环中除自己以外的所有成员 $i \neq s$ ：

随机选择 $x_{i} \in Z_{n_{i}}$ 。
计算 $y_{i} = g_{i} (x_{i}) = x_{i}^{e_{i}} (\mod n_{i})$ 。
此时，我们有了所有的 $y_{i}$ ，唯独缺少 $y_{s}$ 。

步骤 3：逆向求解 $y_{s}$ 我们需要解环方程 $C_{k, v} (y_{1}, \dots, y_{r}) = v$ 来求出 $y_{s}$ 。根据组合函数的定义，我们可以将方程展开。为了求出 $y_{s}$ ，我们需要从方程的两端向中间“夹击”。

令 $u_{0} = v$ 。我们可以正向计算前 $s - 1$ 项的中间值：

u_{i} = E_{k} (y_{i} \oplus u_{i - 1}) for i = 1, \dots, s - 1

同时，我们可以利用目标值 $v$ 反向计算后 $r - s$ 项的中间值（利用对称加密的可逆性 $D_{k}$ ）：

u_{i - 1} = D_{k} (u_{i}) \oplus y_{i} for i = r, r - 1, \dots, s + 1

(注：这里简化了索引，实际是从 $v$ 开始逆向解密)

最终，我们会得到两个中间状态值，使得：

E_{k} (y_{s} \oplus u_{s - 1}) = u_{s}

其中 $u_{s - 1}$ 是正向计算得到的， $u_{s}$ 是反向计算得到的（或者说是使得后续链条最终回到 $v$ 所需的值）。

于是，我们可以直接解出 $y_{s}$ ：

y_{s} = D_{k} (u_{s}) \oplus u_{s - 1}

步骤 4：计算陷门逆 现在我们有了 $y_{s}$ ，但签名需要的是 $x_{s}$ （即 $g_{s}$ 的输入）。由于签名者拥有私钥 $d_{s}$ ，他可以计算：

x_{s} = g_{s}^{- 1} (y_{s}) = y_{s}^{d_{s}} (\mod n_{s})

步骤 5：输出签名 签名为元组： $σ = (p k_{1}, \dots, p k_{r}; v; x_{1}, \dots, x_{r})$ 。

3. 验证算法

验证者收到消息 $m$ 和签名 $σ$ 。

恢复密钥： 计算 $k = h (m)$ 。
计算 $y_{i}$ ： 对于所有 $i = 1 \dots r$ ，使用公钥计算 $y_{i} = g_{i} (x_{i}) = x_{i}^{e_{i}} (\mod n_{i})$ 。
验证环方程： 计算 $C_{k, v} (y_{1}, \dots, y_{r})$ 。
判定： 如果计算结果等于 $v$ ，则签名有效；否则无效。

4. 数学证明与安全性分析

A. 正确性证明

命题： 如果签名是按照上述步骤生成的，那么验证算法一定输出 True。

证明： 验证者计算的是：

Z = E_{k} (y_{r} \oplus E_{k} (\dots \oplus E_{k} (y_{1} \oplus v) \dots))

在签名生成过程中，我们构造 $y_{s}$ 的目的正是为了满足方程 $C_{k, v} (y_{1}, \dots, y_{r}) = v$ 。具体来说，我们在步骤 3 中通过 $y_{s} = D_{k} (u_{s}) \oplus u_{s - 1}$ 强行使得加密链在 $s$ 处连接，并且最终输出回到 $v$ 。由于 $x_{i}$ 是通过 $g_{i}$ 正确生成的（ $y_{i} = g_{i} (x_{i})$ ），验证者计算出的 $y_{i}$ 与签名者使用的一致。因此， $Z = v$ 恒成立。证毕。

B. 无条件匿名性证明

命题： 即使攻击者拥有无限算力，甚至拥有环中所有成员的私钥，他猜中真实签名者的概率也是 $1 / r$ 。

证明思路： 我们需要证明签名 $σ$ 的分布与真实签名者 $s$ 的身份无关。

$v$ 的分布： $v$ 是均匀随机选择的。
$x_{i} (i \neq s)$ 的分布： 是均匀随机选择的。
$y_{i} (i \neq s)$ 的分布： 由于 $g_{i}$ 是置换， $y_{i}$ 也是均匀分布的。
$y_{s}$ 的分布： $y_{s} = D_{k} (u_{s}) \oplus u_{s - 1}$ 由于 $E_{k}$ 是伪随机置换，且 $v$ 和其他 $y_{i}$ 都是随机的，中间值 $u_{s}$ 和 $u_{s - 1}$ 对于观察者来说看起来也是随机的。因此 $y_{s}$ 在 ${0, 1}^{b}$ 上也是均匀分布的。
$x_{s}$ 的分布： $x_{s} = g_{s}^{- 1} (y_{s})$ 。由于 $g_{s}$ 是置换， $x_{s}$ 也是均匀分布的。

结论： 对于任何观察者来说，签名中的每一个分量 $(x_{1}, \dots, x_{r})$ 看起来都是从各自的域中均匀随机抽取的。没有任何统计特征能将签名与特定的 $s$ 联系起来。即使攻击者拥有所有私钥，他也无法区分“真实的签名”和“模拟的签名”（即攻击者自己随机选一个 $s$ 并伪造一个满足方程的签名）。因此，匿名性是无条件的（信息论安全的）。

基于椭圆曲线的方案

其实从上面的描述中不难看出，本质上就是一个公钥方案的变形，故而很自然地就能得出在EC上的方案描述

1. 密钥生成

选择椭圆曲线参数：选定一条标准的椭圆曲线，并确定其基点（生成元） $G$ 和阶 $n$ 。
生成密钥对：对于环中的 $N$ 个成员，每个成员独立生成自己的密钥对: ( $s k_{i}$ , $p k_{i}$ = $s k_{i} G$ )

所有成员的公钥集合 $p k_{0}, p k_{1}, . . ., p k_{N - 1}$ 构成了这个“环”。

2. 签名

假设签名者在环中的位置为 $s$ （采用 $0$ -based 索引，即成员编号为 $0, 1, \dots, N - 1$ ）。

选择随机起点：
- 随机选择 $α \in Z_{n}$ ，并计算临时承诺 $U = α G$ 。
- 令挑战从 $s$ 的下一个位置开始（按模 $N$ 计算）： $c_{(s + 1) mod N} = H (m ∥ U)$
沿环生成（除签名者外）：
- 按环索引遍历 $i = (s + 1) mod N, (s + 2) mod N, \dots, (s + N - 1) mod N$ （即所有 $i \neq s$ ）：
  - 随机选择 $r_{i} \in Z_{n}$ ；
  - 计算 $R_{i} = r_{i} G + c_{i} p k_{i}$
  - 再计算下一项挑战 $c_{(i + 1) mod N} = H (m ∥ R_{i})$
计算签名者响应并闭环：
- 当链回到 $i = s$ 时，已知 $c_{s}$ ，计算 $r_{s} = (α - c_{s} \cdot s k_{s}) mod n$
- 则 $R_{s} = r_{s} G + c_{s} p k_{s} = α G = U$
- 因而 $H (m ∥ R_{s}) = H (m ∥ U) = c_{(s + 1) mod N}$
闭环成立。
生成签名：
- 签名输出为 $σ = (c_{0}, r_{0}, r_{1}, \dots, r_{N - 1})$
- 其中 $c_{0}$ 是挑战链绕环后的第一项，不是独立预设的随机值。

3. 验签

任何验证者已知：消息 $m$ 、签名 $(c_{0}, r_{0}, . . ., r_{N - 1})$ 以及环中所有成员的公钥 $p k_{0}, . . ., p k_{N - 1}$ 来验证签名的有效性。

重新计算：
- 从签名给出的 $c_{0}$ 开始，对 $i = 0, 1, \dots, N - 1$ 依次计算： $R_{i} = r_{i} G + c_{i} p k_{i}$ $c_{(i + 1) mod N} = H (m ∥ R_{i})$
检查闭环：
- 计算最后一步得到的闭环挑战： $c_{0}^{'} = H (m ∥ R_{N - 1})$
- 检查是否满足： $c_{0}^{'} = c_{0}$

如果成立，则验证通过。这证明了签名确实由环中某个持有对应私钥的成员生成，但无法确定具体身份，从而实现匿名性。

本质上，我们是让 $U (= α G)$ 与签名者位置的承诺一致，即 $U = r_{s} G + c_{s} s k_{s} G$ 。

Intro to Ring Signature ​

基于RSA的方案描述 ​

1. 核心数学构件 ​

A. 陷门单向置换 ​

B. 带密钥的组合函数 ​

C. 环方程 ​

2. 签名算法 ​

3. 验证算法 ​

4. 数学证明与安全性分析 ​

A. 正确性证明 ​

B. 无条件匿名性证明 ​

基于椭圆曲线的方案 ​

1. 密钥生成 ​

2. 签名 ​

3. 验签 ​