6.2.1 非均匀Diffie-Hellman相关方案的比特安全¶

• $\mathbb{F}_p$-HNP，$\mathbb{F}_p$-MVHNP和$\mathbb{F}_p$-HNP(CM)，$\mathbb{F}_p$-MVHNP(CM)的根本区别是后者给我们提供了更强的结论。在非均匀模型中，我们可以从问题设定中获取到别处无法得到的一些提示(advice)位。使用非均匀模型研究与Diffie-Hellman密钥交换的练习可以追溯到Maurer的工作中 [63]。Boneh和Venkatesan在随后的工作中首次考虑了使用提示位来解决隐藏数问题的不同变体 [18]。使用与密钥$s$无关的提示位，他们能够为输出$2\log\log p$的最高有效位的函数使用均匀独立样本来解决$\mathbb{F}_p$-HNP。Shparlinski和Winterhof [84]修改了这项工作，将结论推广至$\mathbb{F}_p$的某些子群中，当然也需要提供提示位。

• 回顾一下，我们对随机乘数变体的研究源于$\mathbb{F}_q$-HNP(DH)，其对乘数有部分（非常弱的）控制，即我们能够选择$h^x$上的$x$。在这种情况下，实现对乘数的强控制似乎做不到，因为这意味着我们需要解决$\mathbb{F}_q^{*}$中的离散对数问题——这将导致Diffie-Hellman失去安全性。为了将$\mathbb{F}_q$-HNP(DN)减少到其选择的乘数的提示位是以$h$为底的离散对数。回想一下在Diffle-Hellman密钥交换中有$h = g^b$，因此获得$h$的特定离散对数值对于证明Diffle-Hellman的比特安全结论没有任何帮助，因为每一个密钥共享中$g^b$的值都不同，除非考虑静态Diffle-Hellman。因此，Boneh和Venkatesan考虑了当$g^b$是固定值时与Diffle-Hellman相关的方案，特别是他们讨论了ElGamal公钥系统和Okamoto的会议密码共享方案，更多细节参见 [18, 节 3]，关于他们的结论参见定理 3.2。

• 这种方法可以获得更强的结论，基于推论 6.3，以及假设的提示位——以$g^b$为底的离散对数（仅和$p,g$有关，与$s$无关），可以得到一下结论。

  推论 6.5： 给定仅和$p,h$有关的提示位信息，对于任何单比特函数和具有猜测概率的预言机，存在$\mathbb{F}_p$-HNP(DH)的（非适应性）多项式时间解。

• Akavia [1]将此结论用于$\mathbb{F}_p$-HNP(DH)，为ElGamal公钥系统和Okamoto在$\mathbb{Z}_p^*$的会议密钥共享方案提供了单比特结论。关于$\mathbb{F}_{p^m}$-HNP和$\mathbb{F}_p$-MVHNP在第5章中以及解释了，所以对于$\mathbb{F}_{p^m}^*$下的ElGamal公钥系统和Okamoto会议密码共享方案有着相同的结论。

• 我们注意到虽然Boneh和Venkatesan的格方法中作为提示位给出的离散对数的上界为$2\log(p)$（实际上可以取$\log(p)+\log\log(p)+4$），SFT算法（以及推论 6.5中的方案）所需的离散对数更大，但依然是$\log(p)$的线性关系。还应注意当$g$是一个小子群时，还不清楚锁所需的所选乘数是否还在$g$的生成群中（详见 [33，节 6.2]）。