前言
继续做论文阅读笔记, 这篇是关于安全性证明的, 安全性证明一般是云数据安全论文的最硬核的部分, 不过一般也有固定模式, 所以有必要彻底搞懂一篇论文的安全性证明过程.
上一篇笔记见
RO-CP-ABE方案系统
安全模型
证明方案可以抵抗用户合谋攻击, 定义敌手可询问2种密钥:
- 已撤销用户的私钥
- 未撤销用户的私钥
(就是撤销用户和未撤销用户的合谋攻击, 可以相互通信私钥
证明
概念定义
f
(
S
,
(
M
,
ρ
)
)
f(S, (M, \rho))
f(S,(M,ρ)) 函数是描述属性集是否符合访问结构
f
(
S
,
(
M
,
ρ
)
)
=
1
f(S, (M, \rho)) = 1
f(S,(M,ρ))=1 表示属性集满足访问结构,
≠
1
\neq 1
=1 表示不满足
1 初始化
A
\mathcal{A}
A选择挑战属性Type-I和挑战访问结构
(
M
∗
,
ρ
∗
)
(M^*, \rho^*)
(M∗,ρ∗)发送给
B
\mathcal{B}
B
2 系统建立
B
\mathcal{B}
B运行AASetup, DSMSetup得到PK, MSK, DPK, DSK.
B
\mathcal{B}
B更新关联属性
a
t
t
∗
att^*
att∗的密钥对
D
P
K
‾
,
D
S
K
‾
\overline{DPK}, \overline{DSK}
DPK,DSK发送给
A
\mathcal{A}
A.
(
B
\mathcal{B}
B看作是扮演AA和DSM的角色, 给恶意用户
A
\mathcal{A}
A提供服务.
3 询问阶段 1
分两种私钥询问, 注意对比
(1) Type-I私钥询问
<
u
I
,
S
I
>
<u_I, S_I>
<uI,SI>: 用户
u
I
u_I
uI属性集
S
I
S_I
SI满足访问结构
(
M
∗
,
ρ
∗
)
(M^*, \rho^*)
(M∗,ρ∗), 但属性
a
t
t
∗
att^*
att∗已被撤销.
B
\mathcal{B}
B运行AAKeyGen, DSMKeyGen, 得到
R
K
I
,
S
K
I
,
K
E
K
I
RK_I, SK_I, KEK_I
RKI,SKI,KEKI并发送给
A
\mathcal{A}
A
(2) Type-II私钥询问
<
u
I
I
,
S
I
I
>
<u_{II}, S_{II}>
<uII,SII>: 用户
u
I
I
u_{II}
uII属性集
S
I
I
S_{II}
SII不满足访问结构
(
M
∗
,
ρ
∗
)
(M^*, \rho^*)
(M∗,ρ∗), 但拥有属性
a
t
t
∗
att^*
att∗.
B
\mathcal{B}
B运行AAKeyGen, DSMKeyGen, 得到
R
K
I
I
,
S
K
I
I
,
K
E
K
I
I
RK_{II}, SK_{II}, KEK_{II}
RKII,SKII,KEKII并发送给
A
\mathcal{A}
A
(可以看成有两类用户可供
A
\mathcal{A}
A进行私钥询问, 第一类Type-I, 是满足访问结构但是属性已经撤销的, 第二类Type-II, 是不满足访问结构, 但是属性集里还有挑战属性
a
t
t
∗
att^*
att∗的, 需要理解属性撤销对象是对单个用户而言的, 撤销用户P的属性, 不会影响用户Q的属性.
4 挑战阶段
A
\mathcal{A}
A给
B
\mathcal{B}
B发送2个等长消息
m
0
,
m
1
m_0, m_1
m0,m1.
B
\mathcal{B}
B选择随机值
b
∈
{
0
,
1
}
b \in \{0, 1\}
b∈{0,1}, 运行Encrypt, DSMEncrypt得到密文头
H
d
r
∗
Hdr^*
Hdr∗, 最终密文
C
T
b
∗
CT_b^*
CTb∗发送给
A
\mathcal{A}
A
5 询问阶段 2
同询问阶段 1,
A
\mathcal{A}
A做两种私钥询问
6 猜测阶段
A
\mathcal{A}
A输出
b
′
∈
{
0
,
1
}
b' \in \{0, 1\}
b′∈{0,1}. 如果
b
′
=
b
b' = b
b′=b 则
A
\mathcal{A}
A攻破方案. 攻破方案的优势定义为
A
d
v
A
=
∣
P
r
[
b
′
=
b
]
−
1
2
∣
Adv_{\mathcal{A}} = |Pr[b' = b] - \frac{1}{2}|
AdvA=∣Pr[b′=b]−21∣
安全性证明
定理
若CDH假设在群G中成立, 则没有多项式时间敌手能够攻破RO-CP-ABE方案, 挑战矩阵设为 M ∗ ( l ∗ × n ∗ ) M^*(l^* \times n^*) M∗(l∗×n∗)
CDH假设
给定三元组
(
g
,
g
a
,
g
b
)
∈
G
3
(g, g^a, g^b) \in G^3
(g,ga,gb)∈G3, 其中
a
,
b
∈
Z
p
∗
a,b \in Z_p^*
a,b∈Zp∗且未知, 要求计算
g
a
b
g^{ab}
gab的值. 设敌手
A
\mathcal{A}
A成功计算出
g
a
b
g^{ab}
gab的概率是
A
d
v
A
C
D
H
=
∣
P
r
[
A
(
g
a
,
g
b
)
=
g
a
b
]
∣
≤
ε
Adv_A^{CDH} = | Pr[\Alpha(g^a, g^b) = g^{ab}] | \leq \varepsilon
AdvACDH=∣Pr[A(ga,gb)=gab]∣≤ε. 如果
ε
\varepsilon
ε是可忽略的, 则称CDH问题是
ε
−
\varepsilon-
ε−困难的.
证明
A \mathcal{A} A进行 q I q_I qI次Type-I询问, q I I q_{II} qII次Type-II询问, 攻破方案的优势不可忽略为 ε = A d v A \varepsilon = Adv_{\mathcal{A}} ε=AdvA. 则可以构造一个 B \mathcal{B} B能够以不可忽略优势 A d v B = ε q I q I I Adv_{\mathcal{B}} = \frac{\varepsilon}{q_I q_{II}} AdvB=qIqIIε攻破CDH假设. (反证法, 先设定CDH假设成立, 如果 A \mathcal{A} A能轻易攻破方案, 若证明 B \mathcal{B} B也能轻易攻破CDH假设, 则推出矛盾, 所以就完成证明, 即 A \mathcal{A} A不能轻易攻破方案.
初始化
A
\mathcal{A}
A选择挑战属性
a
t
t
x
∗
att_x^*
attx∗和挑战访问结构
(
M
∗
,
ρ
∗
)
(M^*, \rho^*)
(M∗,ρ∗)发送给
B
\mathcal{B}
B, 若
a
t
t
x
∗
∉
S
att_x^* \notin S
attx∗∈/S, 则一定有S不满足访问结构
(
M
∗
,
ρ
∗
)
(M^*, \rho^*)
(M∗,ρ∗),
f
(
S
,
(
M
,
ρ
)
)
≠
1
f(S, (M, \rho)) \neq 1
f(S,(M,ρ))=1. 同时挑战者
A
\mathcal{A}
A把
A
=
g
z
1
,
B
=
g
z
2
A = g^{z_1}, B = g^{z_2}
A=gz1,B=gz2发送给仿真者
B
\mathcal{B}
B.
系统建立
B
\mathcal{B}
B生成阶为素数p的循环群
G
,
G
T
G, G_T
G,GT, g是G的生成元, 选取随机数
α
,
a
∈
Z
p
,
h
1
,
h
2
,
.
.
.
,
h
n
∈
G
\alpha, a \in Z_p, h_1, h_2, ..., h_n \in G
α,a∈Zp,h1,h2,...,hn∈G. 则系统的主私钥 MSK =
g
α
g^\alpha
gα, 系统公钥 MPK =
(
g
,
e
(
g
,
g
)
α
,
g
a
,
h
1
,
h
2
,
.
.
.
,
h
n
)
(g, e(g, g)^\alpha, g^a, h_1, h_2, ..., h_n)
(g,e(g,g)α,ga,h1,h2,...,hn).
B
\mathcal{B}
B为每一个
a
t
t
i
att_i
atti选择一个随机指数
t
i
∈
Z
p
t_i \in Z_p
ti∈Zp计算
T
i
=
g
t
i
T_i = g^{t_i}
Ti=gti. (
1
≤
i
≤
n
,
i
≠
x
1 \leq i \leq n, i \neq x
1≤i≤n,i=x)
对挑战属性
a
t
t
∗
att^*
att∗, 随机选择
t
x
∗
∈
Z
p
t_x^* \in Z_p
tx∗∈Zp, 计算
T
x
∗
=
g
t
x
∗
T_x^* = g^{t^*_x}
Tx∗=gtx∗.
输出的DSM的公钥, 主私钥分别为
D
P
K
=
{
T
i
∣
1
≤
i
≤
n
,
i
≠
x
}
∪
{
T
x
∗
}
DPK = \{T_i | 1 \leq i \leq n, i \neq x\} \cup \{T_x^*\}
DPK={Ti∣1≤i≤n,i=x}∪{Tx∗}
D
S
K
=
{
t
i
∣
1
≤
i
≤
n
,
i
≠
x
}
∪
{
t
x
∗
}
DSK = \{t_i | 1 \leq i \leq n, i \neq x\} \cup \{t_x^*\}
DSK={ti∣1≤i≤n,i=x}∪{tx∗}
设定理论值
t
x
∗
‾
=
z
1
t
x
∗
\overline{t^*_x} = z_1 t^*_x
tx∗=z1tx∗,
B
\mathcal{B}
B实际是不知道
z
1
z_1
z1, 所以这是一个理论值计算不出来. (但有用
B
\mathcal{B}
B更新
a
t
t
x
∗
att_x^*
attx∗的密钥对
T
x
∗
‾
=
(
T
x
∗
)
z
1
=
A
t
x
∗
\overline{T_x^*} = (T_x^*)^{z_1} = A^{t_x^*}
Tx∗=(Tx∗)z1=Atx∗, 更新DSM的公钥和主私钥
D
P
K
‾
=
{
T
i
∣
1
≤
i
≤
n
,
i
≠
x
}
∪
{
T
x
∗
‾
}
\overline{DPK} = \{T_i | 1 \leq i \leq n, i \neq x\} \cup \{\overline{T_x^*}\}
DPK={Ti∣1≤i≤n,i=x}∪{Tx∗}
D
S
K
‾
=
{
t
i
∣
1
≤
i
≤
n
,
i
≠
x
}
∪
{
t
x
∗
‾
}
\overline{DSK} = \{t_i | 1 \leq i \leq n, i \neq x\} \cup \{\overline{t_x^*}\}
DSK={ti∣1≤i≤n,i=x}∪{tx∗}
询问阶段 1
B
\mathcal{B}
B设置2个列表
L
I
L_I
LI和
L
I
I
L_{II}
LII, 并初始化2个列表为空.
(1) Type-I私钥询问
<
u
I
,
S
I
>
<u_I, S_I>
<uI,SI>:
用户
u
I
u_I
uI属性集
S
I
S_I
SI满足访问结构
(
M
∗
,
ρ
∗
)
(M^*, \rho^*)
(M∗,ρ∗), 但属性
a
t
t
∗
att^*
att∗已被撤销.
B
\mathcal{B}
B分两种情况处理, 检查列表
L
I
L_I
LI里是否有
u
I
u_I
uI用户:
- 有, 则将{ R K I , S K I , K E K S I RK_I, SK_I, KEK_{S_I} RKI,SKI,KEKSI}发送给 A \mathcal{A} A
- 无, 则执行
- 随机选择 r 1 , λ ∈ Z p r_1, \lambda \in Z_p r1,λ∈Zp, 计算 K = g α λ B a r I λ = g ( α + a z 2 r I ) λ , L = B r I λ = g z 2 r I λ K = g^{\alpha \lambda}B^{ar_I\lambda} = g^{(\alpha + az_2r_I)\lambda}, L = B^{r_I\lambda} = g^{z_2r_I\lambda} K=gαλBarIλ=g(α+az2rI)λ,L=BrIλ=gz2rIλ.
- 对于 a t t i ∈ S I , i ≠ x att_i \in S_I, i \neq x atti∈SI,i=x, 计算 K i = h i r I λ , k e k i = T i r I λ K_i = h_i^{r_I\lambda}, kek_i = T_i^{r_I\lambda} Ki=hirIλ,keki=TirIλ, φ i = P a t h ( u I ) ∩ M i n c s ( G i ) \varphi_i = Path(u_I) \cap Mincs(G_i) φi=Path(uI)∩Mincs(Gi), K E K i = ( k e k i ) 1 θ j = g t i r i d λ θ j KEK_i = (kek_i)^{\frac{1}{\theta_j}} = g^{\frac{t_i r_{id} \lambda}{\theta_j}} KEKi=(keki)θj1=gθjtiridλ.
- 对于 a t t x ∗ att_x^* attx∗, 计算 K x ∗ = h x z 2 r I λ = B z 2 r I λ , k e k x ∗ = ( T x ∗ ) z 2 r I λ = B t x ∗ r I λ K_x^* = h_x^{z_2r_I\lambda} = B^{z_2r_I\lambda}, kek_x^* = (T_x^*)^{z_2r_I\lambda} = B^{t_x^*r_I\lambda} Kx∗=hxz2rIλ=Bz2rIλ,kekx∗=(Tx∗)z2rIλ=Btx∗rIλ, 然后随机选择 θ ∗ ∈ P a t h ( u I ) \theta^* \in Path(u_I) θ∗∈Path(uI)计算 K E K x ∗ = ( k e k x ∗ ) 1 θ ∗ = B t x ∗ r I λ θ ∗ KEK_x^* = (kek_x^*)^{\frac{1}{\theta^*}} = B^{\frac{t_x^*r_I\lambda}{\theta^*}} KEKx∗=(kekx∗)θ∗1=Bθ∗tx∗rIλ.
- 令 R K I = λ , S K I = ( K , L , K x ∗ , K i ) , a t t i ∈ S I , i ≠ x , K E K S I = ( { a t t x ∗ , v j ∗ , k e k x ∗ , K E K x ∗ } , { a t t i , v j , k e k i , K E K i } ) , i ≠ x RK_I = \lambda, SK_I = (K, L, K_x^*, {K_i}), att_i \in S_I, i \neq x, KEK_{S_I} = (\{att_x^*, v_j^*, kek_x^*, KEK_x^*\}, \{att_i, v_j, kek_i, KEK_i\}), i \neq x RKI=λ,SKI=(K,L,Kx∗,Ki),atti∈SI,i=x,KEKSI=({attx∗,vj∗,kekx∗,KEKx∗},{atti,vj,keki,KEKi}),i=x.
- 在 L I L_I LI中添加{ u I , r I , K E K S I , S K I , R K I u_I, r_I, KEK_{S_I}, SK_I, RK_I uI,rI,KEKSI,SKI,RKI}, 最后将{ R K I , S K I , K E K S I RK_I, SK_I, KEK_{S_I} RKI,SKI,KEKSI}并发送给 A \mathcal{A} A
(2) Type-II私钥询问
<
u
I
I
,
S
I
I
>
<u_{II}, S_{II}>
<uII,SII>:
用户
u
I
I
u_{II}
uII属性集
S
I
I
S_{II}
SII不满足访问结构
(
M
∗
,
ρ
∗
)
(M^*, \rho^*)
(M∗,ρ∗), 但拥有属性
a
t
t
x
∗
att_x^*
attx∗.
B
\mathcal{B}
B将
{
R
K
I
I
,
S
K
I
I
,
K
E
K
S
I
I
}
\{RK_{II}, SK_{II}, KEK_{S_{II}}\}
{RKII,SKII,KEKSII}并发送给
A
\mathcal{A}
A
B
\mathcal{B}
B分两种情况处理, 检查列表
L
I
I
L_{II}
LII里是否有
u
I
I
u_{II}
uII用户:
- 有, 则将 { R K I I , S K I I , K E K S I I } \{RK_{II}, SK_{II}, KEK_{S_{II}}\} {RKII,SKII,KEKSII}发送给 A \mathcal{A} A
- 无, 则执行
- 随机选择 r I I , λ ∈ Z p r_{II}, \lambda \in Z_p rII,λ∈Zp, 计算 K = g ( α + a r I I ) λ , L = g r I I λ K = g^{(\alpha + ar_{II})\lambda}, L = g^{r_{II}\lambda} K=g(α+arII)λ,L=grIIλ.
- 对于 a t t i ∈ S I I , i ≠ x att_i \in S_{II}, i \neq x atti∈SII,i=x, 计算 K i = h i r I I λ , k e k i = T i r I I λ K_i = h_i^{r_{II}\lambda}, kek_i = T_i^{r_{II}\lambda} Ki=hirIIλ,keki=TirIIλ, φ i = P a t h ( u I I ) ∩ M i n c s ( G i ) \varphi_i = Path(u_{II}) \cap Mincs(G_i) φi=Path(uII)∩Mincs(Gi), K E K i = ( k e k i ) 1 θ j = g t i r i d λ θ j KEK_i = (kek_i)^{\frac{1}{\theta_j}} = g^{\frac{t_i r_{id} \lambda}{\theta_j}} KEKi=(keki)θj1=gθjtiridλ.
- 对于 a t t x ∗ att_x^* attx∗, 计算 K x ∗ = h x r I I λ , k e k x ∗ = ( T x ∗ ‾ ) r I I λ = A t x ∗ r I I λ K_x^* = h_x^{r_{II}\lambda}, kek_x^* = (\overline{T_x^*})^{r_{II}\lambda} = A^{t_x^*r_{II}\lambda} Kx∗=hxrIIλ,kekx∗=(Tx∗)rIIλ=Atx∗rIIλ, φ i ∗ = P a t h ( u I I ) ∩ M i n c s ( G x ) \varphi_i^* = Path(u_{II}) \cap Mincs(G_x) φi∗=Path(uII)∩Mincs(Gx), 然后随机选择 θ j ∗ ∈ φ x ∗ \theta_j ^* \in \varphi^*_x θj∗∈φx∗, 计算 K E K x ∗ = ( k e k x ∗ ) 1 θ j ∗ = A t x ∗ r I I λ θ j ∗ KEK_x^* = (kek_x^*)^{\frac{1}{\theta_j^*}} = A^{\frac{t_x^*r_{II}\lambda}{\theta_j^*}} KEKx∗=(kekx∗)θj∗1=Aθj∗tx∗rIIλ.
- 令 R K I I = λ , S K I I = ( K , L , { K i } a t t i ∈ S I I ) , K E K S I I = ( { a t t x ∗ , v j ∗ , k e k x ∗ , K E K x ∗ } , { a t t i , v j , k e k i , K E K i } ) , i ≠ x RK_{II} = \lambda, SK_{II} = (K, L, \{K_i\}_{att_i \in S_{II}}), KEK_{S_{II}} = (\{att_x^*, v_j^*, kek_x^*, KEK_x^*\}, \{att_i, v_j, kek_i, KEK_i\}), i \neq x RKII=λ,SKII=(K,L,{Ki}atti∈SII),KEKSII=({attx∗,vj∗,kekx∗,KEKx∗},{atti,vj,keki,KEKi}),i=x.
- 在 L I I L_{II} LII中添加{ u I I , r I I , K E K S I I , S K I I , R K I I u_{II}, r_{II}, KEK_{S_{II}}, SK_{II}, RK_{II} uII,rII,KEKSII,SKII,RKII}, 最后将{ R K I I , S K I I , K E K S I I RK_{II}, SK_{II}, KEK_{S_{II}} RKII,SKII,KEKSII}并发送给 A \mathcal{A} A.
挑战阶段
A
\mathcal{A}
A给
B
\mathcal{B}
B发送2个等长消息
m
0
,
m
1
m_0, m_1
m0,m1.
B
\mathcal{B}
B选择随机值
b
∈
{
0
,
1
}
b \in \{0, 1\}
b∈{0,1}, 运行Encrypt, DSMEncrypt得到密文头
H
d
r
∗
Hdr^*
Hdr∗, 最终密文
C
T
b
∗
CT_b^*
CTb∗发送给
A
\mathcal{A}
A.
选择随机向量
v
=
(
s
,
y
2
,
y
3
,
.
.
.
,
y
n
)
∈
Z
p
n
v = (s, y_2, y_3, ..., y_n) \in Z_p^n
v=(s,y2,y3,...,yn)∈Zpn 用于共享加密指数s.
计算
λ
i
=
M
i
∗
v
\lambda_i = M_i^* v
λi=Mi∗v,
M
i
∗
M_i^*
Mi∗是
M
∗
M^*
M∗的第
i
i
i行分量. 计算每一个
1
≤
i
≤
l
1 \leq i \leq l
1≤i≤l.
C
=
m
b
e
(
g
,
g
)
α
s
C = m_be(g, g)^{\alpha s}
C=mbe(g,g)αs
C
′
=
g
s
C' = g^s
C′=gs
C
i
=
g
a
λ
i
h
ρ
(
i
)
−
s
,
1
≤
i
≤
l
C_i = g^{a\lambda_i}h^{-s}_{\rho(i)}, 1 \leq i \leq l
Ci=gaλihρ(i)−s,1≤i≤l
对于
a
t
t
i
∈
(
M
∗
,
ρ
∗
)
,
i
≠
x
att_i \in (M^*, \rho^*), i\neq x
atti∈(M∗,ρ∗),i=x,
B
\mathcal{B}
B随机选择
k
i
∈
Z
p
k_i \in Z_p
ki∈Zp, 计算
{
C
i
∗
=
g
a
λ
i
h
ρ
(
i
)
−
s
g
k
i
}
,
1
≤
i
≤
l
∗
,
i
≠
x
\{C_i^* = g^{a\lambda_i}h^{-s}_{\rho(i)}g^{k_i}\}, 1 \leq i \leq l^*, i \neq x
{Ci∗=gaλihρ(i)−sgki},1≤i≤l∗,i=x.
对于
a
t
t
x
∗
∈
(
M
∗
,
ρ
∗
)
att_x^* \in (M^*, \rho^*)
attx∗∈(M∗,ρ∗), 计算
C
x
∗
=
g
a
λ
x
h
ρ
(
x
)
−
s
g
k
x
∗
=
g
a
λ
x
h
ρ
(
x
)
−
s
A
k
x
,
(
k
x
∗
=
z
1
k
x
)
C_x^* = g^{a\lambda_x}h^{-s}_{\rho(x)}g^{k_x^*} = g^{a\lambda_x}h^{-s}_{\rho(x)}A^{k_x}, (k^*_x = z_1k_x)
Cx∗=gaλxhρ(x)−sgkx∗=gaλxhρ(x)−sAkx,(kx∗=z1kx).
B
\mathcal{B}
B计算最终密文
C
T
b
∗
=
(
C
,
C
′
,
C
x
∗
,
C
i
∗
)
,
1
≤
i
≤
l
∗
,
i
≠
x
CT_b^* = (C, C', C_x^*, {C_i^*}), 1 \leq i \leq l^*, i \neq x
CTb∗=(C,C′,Cx∗,Ci∗),1≤i≤l∗,i=x.
对于
a
t
t
i
∈
(
M
∗
,
ρ
∗
)
att_i \in (M^*, \rho^*)
atti∈(M∗,ρ∗), 执行Mincs(G_i), 计算密文头
H
d
r
∗
=
{
{
v
j
,
E
(
k
i
)
=
g
k
i
θ
j
t
i
}
,
v
j
∈
M
i
n
c
s
(
G
i
)
,
1
≤
i
≤
l
,
i
≠
x
{
v
j
∗
,
E
(
k
x
∗
)
=
g
k
x
θ
j
∗
t
x
∗
}
,
v
j
∗
∈
M
i
n
c
s
(
G
x
)
Hdr^* = \begin{cases} \{v_j, E(k_i) = g^{\frac{k_i \theta_j}{t_i}}\},\quad v_{j} \in Mincs(G_i), 1 \leq i \leq l, i \neq x \\[2ex] \{v^*_j, E(k_x^*) = g^{\frac{k_x \theta_j^*}{t_x^*}}\}, \quad v^*_j \in Mincs(G_x) \end{cases}
Hdr∗=⎩⎪⎨⎪⎧{vj,E(ki)=gtikiθj},vj∈Mincs(Gi),1≤i≤l,i=x{vj∗,E(kx∗)=gtx∗kxθj∗},vj∗∈Mincs(Gx)
最后
B
\mathcal{B}
B将
(
C
T
b
∗
,
H
d
r
∗
)
(CT_b^*, Hdr^*)
(CTb∗,Hdr∗)发送给
A
\mathcal{A}
A
询问阶段 2
同询问阶段 1,
A
\mathcal{A}
A做两种私钥询问.
猜测阶段
A
\mathcal{A}
A输出
b
′
∈
{
0
,
1
}
b' \in \{0, 1\}
b′∈{0,1}. 如果
b
′
=
b
b' = b
b′=b. 攻破方案的优势为
A
d
v
A
=
∣
P
r
[
b
′
=
b
]
−
1
2
∣
=
ε
Adv_{\mathcal{A}} = |Pr[b' = b] - \frac{1}{2}| = \varepsilon
AdvA=∣Pr[b′=b]−21∣=ε.
仿真者
B
\mathcal{B}
B从
L
I
L_I
LI,
L
I
I
L_{II}
LII中选择{
u
I
,
r
I
,
K
E
K
S
I
,
S
K
I
,
R
K
I
u_I, r_I, KEK_{S_I}, SK_I, RK_I
uI,rI,KEKSI,SKI,RKI}, {
u
I
I
,
r
I
I
,
K
E
K
S
I
I
,
S
K
I
I
,
R
K
I
I
u_{II}, r_{II}, KEK_{S_{II}}, SK_{II}, RK_{II}
uII,rII,KEKSII,SKII,RKII}发送给
A
\mathcal{A}
A, 作为私钥问询.
对于
a
t
t
x
∗
att_x^*
attx∗, 存在
L
I
L_I
LI中的{
S
K
I
,
R
K
I
SK_I, RK_I
SKI,RKI}和
L
I
I
L_{II}
LII中{
K
E
K
S
I
I
,
R
K
I
I
KEK_{S_{II}}, RK_{II}
KEKSII,RKII}结合, 使得下式成立, 进而可以计算
g
z
1
z
2
g^{z_1z_2}
gz1z2. (破解CDH假设的目的就是给定三元组
(
g
,
g
a
,
g
b
)
∈
G
3
(g, g^a, g^b) \in G^3
(g,ga,gb)∈G3, 其中
a
,
b
∈
Z
p
∗
a,b \in Z_p^*
a,b∈Zp∗且未知, 要求计算
g
a
b
g^{ab}
gab的值. 这里证明过程就是设定了
A
=
g
z
1
,
B
=
g
z
2
A = g^{z_1}, B = g^{z_2}
A=gz1,B=gz2, 求
g
z
1
z
2
g^{z_1z_2}
gz1z2.
(
e
(
L
,
C
x
∗
)
e
(
K
x
∗
,
C
′
)
)
1
R
K
I
(
e
(
K
E
K
x
∗
,
E
(
k
x
∗
)
)
)
1
R
K
I
I
=
e
(
B
r
I
,
g
a
λ
x
h
ρ
(
x
)
−
s
A
k
x
)
e
(
B
e
x
r
I
,
g
s
)
e
(
A
t
x
∗
r
I
I
θ
j
∗
,
B
k
x
θ
j
∗
t
x
∗
)
=
e
(
B
r
I
,
g
a
λ
x
A
k
x
)
e
(
B
r
I
,
g
−
e
x
s
)
e
(
B
e
x
r
I
,
g
s
)
e
(
A
r
I
I
,
g
k
x
)
=
e
(
B
r
I
,
g
a
λ
x
)
e
(
B
r
I
,
A
k
x
)
e
(
A
r
I
I
,
g
k
x
)
=
e
(
B
r
I
,
g
a
λ
x
)
\frac{(e(L, C_x^*)e(K_x^*, C'))^{\frac{1}{RK_I}}}{(e(KEK_x^*, E(k_x^*)))^{\frac{1}{RK_{II}}}} = \\ \! \\ \frac{e(B^{r_I}, g^{a\lambda_x h^{-s}_{\rho(x)}A^{k_x}})e(B^{e_xr_I}, g^s)}{e(A^{\frac{t_x^*r_{II}}{\theta_j^*}}, B^{\frac{k_x\theta^*_j}{t_x^*}})} = \\ \! \\ \frac{e(B^{r_I}, g^{a\lambda_x}A^{k_x})e(B^{r_I}, g^{-e_xs})e(B^{e_xr_I}, g^s)}{e(A^{r_{II}}, g^{k_x})} = \\ \! \\ \frac{e(B^{r_I}, g^{a\lambda_x})e(B^{r_I}, A^{k_x})}{e(A^{r_{II}}, g^{k_x})} = \\ \! \\ e(B^{r_I}, g^{a\lambda_x})
(e(KEKx∗,E(kx∗)))RKII1(e(L,Cx∗)e(Kx∗,C′))RKI1=e(Aθj∗tx∗rII,Btx∗kxθj∗)e(BrI,gaλxhρ(x)−sAkx)e(BexrI,gs)=e(ArII,gkx)e(BrI,gaλxAkx)e(BrI,g−exs)e(BexrI,gs)=e(ArII,gkx)e(BrI,gaλx)e(BrI,Akx)=e(BrI,gaλx)
上式成立的充分必要条件是
A
r
I
I
=
g
z
1
z
2
r
I
A^{r_{II}} = g^{z_1z_2r_I}
ArII=gz1z2rI. 则
B
\mathcal{B}
B计算
g
z
1
z
2
=
A
r
I
I
r
I
=
(
K
E
K
x
∗
)
θ
j
∗
r
I
t
x
∗
R
K
I
I
,
K
E
K
x
∗
∈
K
E
K
S
I
I
.
g^{z_1z_2} = A^{\frac{r_{II}}{r_I}} = (KEK_x^*)^{\frac{\theta_j^*}{r_It_x^*RK_{II}}}, \quad KEK_x^* \in KEK_{S_{II}}.
gz1z2=ArIrII=(KEKx∗)rItx∗RKIIθj∗,KEKx∗∈KEKSII.
假设
A
\mathcal{A}
A攻破方案总共进行了
q
I
q_I
qI次Type-I询问,
q
I
I
q_{II}
qII次Type-II询问, 则
B
\mathcal{B}
B从{
u
I
,
r
I
,
K
E
K
S
I
,
S
K
I
,
R
K
I
u_I, r_I, KEK_{S_I}, SK_I, RK_I
uI,rI,KEKSI,SKI,RKI}, {
u
I
I
,
r
I
I
,
K
E
K
S
I
I
,
S
K
I
I
,
R
K
I
I
u_{II}, r_{II}, KEK_{S_{II}}, SK_{II}, RK_{II}
uII,rII,KEKSII,SKII,RKII}选择正确的概率是
1
q
I
q
I
I
\frac{1}{q_I q_{II}}
qIqII1. 所以
B
\mathcal{B}
B攻破CDH假设的优势为
A
d
v
B
=
ε
q
I
q
I
I
Adv_{\mathcal{B}} = \frac{\varepsilon}{q_I q_{II}}
AdvB=qIqIIε. 所以
B
\mathcal{B}
B仍有不可忽略优势攻破CDH假设, 与前提CDH假设成立不符, 所以
A
\mathcal{A}
A没有不可忽略优势攻破方案, 则方案安全性得证.