Page 466 - 《软件学报》2026年第2期

毕昌兵 等: 5G 车联网中基于区块链的半分布式消息认证加密方案 945

C 想解决 ECDLP
证明: 假设挑战者 假设, 其输入是 (ss· P,P), 若他能计算出 ss 作为该问题的解. 则称挑战者 C
可以解决 ECDLP 假设.
τ
初始化阶段: 挑战者 C 输入安全参数 进行系统初始化, 产生系统参数 {p,q,P,P Pub ,H 1 ,H 2 }, 其中 P Pub = ss· P.
挑战者 C 发送系统参数给敌手 A I . 安全模型将哈希函数 H 1 , H 2 看成 RO.
询问阶段: A I 可以自适应地向 C 发起下列询问.
1) H 1 询问: 挑战者 C 维护列表 L 1 , 列表结构为 < Addr,X,Y,P Pub ,α > 且初始化为空. 当敌手 A I 使用元组 < Addr i ,
∗
X i ,Y i ,P Pub > 进行 H 1 询问时, 如果元组已经存在列表 L 1 中, 则返回 ; 否则, C 随机选择 α i ∈ Z , 将 < Addr i ,X i ,Y i ,α i >
α i
q
加入列表 L 1 , 并返回 α i 给 A I .
2) H 2 询问: 挑战者 C 维护列表 L 2 , 列表结构为 < X,Y,L,m,t,β > 且初始化为空. 当敌手 A I 使用元组 < X i ,Y i ,L i ,
∗
m i ,t i > 进行 H 2 询问时, 如果元组已经存在列表 L 2 中, 则返回 ; 否则, C 随机选择 β i ∈ Z , 将 < X i ,Y i ,K i ,m i ,t i > 加入
β i
q
列表 L 2 , 并返回 β 给 A I .
3) 部分私钥询问: 挑战者 C 维护列表 L py , 列表结构为 < Addr, py,Y,c > 且初始为空. 当敌手 A I 使用 Addr i 进行密
1
(
钥提取询问时, 若元组已经存在列表中, 则返回给 A I ; 否则, C 抛掷偏心硬币 c ∈ {0,1} Pr[c = 1] = , Pr[c = 0] =
q 1 +1
q 1
∗
) , 当 c = 1 时, 令 py = ⊥, 返回 ⊥ 给 A I ; 当 c = 0 时, C 随机选择 py i ∈ Z 计算 Y i = py i P−α i P Pub , 将 < Addr i , py i ,Y i >
q 1 +1 q
加入列表 L py , 并返回 < py i ,Y i > 给 A I .
4) 私钥询问: 挑战者 C 维护列表 L SK , 列表结构为 < Addr, x, py > 且初始为空. 当敌手 A I 使用 Addr i 进行私钥提
取询问时, 若元组已经存在列表 L SK 中, 则返回给 A I ; 否则, C 询问列表 L py , 若 c = 1, 则终止; 否则, C 随机选择
∗
x i , py i ∈ Z , 将 < Addr i , x i , py i > 加入列表 L SK , 并返回 < x i , py i > 给 A I .
q
5) 公钥询问: 挑战者 C 维护列表 L PK , 列表结构为 < Addr,X,Y > 且初始为空. 当敌手 A I 使用 Addr i 进行公钥提
,
∗
问时, 若元组已经存在列表 L PK 中, 则返回给 A I ; 否则, C 询问列表 L py , 若 c = 1 C 随机选择 x i ,y i ∈ Z , 计算 X i = x i P
q
和 Y i = y i P, 将 < Addr i ,X i ,Y i ,c > 加入列表 L PK , 并返回给 A I ; 若 c = 0, 运行部分私钥询问, 从 L cy 中获得 < Y i , py i >.
然后, C 随机选择 x i ∈ Z , 将 < Addr i , py i , x i > 和 < Addr i ,X i ,Y i > 分别加入到 L SK 列表和 L PK 列表, 并返回给 A I .
∗
q
′ ′ <Addr i ,X i ,Y i >.
6) 公钥替换询问: 敌手 A I 可以进行公钥替换, 即使用 < Addr i ,X ,Y > 替换
i i
7) 签名询问: 当 A I 使用 < Addr i ,m i > 进行该询问时, C 先在列表 L py 中查询 < Addr i , py i ,Y i ,c >, 若 c = 1, 则终
,
∗
止; 否则 C 在列表 L SK 中查询得到 < Addr i , x i , py i >. 然后 C 选择随机数 l i ∈ Z , 计算 L i = l i P α i = H 1 (Addr i ,X i ,Y i ),
q
−1
,
β i = H 2 (X i ,Y i ,L i ,m i ,t i ) σ i = l (x i + py i +β i ), 返回签名 σ i 给 A I .
′ σ 2 , 若签名伪造成功,
伪造阶段: 经过概率多项式次数询问后, 敌手 A I 成功伪造对 Addr 的两个合法签名 σ 1 和
′ ′ ′ ′
说明等式 σ 1 P = L+β(X +Y )+α 1 βP Pub 和 σ 2 P = L+β(X +Y )+α 2 βP Pub 成立.
根据叉子引理 (forking lemma) [36] , C 可以计算出 ss = (σ 1 −σ 2 )/β(α 1 −α 2 ) 作为 ECDLP 假设的解; 否则, C 没有
解决 ECDLP 假设. 若 A I 对 Addr 进行过部分私钥询问或者私钥询问, 则 C 失败. A I 不进行这种询问的概率至少是
′
2 ∗ 1/q 2 ; 利用预言机重放技术产生两个或
1/q ; 若 A I 对 L 进行过 H 2 询问, 则 C 失败, A I 不进行这种询问的概率大于
1
以上有效签名时, 失败的概率小于 1/9. 因此, 解决 ECDLP 假设的优势为:

2
Adv τ ⩾ 1/9q q 2 .
A I 1
定理 2. 在基于 ECDLP 假设和 ROM 的帮助下, 若敌手 A II 能在概率多项式时间内, 以不可忽略的优势
ε ⩾ 10(q s +1)(q s +q 2 )/2 赢得游戏 2 (假设最多进行 q i 次 H i 询问, q s 次签名询问), 则挑战者 C 能在概率多项式时间
k
1/(9q 1 q 2 ) 解决 ECDLP 假设.
内, 以不可忽略的优势
证明: 假设挑战者 C 想解决 ECDLP 假设, 其输入是 (xx· P,P), 若他能计算出 xx 作为该问题的解. 则称挑战者
C 可以解决 ECDLP 假设.
τ P Pub = ss· P.
初始化阶段: 挑战者 C 输入安全参数 进行系统初始化, 产生系统参数 {p,q,P,P Pub ,H 1 ,H 2 }, 其中
挑战者 C 发送系统参数和 ss 给敌手 A I . 安全模型将哈希函数 H 1 和H 2 看成 RO.