4.4 部分信息的类型¶

这里的讨论的内容仅限于“比特”的部分信息，然而在最高有效位的景况中，文献中会给出一些经典函数的代替方案更适合处理模。本节将介绍在后面的节中会使用到的不同的比特模型。

4.4.1 最高有效位¶

在有关Diffie-Hellman密钥的研究中，对最高有效位的研究最多。本文使用了三种类型的最高有效位。
传统比特（Classical Bits）：此时二进制是最自然和最理想的表示，令 $x\in [0, p-1]$ 且 $n := \lfloor \log(p)\rfloor$ ，所以 $x$ 是一个 $(n+1)$ -比特的数。记

$x = \sum_{i=0}^{n}{\varepsilon_i2^i}$

其中 $\varepsilon_i \in {0, 1}$ 。此时记 $x$ 的传统比特的 $k$ -最高有效位 $\mathrm{MSB}_k(x)$ 为序列 $(\varepsilon_n, \dots, \varepsilon_{n-k+1})$ 。有时很方便将其表示为一个 $\mathbb{Z}_p$ 的元素。注意给出 $\mathrm{MSB}_k(x)$ 可以计算得出与 $x$ 最多相差 $2^{n-k}$ 的值 $\sum_{i=n-k+1}^{n}{\varepsilon_i2^i} + 2^{n-k}$ 。

这种定义引出了下列问题，当 $p = 2^n + r$ 对于“较小”的 $r$ 时最高位几乎没有信息，因为我们希望的是 $\mathrm{MSB}_1(x)=0$ 是随机概率而不是确定的。
模比特（Modular Bits）：这种替代方案中每个值出现的可能性是相同的。我们将 $[0, p-1]\subset \mathbb{R}$ 划分为 $2^k$ 个子区间，并将 $k$ -最高有效位与 $x$ 的子区间相关联。更准确地说，定义 $\mathrm{MSMB}_k(x)$ 为对于 ${0,\dots,2^k-1}$ 有

$\mathrm{MSMB}_k(x)\frac{p}{2^k} \le x < (\mathrm{MSMB}_k(x) + 1)\frac{p}{2^k}$

请注意计算 $\lfloor \mathrm{MSMB}_k(x)\frac{p}{2^k} + \frac{p}{2^{k+1}}\rfloor$ 将会得到一个与 $x$ 最多差 $p/2^{k+1}$ 的值。
近似值（Approximation）
一种更宽松的是给出 $x$ 的不确定的近似值。我们将 $x$ 的k-比特近似值记为 $\mathrm{APPR}_x(x)$ ，它对于任意整数 $u$ 有

$|x-u| \le \frac{p}{2^{k+1}}$

与模比特给出的确定性表示相反，近似值可以认为是一种不确定的表示。由于其普适性更高，它经常在文献中被使用。
我们注意到在最后的两个定义中 $k$ 可以不是整数，这里给出了“分数”比特的概率。众所周知，这两个定义与传统比特最多差一位，其实上面已经提到了这一点。因此，当 $k$ 较大时，一位的差距是微不足道的，因为它不会对真正的困难性产生影响。在下文中，对于比较大的 $k$ ，我们很少去关注这些差异。另一方面，在 $k$ 非常小的情况下，这种差距便不能被忽略，参见第9章中对这些差异说明的几个例子。

4.4.2 其他连续位¶

显然关于传统比特的定义可以被扩展到任意比特序列中。对于 $x=\sum_{i=0}^{n}{\varepsilon_i2^i}$ 我们定义 $\mathrm{Bits}_{i,i+j}(x)$ 为序列 $(\varepsilon_{i+j},\dots,\varepsilon_i)$ ，其中 $0\le i\le i+j \le n$ 。特别是对于单个比特 $0\le i\le n$ 我们定义 $\mathrm{Bit}_i(x) = \varepsilon_i$ 。要将这些值表示为 $\mathbb{Z}_p$ 中的元素，可以计算 $a=\sum_{l=0}^{j}{\varepsilon_{i+l}2^{i+l}}$ 或是 $2^ia$ 。它有

$x = 2^{i+j}b+2^ia+c$

其中未知数 $b$ 满足 $0\le b\le \frac{p}{2^{i+j}}$ 且 $0\le c\le 2^j$ 。特别的，我们令 $\mathrm{LSB}_k(x) := x\pmod{2^k}$ ，同样我们可以考虑 $l$ 不是2的幂的情况下的 $x\pmod{l}$ 。与上面的情况类似，我们允许 $k$ 取任何（正）实数值，因此在这种情况下，我们可以通过 $\mathrm{LSB}_k(x) := x\pmod{\lceil 2^k\rceil}$ 来定义 $\mathrm{LSB}_k$ ，换句话说， $\mathrm{LSB}_k(x)$ 便是 $2\le l = \lceil 2^k\rceil \le p$ 的情况下的 $x\pmod{l}$ 。
和最高有效位的情况不同，对于任何形式的 $p$ 和任意位 $i<n$ 中没有一个值会总是出现。也就是说，对于 $\varepsilon_i = 0$ 的值数目可能不等于 $\varepsilon = 1$ 的数目，但二者的比例始终是多项式的。特别是对于 $p = 2^n + 2^{n-1} + 1$ 的极端情况，其中有 $2^{n} - 1$ 个元素对于 $x\in \mathbb{Z}_p^*$ 有 $\mathrm{Bit}_{n-1} = 0$ ，以及 $2^{n-1}+1$ 个元素有 $\mathrm{Bit}_{n-1}(x) = 1$ 。当 $i=0$ 时， $(p-1)/2$ 个元素对于 $x\in \mathrm{Z}_p^*$ 有 $\mathrm{Bit}_0(x) =0$ 以及 $(p-1)/2$ 个元素有 $\mathrm{Bit}_0(x) = 1$ ，显然这两个占比完全一致。