6.2.2 不同群表示中的Diffle-Hellman密钥计算难度¶

• 上一章节中得到的$\mathbb{F}_q$-HNP(DH)的结论与本章得到的关于$\mathbb{F}_p$-HNP(CM)的结论来比是相当弱的。这使得研究人员考虑利用$\mathbb{F}_p$-HNP(CM)的解决方案对Diffie-Hellman密钥交换的比特安全性进行尝试。其中一项研究便是不同群下表现中的Diffle-Hellman利用。

• 在第四章中，我们提到可以考虑用一个更强大的预言机$\mathcal{O}_{G}$，而不是将点$g$"固定"(embedded)到预言机$\mathcal{O}_{G,g}$中。即我们可以将基点$g$作为输入有$\mathcal{O}_G(g,g^a, g^b)=f(g^{ab})$，在本节中我们提出了一个更强大的预言机$\mathcal{O}$，此时我们将群表示$\Phi(G)$作为输入，有$\mathcal{O}(\Phi(G), g, g^a, g^b) = f(\Phi(g^{ab}))$。

框架¶

• 令$\Phi$是$G$上的同态，给定$g,g^a,g^b\in G$可以计算得出$\Phi(g)$，$\Phi(g)^a=\Phi(g^a)$以及$\Phi(g)^b=\Phi(g^b)$，前面的三元组可得Diffie-Hellman密钥$g^{ab}$，后面的三元组可得$\Phi(g)^{ab}$。对于特定的$G$上实现，考虑一个将Diffie-Hellman三元组$(g, g^a, g^b)$和群同态$\Phi$作为输入并输出Diffile-Hellman密钥$\Phi(g)^{ab}$（按照$\Phi$的表现式$\Phi(g), \Phi(g)^a, \Phi(g)^g$）的部分信息的预言机$\mathcal{O}$。请注意，这和从$\mathcal{O}_G$中查询$\mathcal{O}_G(\Phi(g), \Phi(g)^a, \Phi(g)^g)$并不同，因为后者考虑了$G$中的$\Phi(g)^{ab}$，而$\mathcal{O}$考虑在不同的群$G$表示下中$\Phi(g)^{ab}$将会使用不同的乘法表。

• 构建技巧是找到群$G$表示中满足，存在$r\in \mathbb{Z}_p^{*}$以及所以$x\in G$有$\Phi(x) = rx$。如果我们可以使用这样的同构族$\{\Phi^r\}_{r\in \mathbb{Z}_p^*}$，我们便可以简化为选择乘数隐藏数问题：对于任意的$r$对预言机查询$\mathcal{O}(\Phi^r,g,g^a,g^b)=f(\Phi(g^{ab})) = f(rg^{ab})$。为了使用推论6.3中的单比特结论，我们就需要找到这种形式的群同构。

• 椭圆曲线：此框架是由Boneh和Shparlinski针对素数域$\mathbb{F}_q$上的椭圆曲线开发的，其中预言机能够对曲线使用不同的Weierstrass方程 [16]。给定一个短的Weierstrass形式的椭圆方程$W: y^2=x^3+Ax+B$，有曲线$W_\lambda: Y^2 = X^3 + A\lambda^4 X + B\lambda^6$和$W$同构。其中映射$\phi_\lambda: W \rightarrow W_\lambda$为对任意非零$\lambda \in \mathbb{F}_q$，有从$W$上的$P=(x,y)$到$W_\lambda$上的$P_\lambda=(\lambda^2x,\lambda^3y)$。

  即点$S=(s_x, s_y)\in W$在$\phi_\lambda$下像为$\phi_\lambda(S) = (\lambda^2s_x,\lambda^3s_y)$。通过选定的$\lambda$，并已知$\lambda^ds$的一些比特信息，来恢复未知数$s\in\mathbb{F}_p$的问题称为$\mathbb{F}_q\mathrm{-HNP(CM)}^d$ （详见 [16]）。

• 为了解决$\mathbb{F}_q\mathrm{-HNP(CM)}^2$得到密钥$s_x$，如果$t$是$\mathbb{F}_p$下的二次剩余，即存在$\lambda \in \mathbb{F}_q$使得$t=\lambda^2$成立，那么通过同构$\Phi^{\lambda^2}$则可以选择乘数$t$来找到$s_x$。这表明恢复$s_x$的问题当可以选择一半的乘数（假设域的特征值不是2，在Weierstrass方程中是隐含条件）时，可以被简化为$\mathbb{F}_p$-HNP(CM)。对于另一半，例当$t$不是$\mathbb{F}_q$的二次剩余时，我们可以猜测其值（$s_xt$的特定比特）。我们期望有一半的几率能够猜对。此时我们的猜测行为构成一个不可靠的预言机。由于$\mathbb{F}_p$-HNP(CM)的解对于这样的预言机是成立的，即当一些数值不正确时，我们可以用$\mathbb{F}_p$-HNP(Cm)的方式来恢复$s_x$。对于$y$坐标参数也同理，在此模型中我们可以通过一个比特来恢复$s_y$。

• 有一个密钥的坐标轴信息即可恢复完整的密钥点，因为另一个值最多只有三种可能。此外，Shoup的一个结论 [78,定理 7]可以用来确认哪个值才是正确的Diffie-Hellman密钥。

• 这个结论是由Boneh和Shparlinski [16]针对最低有效位函数（使用$\mathbb{F}_p$-HNP(CM)中的结论 [3];[49]中使用了不同的方法）给出的。并由Kiltz [51]注意到它对于每一个比特都成立（使用[46]中$\mathbb{F}_p$-HNP(CM)中的结论）。通过一个等价的$\mathbb{F}_q$-HNP(CM)，对更一般的$\mathbb{F}_p$-MVHNP(CM)进行求解发现，当把$\mathbb{F}_q$设置为其他有限域时，结论依然成立，即对于椭圆曲线扩展域也是成立的。后者在更大的范围内成立，因为我们可以改变域的表现形式，得出下列结论（详见 [34， 节 5.2.2]）。

• 此模型结论可描述为：给定一个有限域上的椭圆曲线红的Diffie-Hellman问题$(P,[a]P, [b]P)$，同时计算曲线下$[ab]P$的短Weierstrass方程的单比特信息与计算曲线下原始表示$[ab]P$一样困难。

• 注意在此模型中，Diffie-Hellman密钥交换的上下文几乎没有起作用，与预言机的交互和给出乘数都只是使用了不同的群同构。因此，这种方法对于群中其他密钥信息更适用。这一观察结论在[29]中被用来证明椭圆曲线和配对函数（pairing-based functions，定义在素数域上的椭圆曲线）的单比特困难性。

• 域扩张：同样的方法也可以用于非素域$\mathbb{F}_{p^m}$。考虑$\mathbb{F}_{p}$中的第$i$个分量单位比特（$1\le i \le m$）。在此情况下我们很容易重新描述该问题。定义$\mathbf{r} = (r_1,\cdots, r_m)\in \mathbb{F}_p^m$以及$1\le i \le m$。找到同构$\Phi^r: \mathbb{F}_{p^m} \rightarrow \mathbb{F}_{p^m}$使得$(\Phi^{i}(x))_i = \sum_{j=1}^{m}{r_jx_j}$。也就是说，$\Phi^r$下像的第$i$个分量为$\mathbf{x}=(x_1,\cdots,x_m)$和$\mathbf{r}$的点积。此时问题简化为$\mathbb{F}_p$-MVHNP(CM)。

• 一个特例是$\mathbf{r} = (0,\cdots,0,r_i,0,\cdots, 0)$，这样便变成了$\mathbb{F}_p$-HNP(CM),因此我们能够恢复$s_i$，即密钥$\mathbf{s}$的第i个分量。如前一章所述，这些问题中恢复其中一个分量和恢复整个密钥一样困难。这种方法在 [30, 94]中被用于域多项式。对于每个$i$都给出确定的同构，$i=1$除外（$i=1$的情况在$\mathbb{F}_{p^2}$有明确处理方式）。关于这些解决方案的细节可参考 [34, 节 5.2]。

• 我们使用这个方法和常规$\mathbf{r}=(r_1,\cdots,r_m)$来扩展这个模型的结论，我们给出任何$\mathbf{r}$在域中的正规基的同构，对任意$1\le i \le m$都作为一个抽象向量空间。我们还发现在多项式表示中，当$i=1$时，所有$\mathbf{r}$的属性$\Phi^\mathbf{r}$都不能成立。如上所述，这些结论对于域中的更多类密钥值也是成立的。

• 此模型中的结论解释如下：在一个有限域$\mathbb{F}_{p^m}$下表示的Diffie-Hellman问题，给定$(g,g^a,g^b)$，同时计算域的（不可忽略的）不同（特定）表示中$g^{ab}$的单比特，与计算原始$\mathbb{F}_{p^m}$下$g^{ab}$一样困难。

• 命题 6.6：令$s=g^{ab}$为$\mathbb{F}_{p^m}$下的Dieffie-Hellman密钥。给定$g,g^a,g^b\in \mathbb{F}_{p^m}$，在一个向量空间或$\mathbb{F}_{p^m}$下正规基中计算$s$中的单个比特，对于从$\Phi^{\mathbf{r}}$诱导表示和直接计算$s$一样困难。

• 证明：令$\mathbf{s} = (s_1,\cdots,s_m)$，$s_i\in\mathbb{F}_p$，假设有一个预言机能够获取$\Phi^{\mathbf{r}}(s)$中第$j$个分量的一个比特。设$\mathbf{\lambda} = (\lambda_1,\cdots,\lambda_m)\in\mathbb{F}_p^m$，我们需要在有限域表示中构造一个同构$\Phi^{\lambda}:\mathbb{F}_{p^m}\rightarrow\mathbb{F}_{p^m}$使得$\Phi^{\mathbf{\lambda}}(s)$的第$j$个分量具有$(\Phi^\mathbf{\lambda}(s))_j=\lambda_1s_1+\cdots+\lambda_ms_m$的形式。然后从$\mathbb{F}_p$-MVHNP(CM)的解法中得出结论，我们简要的谈论一下这个合适的同构的几种例子。

• 正规向量空间$\mathbb{F}_p^m$：令$B_1={v1,\cdots,v_m},B_2={u_1,\cdots,u_m}$为$\mathbb{F}_p^m$的两个基，元素$s=s_1v_1+\cdots+s_mv_m$的映射$\Phi^{\mathbf{\lambda}}$可表示为

  $$\Phi^{\mathbf{\lambda}}(s) = (*)u_1+\cdots+(\lambda_1s_1+\lambda_2s_2+\cdots+\lambda_ms_m)u_j+\cdots+(\star)u_m$$

  考虑将线性映射看作一个矩阵，我们很容易看见矩阵的第$j$行应该是$(\lambda_1,\lambda_2,\cdots,\lambda_m)$。为了让这个矩阵变成满秩映射（因此它是同构的），它不应该为奇异的，我们可以很容易来构造这样一个线性映射。

• 正规基：令$B_1={\alpha,\alpha^p,\cdots,\alpha^{p^{m-1}}},B_2={\beta,\beta^p,\cdots,\beta^{p^{m-1}}}$为$\mathbb{F}_{p^m}$中的两个正规基，，元素$s=s_1v_1+\cdots+s_mv_m$的映射$\Phi^{\mathbf{\lambda}}$可表示为

  $$\Phi^{\mathbf{\lambda}}(s) = (*)\beta+\cdots+(\lambda_1s_1+\lambda_2s_2+\cdots+\lambda_ms_m)\beta^{p^{j-1}}+\cdots+(\star)\beta^{p^{m-1}}\tag{6.1}$$

  考虑线性映射$\Phi^{\mathbf{\lambda}}(\alpha)=\lambda_j\beta+\lambda_{j-1}\beta^{p}+\cdots+\lambda_{j+1}\beta^{p^{m-1}}$（$\lambda_k$的下标为模$m$后的结果，$1\le k\le m$，例$\lambda_0 = \lambda_m,\lambda_{m+1}=\lambda_1$）。有

  $$\begin{aligned} \Phi^{\mathbf{\lambda}}(s) =& \Phi^{\mathbf{\lambda}}(s_1\alpha+\cdots+s_m\alpha^{p^{m-1}}) = s_1\Phi^{\mathbf{\lambda}}(\alpha) + s_2\Phi^{\mathbf{\lambda}}(\alpha)^{p}+\cdots+s_m\Phi^{\mathbf{\lambda}}(\alpha)^{p^{m-1}}\\ =&s_1(\lambda_j\beta+\lambda_{j-1}\beta^{p}+\cdots+\lambda_{j+1}\beta^{p^{m-1}})\\ &+s_2(\lambda_j\beta+\lambda_{j-1}\beta^{p}+\cdots+\lambda_{j+1}\beta^{p^{m-1}})^{p}+\cdots\\ &+s_m(\lambda_j\beta+\lambda_{j-1}\beta^{p}+\cdots+\lambda_{j+1}\beta^{p^{m-1}})^{p^{m-1}}\\ =&s_1(\lambda_j\beta+\lambda_{j-1}\beta^{p}+\cdots+\lambda_{j+1}\beta^{p^{m-1}})\\ &+s_2(\lambda_j\beta^p+\lambda_{j-1}\beta^{p^2}+\cdots+\lambda_{j+1}\beta)+\cdots\\ &+s_m(\lambda_j\beta^{p^{m-1}}+\lambda_{j-1}\beta+\cdots+\lambda_{j+1}\beta^{p^{m-2}})\\ \end{aligned}$$

  其中最后一个等式由$\beta^{p^{m}}=\beta$的正规基得出，在收集了每个$\beta^{p^{k}}$（其中$0\le k\le m-1$）后便可以得到$(6.1)$。为了让$\Phi^{\mathbf{\lambda}}$变成一个同构，我们需要检查$\Phi^{\mathbf{\lambda}}(\alpha)^{p^m} = \Phi^{\mathbf{\lambda}}(\alpha)$和集合$\{\Phi^{\mathbf{\lambda}}(\alpha),\Phi^{\mathbf{\lambda}}(\alpha)^p,\dots,\Phi^{\mathbf{\lambda}}(\alpha)^{p^{m-1}}\}$线性无关。这很显然：前者属性来自$\beta^{p^{m}}=\beta$，而后者则来自基$B_2$的线性独立集。

• 接下来我们处理多项式表示的情况，并表明它的限制性更强。

• 多项式基：给定多项式$a=a_mx^{m-1}+\cdot+a_2x+a_1$，同构$\Phi^{\mathbf{\lambda}}$为

  $$\Phi^{\mathbf{\lambda}} = (*)x^{m-1}+\cdots+(\lambda_1a_1+\lambda_2a_2+\cdots+\lambda_ma_m)x^{j-1}+\cdots+(\star)x^0$$

  对于多项式常数$1=0\cdot x^{m-1}+\cdots+0\cdot x+1$，可以得到多项式$\Phi^{\mathbf{\lambda}}(1)$下$x^{j-1}$的系数为$\lambda_1$，例$\Phi^{\mathbf{\lambda}}(1) = \lambda_1x^{j-1}+\dots$。因此同构是将单位元映射至单位元，由此可见如果$j\not = 1$，则$\lambda_1 = 0$，并且如果$j = 1$，则$\lambda_1 = 1$。因此，当使用多项式表示时，我们不能为密钥$s_1$选择乘数，因此无法使用$\mathbb{F}_p$-MVHNP(CM)的解决方案恢复密钥$s_1$。但仍然可以尝试使用$\mathbb{F}_p$-MVHNP(CM)的解决方案来恢复一些或全部的其他系数。

• 注释 6.7：在[96]中，对超椭圆曲线（Diffie-Hellman密钥交换发生在曲线的除子类群中）采取了这种方法，其中考虑了不同的Mumford表示。研究表明，在这个模型中，计算秘钥的任何组成部分的一个比特与计算整个组成部分一样难。没有给出一个完整的证明，证明人们可以用它来恢复整个密钥。

• 这种强模型不适合用来证明素数域中Diffie-Hellman密钥交换结论，因为它有唯一的表示法。在第9章中，我们考虑一个较弱的模型——我们假设决策性的Diffie-Hellman假设成立——可以证明Diffie-Hellman密钥的单个比特的安全性。