Page 290 - 《软件学报》2021年第11期

3616 Journal of Software 软件学报 Vol.32, No.11, November 2021

ς
束,即 Pr(P′)=(1−δ) ;事件 P″表示挑战阶段未终止,即 Pr(P″)=δ.则游戏未终止的概率至少为 Pr(P∧P′∧P″)=
⎛ ξ ⎞ ς 1 ς 1 ⎛ ξ ⎞ 1
−
)
⎜ 1− k ⎟ (1 δ δ .由于 δ = ,当ς足够大时, (1 δ− ) → ,故 Pr(P ∧ P′ P′ ) ′∧ > ⎜ 1− k ⎟ .
⎝ 2 ⎠ ς + 1 e ⎝ 2 ⎠ e(ς + 1)
1
综上所述,若挑战者ℑ 在整个游戏过程中没有终止,且敌手 以不可忽略的优势ε在多项式时间内赢得相
І
ξ ⎛ ε ⎞
c ()k > 1−
关游戏,则ℑ能以优势 Adv ⎜ k ⎟ 解决 CDH 问题. □
⎝ 2 ⎠ 1)
1 e(ς +
1
定理 6. 本方案具有攻击方式为 2 下的选择密文攻击的保密性,即在随机预言机模型下,敌手 以不可忽
2
略的优势ε赢得定义 2 中的游戏.如果在游戏中,敌手 最多进行ς次签密查询和ξ次私钥生成查询,则挑战者ℑ
1
2
ξ ⎛ ε ⎞
c ()k > 1−
能以不可忽略的优势 Adv ⎜ k ⎟ 解决 CDH 问题.
2 e(ς +
⎝ 2 ⎠ 1)
证明:证明过程同定理 5 类似,这里不再赘述. □
5.2 不可伪造性
2
定理 7. 本方案具有攻击方式为 1 下的选择消息攻击下的不可伪造性,即在随机预言机模型下,敌手 以
І
2
不可忽略的优势ε赢得定义 3 中的游戏.如果在游戏中,敌手 最多进行ς次签名查询,则挑战者ℑ 能以不可忽略
І
ε
u ()k >
的优势 Adv 1 解决 DL 问题(其中,e 为自然对数的底数).
e(ς + 1)
证明:令算法Γ的输入为 DL 问题的挑战实例〈G,aG〉,其中, a ∈ Z ,而且其值未知,算法Γ的目的就是计算出 a
*
p
2
的数值.算法Γ以敌手 为子程序来计算上述问题,并充当定义 3 中挑战者ℑ .首先,挑战者ℑ 执行 Setup 步骤,令
І
ρ
2
P pub =aG,进而得到公共参数 Params = { , , , ,G p q P P pub ,H H H F index , ,||}⊕ ;然后将 Params 发送至敌手 .挑战者
,
,
,
1
І
3
2
ℑ 维护列表 L 1 ,L 2 ,L 3 ,L sk ,L pk ,以跟踪对预言机 H 1 ,H 2 ,H 3 以及私钥生成、公钥生成的询问结果,上述列表初始化
为空.
• 询问阶段
敌手执行定理 1 中对预言机 H 2 ,H 3 以及公钥替换的询问.
2
公钥生成询问:挑战者ℑ 收到敌手 询问用户 ID i 对应的公钥信息时,ℑ 会查询列表 L pk :如果列表 L pk 存在
І
〈
2
元素 ID i ,U′ i ,ν 〉 i ,其中,ν i ∈{0,1},则返回公钥信息 U′ 给敌手 ;否则,ℑ 随机选择ν i ∈{0,1},且设定 Pr[c i =1]=δ,其
І
i
1
*
〈
中, δ = .若ν i =0,挑战者ℑ选取随机数 ,h γ ′∈ Z ,计算得到U′ = γ ′ P P h− .挑战者ℑ 添加 ID ,U′ ,ν 〉 到 L pk 中,
ς + 1 1 i p i i pub 1 i i i
, ′
*
2
并将公钥信息U′ 发送给敌手 ,同时添加 ID〈 i ,γ ′〉 到 L sk 中,添加 ID〈 i ,U h 〉 到 L 1 中.若ν i =1,选取 ,bγ ′ ∈ Z 以及
i
i
І
p
i
1
i
, ′
*
〈
h ∈ Z ,使得 *,γ ′〉 〈 i ∉ L .令U′ = bP ,挑战者ℑ 添加 ID〈 i ,U′ i ,ν 〉 到 L pk 中,添加 ID〈 i ,U h 〉 到 L 1 中,添加 ID i ,γ ′〉 i 到 L sk
i
1
1
sk
p
i
i
中,并返回公钥信息 κ′ U′ = i 给敌手 .
2
І
敌手执行定理 1 中对预言机 H 1 的询问.
私钥生成询问:当挑战者ℑ 收到敌手 询问 ID i 的私钥信息时,若存在 ID〈 i ,γ ′〉∈ L ,则返回 γ ′ 给敌手 ;否
2
2
sk
i
І
І
i
2
则对 ID i 执行公钥生成询问,并从 L sk 返回私钥信息 γ ′ 给敌手 .
І
i
签名询问:当挑战者ℑ 收到敌手 关于 ID ID〈 s , R = {ID 1 R ,ID R 2 ,...,ID R ρ },M = { ,m m 2 ,...m ρ }〉 的签名询问时,挑
2
І
1
战者ℑ 首先从 L pk 中查询 ID s 所对应的〈ID s ,U s ,ν s 〉信息,并执行如下操作:若ν s =1,则ℑ 终止模拟,并退出游戏;若
i
ν s =0,则ℑ 对 ID s 执行私钥生成询问,获取γ s 信息,对 ID (1≤ ≤ ) ρ 执行公钥生成询问,并获取 ID〈 ,U 〉 信息,然
i R i R i R
2
后运行 SignCrypt 算法,获取签名信息,并发送至敌手 .
І
2
签名验证询问:当挑战者ℑ 收到敌手 关于 ID s , ID 和 ID〈 i R ,c i R ,m 〉 的签名验证询问时,挑战者ℑ首先对
i R
i R
І
ID s 执行公钥生成询问,获得〈ID s ,U s ,ν s 〉信息,并根据ν s 的数值进行如下的计算.