4.3 Diffie-Hellman和隐藏数问题¶

• 在之前的内容中，我们通过RSA和DLP的例子讨论了比特安全的概念，并且很自然的将硬核函数和知名难题联系到一起。因此，扩展我们的定义到基于此类问题原函数产生的密钥的比特安全也是很自然的，CDH的硬核函数以及Diffie-Hellman的比特安全研究之路已经很完善了。

• 考虑一个群$G$和群内元素$g\in G$，给定$g^a, g^b$，那么Diffie-Hellman密钥便是$g^{ab}$。那么预言机便是模拟一个从函数$f$的部分信息中计算得到$f(g^{ab})$的算法，它应该能从公开参数中得到$f(g^{ab})$。形式上，我们定义预言机$\mathcal{O}_{g,G,f}$为$\mathcal{O}_{g,G,f}(g^a, g^b) = f(g^{ab})$。当$g, G, f$是固定的值时，我们可以缩写为$\mathcal{O} = \mathcal{O}_{g,G,f}$。注意这里我们已经对预言机的类型进行了选择，也可以考虑另一种只需要$g$的强预言机$\mathcal{O}_{G,f}$。稍后我们会展示这个预言机的作用，对于大部分情况，我们只需要弱预言机即可。

• 如上述所说，关键是有一种提供Diffie-Hellman密钥$g^{ab}$的代数关系的方法去和预言机进行交互。如果密钥表示为$g^{a+r}, g^b$，那么Diffie-Hellman密钥将是$g^{(a+r)b} = g^{ab}g^{br}$。因此对于任何整数$r$有

  $$\mathcal{O}_{g,G,f}(g^{a+r}, g^b) = f(g^{ab}t)$$

  其中$t = g^{br}$，同时有$r \in [1, |G|]$，所以$g^{a+r}=g^ag^r$以及$t=(g^b)^r$便可以通过计算得出。我们也发现可以通过其他方式和预言机交互，比如相似的指数方法$g^{ar}, g^b$。这些想法在$Boneh$和$Venkatesan$的开创性工作中都有介绍。

  现在我们结合这些想法并且定义Diffie-Hellman中隐藏数问题。

  HNP(DH)：对于一个群$(G,\cdot)$和元素$g\in G, g\in \langle g\rangle$，令$f$为定义在$G$上的函数，以及未知数$s\in G$。从给定的预言机函数$f_s(x) := f(s\cdot h^x)$中恢复$s$。

  这个问题是之前所讨论的内容的抽象概念，其中$s=g^{ab}$和$h=g^b$(在指数情况下，会收到$f(s^x)$)，这和DLP不同的是“隐藏”指数可以是任意群中的一个整数。Diffie-Hellman密钥也是群中的一个元素，所以找到了HNP(DH)的在某个群中的解并不意味着能够在其他群中找到解。HNP(DH)对于一般的隐藏数问题是一个特例。

  HNP：设群$(G,\cdot)$，以及定义在$G$上的函数$f$，令$t_1,\dots,t_d\in G$和未知数$s\in G$。从给定的$d$组$(t_i,f(s\cdot t_i))$中恢复$s$。

  这是一个非常宽泛的定义，以至隐藏数问题可以应用在各种不同的地方。我们先来看几个例子，首先，它不仅仅适用于CDH的比特安全研究，我们也将介绍其在RSA和DLP的应用。它已经被广泛运用于DSA和ECDSA签名中临时密钥（nonce）部分信息泄漏的研究[45, 68, 69]（在[70, 节4.4]也有讨论），同样也被运用在对签名上下文的侧信道攻击研究中[27, 4]（这项工作还给出了椭圆曲线分解的结论）。综合调查[82]中给出了对于隐藏数问题的许多变体和应用。这个问题具有非常大的理论意义，所以对它的研究至今还在延续。

  除了理论意义外，对HNP(DH)的研究还有另外一个作用。在Diffie-Hellman密钥交换协议结束时，双方进行共享一个固定长度的密钥$g^{ab}$。实践中，这个长度需要（至少两倍）大于双方的安全级别，所以他们会在共享密钥上使用一些派生函数。一种显然可行的思路是从$g^{ab}$中选取一些块满足所需的比特长度。因此，需要有一个严格的证明指出计算这样的块不比计算出整个密钥要容易。

• 自随机性（Self-randomisation）：HNP能够使用下面的方法进行自随机化，给定$u\in G$，我们定义一个新的未知数$s^{'} = s\cdot u$和$t^{'} = u\cdot u^{-1}$。然后任意组$(t, f(s\cdot t))$都可以得到$(t^{'}, f(s^{'}\cdot t^{'}))$，其中$f(s^{'}\cdot t^{'})=f(s\cdot t)$。HNP(DH)也可以上类似的方法进行进一步的随机化。可以在[17, 节4.1]中查看细节。我们可以假设对$h$生成的$\langle g\rangle$都能这样随机化。

• RSA和DLP：对于RSA和DLP的比特安全研究目前已经非常广泛并且知名了。它并不是我们研究的主要内容，为了完整期间，我们会描述它们和隐藏数问题的关系。回想对于$RSA_{N,e}(x) := x^e \pmod{N}$，假设一个预言机能够从$x^e$中输出$f(x)$，然后考虑输入$(xt)^e \equiv x^et^e\pmod{N}$到预言机中得到$f(xt)$。同样对于$exp_{g,p}(x) := g^x\pmod{p}$，假设一个预言机能够从$g^x$中输出$f(x)$，那么我们便可以输入$g^{xt} = (g^x)^t$得到$f(xt)$。如果我们能够选择这其中的乘数$t$的话，那么这些问题将简化为HNP中一个非常容易的变体。

• 本论文的余下部分将致力于研究HNP(DH)的变体，我们的主要动机是获取CDH中比特安全的结论。大多数情况下，我们可以得到相同群中HNP的一般性结论，但是椭圆曲线下的HNP(DH)是个特例，我们必须访问预言机。它也是对于HNP(DH)的第一个解法，（弱）控制乘数。我们考虑不同的群，例如有限域下的乘法群、椭圆曲线上的点、代数环面（具有偏群定理）和不同的函数，大部分函数都有不同的最高有效位，但是对于LUC和XTR，最高有效位函数都由追踪(trace)函数组成，这里同样一个特例是对于超奇异同源Diffie-Hellman不是基于DLP的，之后我们会对其定义一个等价问题。