Rai-Choo：高效盲签名方案的创新之路

### Rai-Choo：高效盲签名方案的创新之路 #### 1. 技术概述 - **Boosting 变换与 PI - Cut - Choo** - **Boosting 变换**：假设存在一个盲签名方案 BS，它能抵御对手对签名者进行少量签名查询的攻击。通过 Boosting 变换，可得到一个新的签名方案，该方案在签名者和对手进行任意数量的签名交互时都是安全的。在第 N 次签名交互中，用户和签名者的行为如下： 1. 用户使用随机性 $\phi_j$（$j \in [N]$）对消息 $m$ 进行承诺，得到 $N$ 个承诺 $\mu_j$。同时，为 BS 的用户算法采样随机硬币 $\rho_j$（$j \in [N]$）。然后，使用随机预言机对每对 $(\mu_j, \rho_j)$ 进行承诺，并将结果承诺 $\tau_j$ 发送给签名者。 2. 签名者和用户并行运行底层方案 BS $N$ 次，这 $N$ 次并行运行称为会话。具体而言，签名者使用其秘密密钥 $sk$，用户在第 $j$ 个会话中使用公钥 $pk$、$\mu_i$ 作为消息以及 $\rho_j$ 作为随机硬币（$j \in [N]$）。 3. 在签名者向用户发送最终消息 $s_j$（$j \in [N]$）之前，签名者选择一个随机会话 $J \in [N]$。用户需要通过发送 $(\mu_j, \rho_j)$ 打开除第 $J$ 个会话之外的所有承诺 $\tau_j$。签名者可以验证用户在除第 $J$ 个会话之外的所有会话中是否诚实。如果用户在某个会话中不诚实，签名者将中止。 4. 签名者通过发送最终消息 $s_J$ 完成第 $J$ 个会话。最后，用户从该会话中导出签名 $\sigma_J$，并输出 $\sigma = (\sigma_J, \phi_J)$ 作为最终签名。 - **PI - Cut - Choo**：Boosting 变换存在一些问题，即得到的签名方案参数大小不切实际，这是由于对 BS 的归约相对宽松。为了解决这些问题，引入了 Boosting 变换的并行实例版本（PI - Cut - Choo）。其主要目标是适用于仅密钥安全的方案 BS，即归约可以在不访问 BS 的签名预言机的情况下完全模拟变换方案中的签名查询。具体做法是，首先将 $N$ 按某个常数进行缩放，使得成功作弊的期望次数小于 11。为了确保以压倒性概率成立，整个 Boosting 变换以 $K = \Theta(\lambda)$ 个实例并行重复。这些实例使用独立的公钥 $pk_1, \ldots, pk_K$ 和独立的随机硬币。这意味着以压倒性概率，存在一个实例 $i^* \in [K]$，使得在归约的整个运行时间内该实例中没有成功作弊。归约可以猜测 $i^*$ 并将 BS 的目标公钥嵌入到 $pk_{i^*}$ 中。如果猜测正确，对 BS 的仅密钥安全的归约就可以通过。 以下是第 N 次签名交互的流程图： ```mermaid graph TD; A[用户对消息 m 承诺] --> B[用户采样随机硬币]; B --> C[用户对 (μj, ρj) 承诺并发送给签名者]; C --> D[签名者和用户并行运行 BS N 次]; D --> E[签名者选择随机会话 J]; E --> F[用户打开除 J 外的承诺]; F --> G{用户是否诚实}; G -- 是 --> H[签名者完成 J 会话并发送 sJ]; G -- 否 --> I[签名者中止]; H --> J[用户导出签名 σJ 并输出 σ]; ``` - **避免增长的切选参数 N 的思路** - **稻草人一：固定切选**：PI - Cut - Choo 的关键思想是确保对于一个并行实例 $i^*$，对手在与签名者的任何交互中都不会作弊。如果将 $N$ 设为常数（例如 $N = 2$），这个论点就会失败。但是，通过保持并行实例的数量 $K$ 不变，我们仍然可以认为在每次签名交互中，以压倒性概率存在一个非作弊实例 $i^*$。然而，PI - Cut - Choo 中提出的归约方法只允许将底层方案 BS 的目标公钥嵌入到与 $K$ 个并行实例对应的公钥 $pk_1, \ldots, pk_K$ 中的一个固定密钥中。一旦这个密钥固定，如果该实例中曾经出现成功作弊，归约就会失败。 - **稻草人二：动态密钥结构（简单方法）**：上述讨论表明，我们需要支持将目标公钥动态嵌入到公钥 $pk_1, \ldots, pk_K$ 中的一个。第一个（简单）想法是在每次交互中使用一组新的公钥 $pk_1, \ldots, pk_K$ 和秘密密钥 $sk_1, \ldots, sk_K$。在 PI - Cut - Choo 中，基础方案 BS 是一个两步方案，其中用户发送给签名者的第一条消息 $c$（挑战）不依赖于公钥。因此，我们对结果方案的归约可以在看到承诺 $\tau_{i,j}$ 和挑战 $c_{i,j}$ 后识别出非作弊实例 $i^*$。基于此观察，签名者可以在收到承诺和挑战后发送将用于当前签名交互的（新）公钥 $pk_1, \ldots, pk_K$。这样，归约就知道在每次签名交互中将目标公钥嵌入到哪个密钥 $pk_{i^*}$ 中。具体做法是，归约首先识别出非作弊实例 $i^*$，然后诚实地采样 $(pki, ski)$（$i \neq i^*$），同时将 $pki^*$ 设置为（目标公钥的重新随机化）。最后，归约可以使用 $ski$ 模拟除 $i^*$ 之外的所有实例，同时在实例 $i^*$ 中使用随机预言机编程。然而，这个方案是不安全的，因为每次交互都使用一组新的密钥，没有任何东西将签名与签名者的实际公钥和秘密密钥联系起来。特别是，无法防止对手（轻易地）创建包含其自己选择的一组密钥的伪造签名。 #### 2. 相关工作 - **标准模型中盲签名构造的不可能结果** - Fischlin 和 Schröder 表明，在某些条件下，不能从非交互式假设构造统计上盲的三步方案。 - Pass 表明，唯一的轮最优盲签名不能基于一类交互式假设。 - Baldimtsi 和 Lysyanskaya 表明，具有唯一秘密密钥和特定结构的方案即使在交互式假设下也无法证明安全。 - **盲签名的构造方法** -