重新审视BBS签名：理论与安全分析

### 重新审视BBS签名：理论与安全分析 #### 1. 引言 在密码学领域，签名方案的安全性和效率一直是研究的重点。BBS签名作为一种重要的签名方案，其安全性和性能备受关注。本文将深入探讨BBS签名的相关理论，包括其游戏模型、假设条件、具体实现细节以及安全分析。 #### 2. 游戏模型与假设条件 ##### 2.1 强不可伪造性游戏（Game SUFA） 该游戏用于验证签名方案的强不可伪造性。具体流程如下： ```plaintext S. Tessaro and C. Zhu Game SUFA SSpλq: S Ð ∅, par ←$ SS.Setupp1λq pvk, skq ←$ SS.KGpparq pM ˚, σ˚q ←$ ASignppar, vkq If pM ˚, σ˚q R S ∧SS.Verppar, vk, M ˚, σ˚q then Return true Return false Oracle SignpMq: σ ←$ SS.Signppar, sk, Mq If σ ‰ ⊥then S ∪Ð {pM, σq} Return σ ``` 这个游戏通过模拟签名过程和验证过程，判断是否能够伪造出有效的签名。 ##### 2.2 q - SDH和q - DL假设 - **q - SDH假设（Game q - SDHA）**： ```plaintext Game q - SDHA GGenpλq: par “ pp, G1, G2, GT , eq Ð GGenp1λq g1 ←$ G˚ 1, g2 ←$ G˚ 2 x ←$ Zp pc, Zq ←$ Appar, g1, pgxi 1 qiP[q], g2, gx 2q Return Z “ g1{px`cq 1 ``` - **q - DL假设（Game q - DLA）**： ```plaintext Game q - DLA GGenpλq: par “ pp, G1, G2, GT , eq Ð GGenp1λq g1 ←$ G˚ 1, g2 ←$ G˚ 2 x ←$ Zp x′ ←$ Appar, g1, pgxi 1 qiP[q], g2, gx 2q Return x′ “ x ``` q - SDH假设意味着对于任何q，它蕴含q - DL假设，但反之不一定成立，不过对于代数敌手是成立的。当q等于1时，q - DL假设即为离散对数（DL）假设。 #### 3. BBS签名方案 ##### 3.1 方案描述与实现细节 BBS签名方案是一种具有较短签名长度的方案，形式上表示为BBS = BBS[GGen, De, ℓ]，其中GGen是群参数生成器，De是Zp上的分布，ℓ是消息长度参数。具体算法如下： ```plaintext Algorithm BBS.Setupp1λq : pp, G1, G2, GT , eq Ð GGenp1λq g1 ←$ G˚ 1, h1 ←$ Gℓ 1, g2 ←$ G˚ 2 par Ð pp, g1, h1, g2, G1, G2, GT , eq Return par Algorithm BBS.KGpparq : pp, g1, h1, g2, G1, G2, GT , eq Ð par x ←$ Zp; X2 Ð gx 2 sk Ð x; vk Ð X2 Return psk, vkq Algorithm BBS.Signpsk “ x, mq : C Ð g1  i h1[i]m [i] e ←$ De A Ð C 1 x`e Return σ “ pA, eq Algorithm BBS.Verpvk, m, σ “ pA, eqq : C Ð g1  i h1[i]m [i] Return epA, ge 2vkq “ epC, g2q ``` 该方案的消息空间是BBS.M = Zℓp，并且存在一个小概率事件，即在签名生成过程中计算1 / (x + e) 时可能因为x + e = 0而失败，这里采用1 / 0 = 0的约定。BBS + 方案是BBS方案的一个特殊情况，其中每个签名消息的第一个分量是随机选择的。 ##### 3.2 建模选择 - **消息长度**：通过ℓ固定消息长度，但实际上可以处理无界长度的消息，h1[i]可以是哈希函数的输出。 - **随机性**：BBS方案被建模为随机化的，但可以通过对m或C应用PRF来消除随机性。 #### 4. BBS签名方案的安全分析 ##### 4.1 安全性定理 在标准模型下，当De是Zp上的均匀分布时，BBS签名方案在q - SDH假设下是安全的，其中q是签名者发出的签名查询次数。具体定理如下： 设GGen是群参数生成器，生成阶为p = p(λ)的群。对于每个发出最多q = q(λ)个签名查询的SUF敌手A，存在敌手B1、B2和B3，使得： ```plaintext Advsuf BBS[GGen]pA, λq ď q · Advq - sdh GGenpB1, λq ` Advdl GGenpB2, λq ` Advq - sdh GGenpB3, λq ` q2 2p ` q ` 2 p ``` 敌手B1、B2和B3在证明中明确给出，并且运行时间与A大致相当。 ##### 4.2 具体参数讨论 依赖q - SDH假设引发了关于参数应在多大