线性哈希函数的阈值和多重签名方案

# 线性哈希函数的阈值和多重签名方案 ## 1. 阈值签名方案概述 阈值签名方案在密码学中具有重要地位，FROST1 及其更高效版本 FROST2 属于（部分）非交互式阈值签名方案。下面将详细介绍其语法、安全性以及基于线性哈希函数（LHF）转换得到的新方案。 ### 1.1 语法定义 对于具有 n 个签名者和阈值 t 的（部分）非交互式阈值签名方案，它是由一组高效（随机化）算法 TS = (Setup, KeyGen, SPP, LPP, LR, PS, Agg, Vf) 组成，各算法的功能如下： - **Setup(1κ)**：初始化每个签名者 i 的状态 sti 和领导者的状态 st0，并返回系统参数 par。 - **KeyGen()**：返回公共验证密钥 pk、公共辅助信息 aux 以及每个签名者 i 的秘密密钥 ski。 - **签名协议**： - **预处理阶段**：签名者 i 运行 SPP(sti) 生成预处理令牌 pp 并发送给领导者，领导者运行 LPP(i, pp, st0) 更新其状态。 - **签名阶段**：对于大小为 t 的签名者集合 SS 和消息 m，领导者运行 LR(m, SS, st0) 生成领导者请求 lr 并发送给 SS 中的每个签名者 i，签名者 i 运行 PS(lr, i, sti) 生成部分签名 psigi，最后领导者运行 Agg({psigi}i∈SS) 计算消息 m 的签名 σ。具体实验表示如下： ```plaintext (ppi, sti) ← SPP() , st0 ← LPP(i, ppi, st0) , for each i ∈ SS , (lr, st0) ← LR(m, SS, st0) , (psigi, sti) ← PS(lr, i, sti) , for each i ∈ SS , σ ← Agg({psigi}i∈SS) . ``` - **Vf(pk, m, σ)**：验证算法，输出一个比特位，表示 σ 对于 pk 和 m 是否有效。若对于任意 SS ⊆ [n] 和任意 m ∈ {0, 1}*，Pr[Vf(pk, m, σ)] = 1，则称 TS 是（完美）正确的。 ### 1.2 安全性定义 阈值签名的安全概念有一个层次结构，这里主要关注 TS - SUF - 2 和 TS - SUF - 3，分别由 FROST2 和 FROST1 实现。 - **TS - SUF - 2**：存在一个高效的强验证算法 SVf，对于每个 (pk, lr)，最多存在一个签名 σ 使得 SVf(pk, lr, σ) = 1。敌手只有在收到至少 t - |CS| 个诚实方针对同一领导者请求 lr（lr.msg = m 且 SVf(pk, lr, σ) = 1）的部分签名时，才能为 m 生成有效签名 σ，其中 CS 表示被破坏的签名者集合。 - **TS - SUF - 3**：仅适用于 lr 额外指定一个函数 lr.PP 的方案，该函数将 lr.SS 中的每个 i 映射到签名者 i 生成的预处理令牌。敌手除了满足 TS - SUF - 2 的条件外，还需收到每个诚实签名者 i 针对 lr 诚实生成的 lr.PP(i) 的部分签名，才能为 m 生成有效签名 σ。 ### 1.3 新方案介绍 从 FROST1 和 FROST2 转换得到的协议 FROST1 - H 和 FROST2 - H，除了一般转换外，还需选择一个注入函数 x(·) : [n] → S，相应的拉格朗日系数为 λSi := ∏j∈S\{i} xj / (xi - xj)。通过从 Dkey ⊆ D 中采样密钥份额并将哈希范围设置为 Shash ⊆ S 来优化方案。 在 AOMPR 假设下，FROST2 - H 在随机预言模型中是 TS - SUF - 2 安全的，FROST1 - H 是 TS - SUF - 3 安全的，具体定理如下： - **定理 3**：对于任何最多向 PPO 进行 qs 次查询、向 RO 进行 qh 次查询的 TS - SUF - 2 敌手 A，存在一个 AOMPR 敌手 B，其最多向 Chal 进行 2qs + t 次查询，运行时间约为 A 的两倍，使得 Advts - suf - 2FROST2 - H[LHF](A, κ) ≤ √(q · (AdvaomprLHF(B, κ) + (3q²)/2κ))，其中 q = qh + qs + 1。 - **定理 4**：对于任何最多向 PPO 进行 qs 次查询、向 RO 进行 qh 次查询的 TS - SUF - 3 敌手 A，存在一个 AOMPR 敌手 B，其最多向 Chal 进行 2qs + t 次查询，运行时间约为 A 的两倍，使得 Advts - suf - 3FROST1 - H[LHF](A, κ) ≤ 4n · q · √(AdvaomprLHF(B, κ) + 6q/2κ)，其中 q = qh + qs + 1。 ## 2. 方案的具体实现 ### 2.1 基于离散对数问题的实现 #### 2.1.1 离散对数问题 离散对数问题通过 DLog 游戏形式化定义，群生成算法 GGen(1κ) 输出 (G, p, g)