3.1
算法描述
● Setup. 针对安全参数
\begin{document}$\lambda $\end{document}
和加密允许的最大用户数量m , 首先以安全参数为输入生成非对称双线群
\begin{document}$BP = \left( {{G_1},}\right. \left.{{G_2},{G_T}, e, p} \right)$\end{document}
, 其中
\begin{document}$ p > {2^\lambda } $\end{document}
, 并随机选取循环群
\begin{document}$ {G_1}, {G_2} $\end{document}
的生成元
\begin{document}$ g, h $\end{document}
, 随机数
\begin{document}$ \alpha \in Z_p^* $\end{document}
, 3个密码函数
\begin{document}${H_1}:{\left\{ {0, 1} \right\}^*} \times Z_p^* \to Z_p^*$\end{document}
,
\begin{document}$ {H_2}:{G_2} \to Z_p^* $\end{document}
和
\begin{document}$ {H_3}:{G_1} \times {G_2} \times {G_T} \times {\left( {Z_p^*} \right)^2} \to {\left\{ {0, 1} \right\}^\ell } $\end{document}
, 其中
\begin{document}$ \ell $\end{document}
为消息的长度(封装密钥长度). 计算
\begin{document}${P_{\rm pub}} = \left( {{g^\alpha }, {g^{{\alpha ^2}}}, \ldots ,}\right. \left. {{g^{{\alpha^{m + 1}}}}} \right)$\end{document}
,
\begin{document}$ u = {h^{{\alpha ^2}}} $\end{document}
,
\begin{document}$ v = e{\left( {g, h} \right)^\alpha } $\end{document}
. 最后, 选择适当的密钥生成函数识别符
\begin{document}$ hid $\end{document}
, 系统的主公钥
\begin{document}$ mpk $\end{document}
和主私钥
\begin{document}$ msk $\end{document}
为:
\begin{document}$ mpk = \left( {BP, g, {P_{\rm pub}}, u, v, {H_1}, {H_2}, {H_3}, hid, \ell } \right), msk = \left( {\alpha , h} \right) . $ \end{document}
● KeyGen. 已知标识
\begin{document}$ID \in {\{ 0, 1\} ^ * }$\end{document}
, KGC计算用户的解密密钥:
\begin{document}$ s{k_{ID}} = {h^{\tfrac{\alpha }{{\alpha + {H_1}\left( {ID||hid, p} \right)}}}}. $ \end{document}
● Encrypt. 给定标识集合
\begin{document}$S = \left( {I{D_1}, I{D_2}, \ldots , I{D_n}} \right)\left( {n \leqslant m} \right)$\end{document}
, 选取随机数
\begin{document}$r \in Z_p^ * $\end{document}
, 计算:
\begin{document}$ w = {v^r}, \quad {C_1} = {u^{ - r}}, \quad {C_2} = {g^{r \cdot \left( {\alpha + {H_2}\left( {{C_1}} \right)} \right) \cdot \prod\nolimits_{i = 1}^n {\left( {\alpha + {H_1}(I{D_i}||hid, p)} \right)} }} , $ \end{document}
\begin{document}$ \tau = \prod\nolimits_{i = 1}^n {{H_1}(I{D_i}||hid, p)} \bmod p, \quad K = {H_3}\left( {{C_1}, {C_2}, w, \tau , \ell } \right), $ \end{document}
输出三元组
\begin{document}$\left( {{C_1}, {C_2}, K} \right)$\end{document}
, 其中
\begin{document}$\left( {{C_1}, {C_2}} \right)$\end{document}
为封装密文, K 为封装的加密密钥.
● Decrypt. 为恢复封装密文
\begin{document}$\left( {{C_1}, {C_2}, S} \right)$\end{document}
中的加密密钥K , 用户
\begin{document}$I{D_i} \in S$\end{document}
以密钥
\begin{document}$s{k_{I{D_i}}}$\end{document}
为输入, 首先验证公式(1)是否成立:
1
\begin{document}$ e\left( {{C_2}, {u^{ - 1}}} \right) = e\left( {{g^{\left( {\alpha + {H_2}\left( {{C_1}} \right)} \right) \cdot \prod\nolimits_{j = 1}^n {\left( {\alpha + {H_1}(I{D_i}||hid, p)} \right)} }}, {C_1}} \right) $ \end{document}
若公式(1)不成立, 表示该密文是无效的密文, 则停止并退出算法, 输出解密失败符号“
\begin{document}$\perp$\end{document}
”. 若公式(1)成立, 接着计算:
\begin{document}$ w' = {\left( {e\left( {{g^{{f_{i, S}}(\alpha )}}, {C_1}} \right) \cdot e\left( {{C_2}, s{k_{I{D_i}}}} \right)} \right)^{^{\tfrac{1}{{{H_2}({C_1}) \cdot \prod\nolimits_{j = 1, j \ne i}^n {{H_1}(I{D_j}||hid, p)} }}}}} , $ \end{document}
其中,
\begin{document}$ {f_{i, S}}(\alpha ) = \frac{1}{\alpha } \cdot \left( {\left( {\alpha + {H_2}({C_1})} \right)\prod\limits_{j = 1, j \ne i}^n {\left( {\alpha + {H_1}\left( {I{D_j}||hid, p} \right)} \right)} - {H_2}({C_1}) \cdot \prod\limits_{j = 1, j \ne i}^n {{H_1}} \left( {I{D_j}||hid, p} \right)} \right). $ \end{document}
最后, 计算
\begin{document}$ \tau ' = \prod\nolimits_{I{D_i} \in S} {{H_1}(I{D_i}||hid, p)} \bmod p $\end{document}
. 若
\begin{document}$K' = {H_3}\left( {{C_1}, {C_2}, w', \tau ', \ell } \right)$\end{document}
为全0比特串, 则报错并结束算法, 否则输出
\begin{document}$K'$\end{document}
作为封装密钥.
3.3
安全性分析
定理1 . 令上述方案中的密码函数
\begin{document}${H_1}$\end{document}
,
\begin{document}${H_2}$\end{document}
为随机谕言器. 如果
\begin{document}$ \left( {q, m + 1, f, g} \right) $\end{document}
-GDDHE假设成立, 则方案满足IND-sID-CCA的安全性.
证明: 假定存在多项式时间攻击算法
\begin{document}$\mathcal{A}$\end{document}
在IND-sID-CCA安全模型中能以不可忽略的优势
\begin{document}$ \epsilon $\end{document}
攻破方案, 则可以构造一个模拟算法
\begin{document}$\mathcal{B}$\end{document}
以不可忽略的优势解决
\begin{document}$\left( {q, m + 1, f, g} \right) $\end{document}
-GDDHE问题. 设询问随机谕言器
\begin{document}${H_1}$\end{document}
和
\begin{document}${H_2}$\end{document}
的总次数为
\begin{document}$ q $\end{document}
, 攻击算法
\begin{document}$\mathcal{A}$\end{document}
和模拟算法
\begin{document}$\mathcal{B}$\end{document}
都以
\begin{document}$m$\end{document}
,
\begin{document}$q$\end{document}
为输入, 且
\begin{document}$\mathcal{B}$\end{document}
额外输入一个
\begin{document}$\left( {q, m + 1, f, g} \right)$\end{document}
-GDDHE问题实例:
\begin{document}$ I = \left( {\begin{array}{*{20}{l}} {h_0^a, {\text{ }}h_0^{{a^2}}, \ldots , {\text{ }}h_0^{{a^q}}, \qquad h_0^{{a^2}f(a)}, {\text{ }}h_0^{r{a^2}f(a)}, } \\ {{g_0}, {\text{ }}g_0^a, {\text{ }}g_0^{{a^2}}, \ldots , {\text{ }}g_0^{{a^{2m + 2}}}, \qquad \qquad g_0^{rg(a)}, } \end{array}} \right) $ \end{document}
和元素T , 其中
\begin{document}$T \in {G_T}$\end{document}
, 且
\begin{document}$T = {\left( {{g_0}, {h_0}} \right)^{raf\left( a \right)}}$\end{document}
或是随机群元素. 多项式
\begin{document}$f\left( \textit{z} \right)$\end{document}
和
\begin{document}$g\left( \textit{z} \right)$\end{document}
分别是定义在
\begin{document}$Z_p^ * $\end{document}
中阶为
\begin{document}$q$\end{document}
和
\begin{document}$m + 1$\end{document}
的互质多项式. 不妨设
\begin{document}$f\left( \textit{z} \right)$\end{document}
的
\begin{document}$q$\end{document}
个不同根为
\begin{document}${x_1}, {x_2}, \ldots , {x_q}, g\left( \textit{z} \right)$\end{document}
的
\begin{document}$m + 1$\end{document}
个不同根为
\begin{document}${x_{q + 1}}, {x_{q + 2}}, \ldots , {x_{q + m + 1}}$\end{document}
, 则
\begin{document}${x_1}, \ldots , {x_{q + m + 1}}$\end{document}
各不相同. 定义
\begin{document}$f\left( \textit{z} \right)$\end{document}
和
\begin{document}$g\left( \textit{z} \right)$\end{document}
为:
\begin{document}$ f(\textit{z}) = \prod\limits_{i = 1}^q {(\textit{z} + {x_i})} = \sum\limits_{i = 0}^q {{b_i}{\textit{z}^i}} , \quad g(\textit{z}) = \prod\limits_{i = q + 1}^{q + m + 1} {(\textit{z} + {x_i})} , $ \end{document}
其中,
\begin{document}$ {b_i} $\end{document}
为多项式
\begin{document}$ f\left( \textit{z} \right) $\end{document}
的系数, 是可求的. 对任意的
\begin{document}$i \in \left[ {1, q} \right]$\end{document}
, 定义
\begin{document}${f_i}\left( \textit{z} \right) = \dfrac{{f\left( \textit{z} \right)}}{{\textit{z} + {x_i}}} = \displaystyle\sum\limits_{j = 0}^{q - 1} {{d_{i, j}}} {\textit{z}^j}$\end{document}
,
\begin{document}$ {d_{i, j}} $\end{document}
为多项式
\begin{document}$ {f_i}\left(\textit{z} \right) $\end{document}
的系数, 是可求的. 对任意的
\begin{document}$i \in \left[ {q + 1, q + m + 1} \right]$\end{document}
, 定义
\begin{document}${g_i}\left( \textit{z} \right) = \dfrac{{g\left( \textit{z} \right)}}{{\textit{z} + {x_i}}}$\end{document}
, 则
\begin{document}${f_i}\left(\textit{z} \right)$\end{document}
的次数为
\begin{document}$q - 1$\end{document}
,
\begin{document}${g_i}\left( \textit{z} \right)$\end{document}
的次数为
\begin{document}$m$\end{document}
.
● 初始化.
\begin{document}$\mathcal{A}$\end{document}
输出一个挑战标识集合
\begin{document}${S^*} = \left( {ID_1^*, ID_2^*, \ldots , ID_{{s^*}}^*} \right)\left( {{s^*} \leqslant m} \right)$\end{document}
.
● 系统建立.
\begin{document}$\mathcal{B}$\end{document}
根据如下方式生成系统主公钥. 首先隐式的令
\begin{document}$\alpha = a$\end{document}
,
\begin{document}$h = h_0^{f\left( a \right)}$\end{document}
, 并设挑战密文的
\begin{document}$C_1^*$\end{document}
部分为
\begin{document}$C_1^* = h_0^{ - r{a^2}f\left( a \right)}$\end{document}
. 接着, 设
\begin{document}$u = h_0^{{a^2}f\left( a \right)} = {h^{{a^2}}}$\end{document}
, 定义多项式
\begin{document}$\displaystyle\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {\left( {a + {x_i}} \right)} = \displaystyle\sum\limits_{i = 0}^{m - {s^*}} {{c_i}} {a^i}$\end{document}
, 其中
\begin{document}$ {c_i} $\end{document}
为多项式系数. 计算:
\begin{document}$ g = {\prod\limits_{i = 0}^{m - {s^*}} {\left( {g_0^{{a^i}}} \right)} ^{{c_i}}} = g_0^{\sum\limits_{i = 0}^{m - {s^*}} {{c_i}} {a^i}} = g_0^{\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {\left( {a + {x_i}} \right)} }, $ \end{document}
\begin{document}$ {g^{{\alpha ^j}}} = {\prod\limits_{i = 0}^{m - {s^*}} {\left( {g_0^{{a^{i + j}}}} \right)} ^{{c_i}}} = g_0^{{a^j} \cdot \prod\nolimits_{i = q + {s^*} + 1}^{q + m} {\left( {a + {x_i}} \right)} }, j = 1, 2, \ldots , m, $ \end{document}
\begin{document}$ v = e\left( {g_0^{\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {\left( {a + {x_i}} \right)} }, h_0^{a{b_0}}} \right)e\left( {g_0^{a\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {\left( {a + {x_i}} \right)} }, h_0^{\sum\limits_{i = 1}^q {{b_i}{a^i}} }} \right) = e\left( {g_0^{a\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {\left( {a + {x_i}} \right)} }, h_0^{f\left( a \right)}} \right) = e{\left( {g, h} \right)^\alpha }. $ \end{document}
在给定困难问题实例中,
\begin{document}$ g_0^{{a^i}} $\end{document}
是已知的, 又
\begin{document}$ {c_i} $\end{document}
是可计算的多项式系数. 因此
\begin{document}$g, {g^{{\alpha ^j}}}$\end{document}
是可计算的. 虽然
\begin{document}$ {h_0} $\end{document}
是未知的,
\begin{document}$h = h_0^{f\left( a \right)}$\end{document}
也是未知的, 但
\begin{document}$ v $\end{document}
可利用双线性对的性质, 通过输入的困难问题实例计算得到.
\begin{document}$u$\end{document}
可直接从困问题实例获得. 最后
\begin{document}$\mathcal{B}$\end{document}
选择密钥生成函数识别符
\begin{document}$hid$\end{document}
, 密码函数
\begin{document}${H_3}:{G_1} \times {G_2} \times {G_T} \times {\left( {Z_p^*} \right)^2} \to {\left\{ {0, 1} \right\}^\ell }$\end{document}
, 输出系统主公钥:
\begin{document}$ mpk = \left( {g, u, v, \ell , {H_3}, hid, \{ {g^{{a^j}}}\} _{j = 1}^m} \right), $ \end{document}
其中,
\begin{document}${H_1}, {H_2}$\end{document}
被看成是由模拟算法
\begin{document}$\mathcal{B}$\end{document}
控制的随机谕言器. 为方便描述, 下文省略
\begin{document}$hid$\end{document}
和
\begin{document}$p$\end{document}
的输入.
● 哈希询问.
\begin{document}$\mathcal{A}$\end{document}
在任何时候可询问谕言器
\begin{document}${H_1}$\end{document}
和
\begin{document}${H_2}$\end{document}
.
(1)
\begin{document}${H_1}$\end{document}
-询问. 已知标识
\begin{document}$I{D_i}$\end{document}
, 不妨设
\begin{document}${H_1}$\end{document}
询问的次数为
\begin{document}${q_1}$\end{document}
. 为回复询问,
\begin{document}$\mathcal{B}$\end{document}
首先建立列表
\begin{document}${\mathcal{L}_1}$\end{document}
, 列表中元素的初始状态为:
\begin{document}$ {\left\{ ( \bot , {x_i})\right\} _{i \in [1, {q_1}]}}, \quad {\left\{ (I{D_i}, {x_i})\right\} _{i \in [q + 1, q + {s^*}]}} , $ \end{document}
其中, “
\begin{document}$ \perp$\end{document}
”代表空,
\begin{document}$\left( {I{D_{q + 1}}, I{D_{q + 2}}, \ldots , I{D_{q + {s^*}}}} \right){\text{ = }}\left( {ID_1^*, ID_2^*, \ldots , ID_{{s^*}}^*} \right)$\end{document}
. 当
\begin{document}$\mathcal{A}$\end{document}
询问标识
\begin{document}$I{D_i}$\end{document}
的
\begin{document}${H_1}$\end{document}
值时, 若
\begin{document}$\left( {I{D_i}, {x_i}} \right)$\end{document}
在列表
\begin{document}${\mathcal{L}_1}$\end{document}
中,
\begin{document}$\mathcal{B}$\end{document}
返回
\begin{document}${x_i}$\end{document}
. 否则, 记
\begin{document}$I{D_i}$\end{document}
为第
\begin{document}$i$\end{document}
个新标识, 设
\begin{document}${H_1}\left( {I{D_i}} \right) = {x_i}$\end{document}
, 并返回
\begin{document}${x_i}$\end{document}
.
(2)
\begin{document}${H_2}$\end{document}
-询问. 已知
\begin{document}${C_i}$\end{document}
, 不妨设
\begin{document}${H_2}$\end{document}
询问的次数为
\begin{document}$ {q_2}({q_2} = q - {q_1}) $\end{document}
, 为回复询问,
\begin{document}$\mathcal{B}$\end{document}
首先建立列表
\begin{document}${\mathcal{L}_2}$\end{document}
, 列表中元素的初始状态为:
\begin{document}$ {\{ ( \bot , {y_i})\} _{i \in [1, {q_2}]}} = {\{ ( \bot , {x_i})\} _{i \in [{q_1} + 1, q]}}, \quad \{ (C_1^*, {x_{q + m + 1}})\} , $ \end{document}
其中, “
\begin{document}$\perp$\end{document}
”代表空. 当攻击算法
\begin{document}$\mathcal{A}$\end{document}
询问
\begin{document}${C_i}$\end{document}
的
\begin{document}${H_2}$\end{document}
值时, 若
\begin{document}$\left( {{C_i}, {x_i}} \right)$\end{document}
在列表
\begin{document}${\mathcal{L}_2}$\end{document}
中,
\begin{document}$\mathcal{B}$\end{document}
返回
\begin{document}${y_i}$\end{document}
. 否则, 记
\begin{document}${C_i}$\end{document}
为第
\begin{document}$i$\end{document}
个新询问, 设
\begin{document}${H_2}\left( {{C_i}} \right) = {y_i}$\end{document}
, 并返回
\begin{document}${y_i}$\end{document}
.
● 询问1.
\begin{document}$\mathcal{A}$\end{document}
可以自适应性地询问用户密钥和密文解密.
(1) 密钥询问. 已知标识
\begin{document}$I{D_i} \notin {S^*}$\end{document}
,
\begin{document}$\mathcal{B}$\end{document}
首先检查列表
\begin{document}${\mathcal{L}_1}$\end{document}
获取
\begin{document}${x_i}$\end{document}
(若不存在, 以
\begin{document}$I{D_i}$\end{document}
为输入询问
\begin{document}${H_1}$\end{document}
, 获得
\begin{document}${x_i}$\end{document}
). 接着, 计算:
\begin{document}$ s{k_{I{D_i}}} = {\prod\limits_{j = 0}^{q - 1} {\left( {h_0^{{a^{j + 1}}}} \right)} ^{{d_{i, j}}}} = h_0^{\sum\limits_{j = 0}^{q - 1} {{d_{i, j}}{a^{j + 1}}} } = h_0^{a{f_i}\left( a \right)} = h_0^{\frac{{af\left( a \right)}}{{a + {x_i}}}} = {h^{\frac{a}{{a + {H_1}\left( {I{D_i}} \right)}}}} . $ \end{document}
最后,
\begin{document}$\mathcal{B}$\end{document}
将
\begin{document}$s{k_{I{D_i}}}$\end{document}
发送给
\begin{document}$\mathcal{A}$\end{document}
. 不难看出,
\begin{document}$s{k_{I{D_i}}}$\end{document}
是正确的密钥,
\begin{document}$\mathcal{B}$\end{document}
能通过给定的困难问题实例成功模拟任意标识
\begin{document}$I{D_i} \notin {S^*}$\end{document}
的密钥.
(2) 密文解密询问. 已知解密询问密文
\begin{document}$\left( {{C_1}, {C_2}, S} \right)$\end{document}
, 其中
\begin{document}$S \subseteq {S^*}$\end{document}
,
\begin{document}$\mathcal{B}$\end{document}
首先判断公式(2)是否成立.
2
\begin{document}$ e\left( {{C_2}, {u^{ - 1}}} \right) = e\left( {{g^{\left( {\alpha + {H_2}\left( {{C_1}} \right)} \right) \cdot \prod\nolimits_{I{D_i} \in S}^{} {\left( {\alpha + {H_1}(I{D_i}||hid, p)} \right)} }}, {C_1}} \right) $ \end{document}
若公式(2)不成立, 表示
\begin{document}$\left( {{C_1}, {C_2}, S} \right)$\end{document}
是无效密文, 返回解密失败符号“
\begin{document}$\perp$\end{document}
”. 若公式(2)成立, 则
\begin{document}${C_1} = C_1^*$\end{document}
的概率是可忽略的, 即
\begin{document}${C_1} \ne C_1^*$\end{document}
. 在该情况下, 存在某个
\begin{document}${y_i}$\end{document}
, 满足
\begin{document}${H_2}\left( {{C_1}} \right) = {y_i} = {x_{{q_1} + i}}$\end{document}
(若不存在
\begin{document}${y_i}$\end{document}
, 则以
\begin{document}${C_1}$\end{document}
为输入询问
\begin{document}${H_2}$\end{document}
获取
\begin{document}${y_i}$\end{document}
). 接着, 按密钥询问的步骤计算:
\begin{document}$ \widetilde {s{k_{{C_1}}}} = h_0^{a{f_{{q_1} + i}}(a)} = h_0^{\frac{{af(a)}}{{a + {x_{{q_1} + i}}}}} = {h^{\frac{a}{{a + {H_2}({C_1})}}}} . $ \end{document}
以
\begin{document}$ \left( {\widetilde {s{k_{{C_1}}}}, {C_1}, {C_2}, S} \right) $\end{document}
为输入运行解密算法, 并把解密结果返回给
\begin{document}$\mathcal{A}$\end{document}
. 注意到
\begin{document}$ \widetilde {s{k_{{C_1}}}} $\end{document}
不是正确的解密密钥, 但是, 根据证明设置, 该值能够正确解密密文.
● 挑战. 当
\begin{document}$\mathcal{A}$\end{document}
决定询问阶段1结束后,
\begin{document}$\mathcal{B}$\end{document}
计算:
\begin{document}$C_2^* = g_0^{rg(a)}, {\tau ^*} = \prod\nolimits_{I{D_i} \in {S^*}} {{H_1}(I{D_i})}, {w^*} = {T^{\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {{x_i}} }} \cdot e\left( {g_0^{\frac{1}{a}\left( {\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {(a + {x_i})} - \prod\nolimits_{i = q + {s^*} + 1}^{q + m} {{x_i}} } \right)}, h_0^{r{a^2}f(a)}} \right). $ \end{document}
计算
\begin{document}${K^*} = {H_3}\left( {C_1^*, C_2^*, {w^*}, {\tau ^*}, \ell } \right)$\end{document}
. 接着, 在封装密钥空间
\begin{document}$\mathcal{K}$\end{document}
中选取一个随机密钥K , 随机选取
\begin{document}$c \in \{ 0, 1\} $\end{document}
. 最后, 设
\begin{document}${K_c} = {K^*}, {K_{1 - c}} = K$\end{document}
, 并发送挑战密文
\begin{document}$\left( {C_1^*, C_2^*, {K_0}, {K_1}} \right)$\end{document}
给
\begin{document}$\mathcal{A}$\end{document}
, 其中
\begin{document}$C_1^*$\end{document}
在系统建立阶段已求. 设生成挑战密文所选取的随机数为
\begin{document}${r^*} = r$\end{document}
, 则有:
\begin{document}$\left\{ \begin{split} C_1^* & = h_0^{ - r{a^2}f(a)} = {u^{ - {r^*}}}\\ C_2^* &= g_0^{rg(a)} = g_0^{r \cdot \prod\nolimits_{i = q + 1}^{q + m + 1} {(a + {x_i})} } = g_0^{r \cdot (a + {x_{q + m + 1}}) \cdot \prod\nolimits_{q + {s^*} + 1}^{q + m} {(a + {x_i})} \cdot \prod\nolimits_{i = q + 1}^{q + {s^*}} {(a + {x_i})} } \\ & = {g^{r \cdot (a + {x_{q + m + 1}}) \cdot \prod\nolimits_{i = q + 1}^{q + {s^*}} {(a + {x_i})} }} = {g^{{r^*} \cdot (a + {H_2}(C_1^*)) \cdot \prod\nolimits_{i = 1}^{{s^*}} {(a + {H_1}(ID_i^*))} }} \end{split} \right. . $ \end{document}
若
\begin{document}$T = e{({g_0}, {h_0})^{raf(a)}}$\end{document}
, 有:
\begin{document}$ \begin{aligned}[b] {w^*} &= {T^{\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {{x_i}} }} \cdot e\left( {g_0^{\frac{1}{a}\left( {\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {(a + {x_i})} - \prod\nolimits_{i = q + {s^*} + 1}^{q + m} {{x_i}} } \right)}, h_0^{r{a^2}f(a)}} \right) = {\left( {e{{({g_0}, {h_0})}^{raf(a)}}} \right)^{\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {{x_i}} }} \cdot e\left( {g_0^{\left( {\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {(a + {x_i})} - \prod\nolimits_{i = q + {s^*} + 1}^{q + m} {{x_i}} } \right)}, h_0^{raf(a)}} \right) \\ &= e{\left( {{g_0}, {h_0}} \right)^{raf(a) \cdot \left( {\prod\nolimits_{i = q + {s^*} + 1}^{q + m} {(a + {x_i})} } \right)}} = {v^{{r^*}}}. \end{aligned} $ \end{document}
因此, 当
\begin{document}$T = e{({g_0}, {h_0})^{raf(a)}}$\end{document}
时, 挑战密文是正确的封装密文.
● 询问2.
\begin{document}$\mathcal{A}$\end{document}
允许继续自适应性地询问用户密钥和密文解密, 但不能询问挑战密文
\begin{document}$\left( {C_1^*, C_2^*} \right)$\end{document}
的解密,
\begin{document}$\mathcal{B}$\end{document}
根据询问1的步骤回复
\begin{document}$\mathcal{A}$\end{document}
.
● 猜测.
\begin{document}$\mathcal{A}$\end{document}
输出对c 的猜测
\begin{document}$c' \in \left\{ {0, 1} \right\}$\end{document}
. 若
\begin{document}$c = c'$\end{document}
,
\begin{document}$\mathcal{B}$\end{document}
输出1, 表示猜测
\begin{document}$T = {({g_0}, {h_0})^{raf(a)}}$\end{document}
. 否则输出0, 表示猜测T 为群
\begin{document}${G_T}$\end{document}
中的随机值.
最后, 分析
\begin{document}$\mathcal{B}$\end{document}
成功解决
\begin{document}$(q, m + 1, f, g)$\end{document}
-GDDHE问题的优势. 从证明的设置可知, 当
\begin{document}$T = e{({g_0}, {h_0})^{raf(a)}}$\end{document}
时, 挑战密文是正确的封装密文, 攻击者
\begin{document}$\mathcal{A}$\end{document}
无法区分是模拟还是真实攻击环境. 在该情况下, 根据假设
\begin{document}$\mathcal{A}$\end{document}
能以不可忽略的优势
\begin{document}$\varepsilon$\end{document}
攻破上述方案, 则有
\begin{document}$ \Pr \left[ {c = c'|T = e{{\left( {{g_0}, {h_0}} \right)}^{raf\left( a \right)}}} \right] = \dfrac{1}{2} + \varepsilon $\end{document}
. 当
\begin{document}$T \ne e{({g_0}, {h_0})^{raf(a)}}$\end{document}
, 为群
\begin{document}${G_T}$\end{document}
中的随机值时,
\begin{document}${w^*}$\end{document}
是随机的, 与
\begin{document}$C_1^*, C_2^*$\end{document}
无关, 挑战密文由一次一密加密得到, 有
\begin{document}$ \Pr \left[ {c = c'|T \ne e{{\left( {{g_0}, {h_0}} \right)}^{raf\left( a \right)}}} \right] = \dfrac{1}{2} $\end{document}
. 综上有:
\begin{document}$ \begin{aligned}[b] Adv(\lambda ) &= \left| {\Pr\left[ {\mathcal{A}\left( {\mathcal{I}, T = e{{\left( {{g_0}, {h_0}} \right)}^{raf(a)}}} \right) = 1} \right] - \Pr\left[ {\mathcal{A}\left( {\mathcal{I}, T \ne e{{\left( {{g_0}, {h_0}} \right)}^{raf(a)}}} \right) = 1} \right)} \right| & \\ & = \left| {\Pr \left[ {c = c'|T = e{{\left( {{g_0}, {h_0}} \right)}^{raf\left( a \right)}}} \right] - \Pr \left[ {c = c'|T \ne e{{\left( {{g_0}, {h_0}} \right)}^{raf\left( a \right)}}} \right]} \right| = \left| {\frac{1}{2} + \varepsilon - \frac{1}{2}} \right| = {\varepsilon} . \end{aligned} $ \end{document}
综上, 若
\begin{document}$\mathcal{A}$\end{document}
能以不可忽略的优势
\begin{document}$ \varepsilon $\end{document}
攻破上述方案, 则
\begin{document}$\mathcal{B}$\end{document}
能以同样的优势
\begin{document}$ \varepsilon $\end{document}
给出
\begin{document}$(q, m + 1, f, g)$\end{document}
-GDDHE问题的正确解.