Boneh Publications: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes

[ssst0n3]

• Boneh Publications: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes
• https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=c8f9439df73b065e124000e23a504d1dbe4ae79d
• diffie hellman - Understanding the Definition of Most Significant Bits in the Hidden Number Problem - Cryptography Stack Exchange

---

• what's Goldreich-Levin hard-core bits #24

[ssst0n3]

摘要

我们证明了，Diffie-Hellman 密钥交换协议中，从参与者的公钥，计算密钥的 最重要bits (MSBs) 和 计算密钥本身同样困难。这项工作通过研究 HNP(hidden number problem) 完成。HNP是指，给定一个 oracle $\mathcal {O}_{\alpha,\beta} (x) : return ~~ MSB_k(\alpha g^x+\beta \mod p)$ , 求 $\alpha, \beta \mod p$ 。 我们展示了这个问题的许多其他应用，包括：(1) 在El-Gamal加密、Shamir消息传递方案等中，计算最高有效位(MSB)非常困难。(2) 带有提示的因式分解。我们的研究结果建议一种新的 Diffie-Hellman 密钥交换(和其他系统) 的变体，我们证明了计算其 MSB 是困难的。

[ssst0n3]

1. Introduction

1.1 Motivation

$\mathbb Z_p^*$ 上关于基 g 的 离散对数问题 (DLP) 是指, 给定 $y = g^x$ 求 x 。Diffie 和 Hellman 假定这个问题是困难的，提出了一个公钥系统: Alice 和 Bob 分别有私钥 a, b ， 他们分别计算 $g^a, g^b$ 并发送给对方。然后他们都计算一个密钥 $g^{ab}$ 。据信计算 $DH_g(g^a, g^b) = g^{ab}$ 和 DLP 一样困难。

在密钥协商后，Alice 和 Bob 可以使用分组密码保证会话安全。一个自然的密钥派生方法是，使用 $g^{ab}$ 的一块(block) bits 。例如, 如果 p 是一个 1024 位素数，可以使用 $g^{ab}$ 的 64 位 MSB 。攻击者可能无法计算整个 $g^{ab}$ ， 但仍然有可能计算 $g^{ab}$ 的部分bits从而破解会话。因此， $g^{ab}$ 的 MSBs 对于知道 $g^a, g^b$ 的敌手是否是安全的，是一个重要的问题。尽管有着悠久的历史，Diffie-Hellman 密钥的 MSBs 的安全性还没有被证明。

有很多密码学方案都与 Diffie-Hellman 函数 $DH_g(g^a, g^b) = g^{ab}$ 相关，或是基于其提出的。这些方案依赖于 $g^{ab}$ 的???隐藏特性???。例如，我们提到的 ElGamal 的公钥系统，Shamir的消息传递方案，Bellare-Micali 非交互式不经意传输，Okamoto会议密钥共享方案。

在这篇论文中，我们研究了 Diffie-Hellman 密钥交换方案及上述相关方案 的 MSB 的安全性。我们的结果建议一种新的Diffie-Hellman密钥交换协议的变体。

[ssst0n3]

1.2 Preliminaries and Statement of Results

MSB

译者注：Most Significant Bit 通常的理解为 x 的最高k bits，作者为了使用数学语言表达，重新对MSB下了定义，但目标一致，仍是为了表达x的最重要bits，只是与我们通常理解的定义不同。这样的定义可以有多个。

给定素数p， $n= \lceil \log p \rceil$ 是p的二进制长度， $x \in [0, p-1]$ , 定义 $MSB_k(x) = t, t\cdot p /2^k \le x \lt (t+1)\cdot p / 2^k$ 。例如, $MSB_1(x)$ 在 $x < p/2$ 或 $x > p/2$ 时为 0 或 1。

译者注：原论文MSB定义为 $(t-1)\cdot p/2^k \le x \lt t\cdot p / 2^k$ ，并举例 $MSB_1(x)=0, 1$ ,我认为这是错误的。因为在 $MSB_1(x) = 0$ 时，x < 0 ，矛盾。
Steven Galbraith “Mathematics of Public Key Cryptography” : 21.7 Bit Security of Diffie-Hellman 支持了这个观点。故采用 Steven Galbraith 修正后的定义。

为了方便，我们有时采取另一个定义：

$MSB_k(x)$ 是一个整数 z 使得 $|x-z|\lt p/ 2^{k+1}$ 。

译者注：与上一个定义是独立的，都可表达x的最重要k bits，但两者无关。以上两个定义，在 k 越大时，MSB约接近x ，都具备表达 x 的最重要 k bits的能力。

这个定义和标准的MSB定义很相似，至多有1bit不同。换句话说，我们的结果同样适用于MSB的标准定义。给定x的k位MSB(标准定义)，我们可以通过在其后添加0来构造 z。

为了研究 Diffie-Hellman 密钥的一部分的安全性，建议研究一个抽象问题，HNP。

[ssst0n3]

Hidden Number Problem (HNP)

p, k 确定, 令 $O_{\alpha,\beta,g}(x)$ 是一个oracle(提示函数), 给定输入x，返回 $\alpha g^x + \beta \mod p$ 的最重要k位 。

$$ \mathcal {O}_{\alpha,\beta,g}(x) = MSB_k(\alpha g^x + \beta \mod p) $$

这个任务是通过oracle $\mathcal {O}_{\alpha,\beta,g}(x)$ , 计算“隐藏数” $\alpha,\beta \mod p$ 。

可以使用选择的x查询oracle(假定oracle永远返回正确的答案)。注意，查询oracle的方式会带来一个???限制???。具体来说，隐藏数 $\alpha$ 的乘数，是 $\mathbb{Z}^{*}_p$ 的一个元素，查询方需要知道其关于g的离散对数(x)。能够应对这个限制，对于当前的应用很关键。这将使得攻击变得困难，且与不受限时使用的方法有所不同。

[ssst0n3]

使用非受限查询的Oracle

允许使用任意 $\alpha$ 的乘数查询的场景已经被充分研究了。假定 oracle 计算 $O_{\alpha,\beta(x)} = MSB(\alpha x + \beta)\mod p$ ， $\beta=0$ 的场景，Alexi, Chor, Goldreich 和 Schnorr 完全解决了这个问题。他们的方法即使在oracle有噪声的情况下也有效。同时，在非受限查询的场景，容易发现和线性同余生成器 $x_{i+1}=ax_i + b \mod p$ 相关 ，它截断了 $x_i$ 并输出它们的最高有效位（MSB）。在[FHKLS 88]中研究了满足线性同余的整数变量重构问题。我们的结果在某些场景中优化了[FHKLS 88]的结果。

[ssst0n3]

1.3 主要结果

我们首先证明以下两个关于 Diffie-Hellman 密钥的难度(hardness) 的结果。

THEOREM 1.1 ???给定一个高效的算法???，由 $g^a, g^b$ 计算 $g^{ab}$ 的 $3\sqrt{\log p}$ bits ，则有一个算法可在多项式时间计算 $g^{ab}$ 。

如果计算 $DH_g{g^a, g^b}$ 是困难的，则 $DH_g{g^a, g^b}$ 的MSB 是安全的。???我们提供一个算法通过舍入(rounding) 在格中解决这个问题???。我们的约简算法高效，并且其实现总能够迅速找到隐藏的值。我们注意到，在通常的 p 大小下，格子的维数很小。即使oracle只给出一个比特，该实现在所有运行中都成功找到了解决方案。

THEOREM 1.2 （小生成元场景）如果 $g\le 2^k$ ，计算 $DH_g(g^a, g^b)$ 的最重要k bits 是困难的。

例如, 如果 $g=2$ 是 $\mathbb Z^{*}_p$ 的一个生成元，即使第1个bit也是难以计算的。

这些结论，可扩展至下列相关方案。我们假定生成元、素数已经由Bob 和 Alice商定，且所需的逆元存在。

ElGamal Public Key Encryption Bob 选择随机数x，公开 $y = g^x$ ， 欲发送消息 m 给 Bob， Alice选择随机数 r 并发送 $g^r, my^r$ 。破解这个方案需要计算函数 $EL_g(g^x, g^r, mg^{xr})=m$

Shamir Message Passing Scheme 为了发送消息m, Alice 选择随机数 r, 发送 $y=m^r$ 。Bob选择随机数 s, 发送 $z=y^s$ 给Alice。Alice发送 $w=z^{r^{-1}}$ 给Bob，Bob计算 $m=w^{s^{-1}}$ 。破解该方案需要计算 $SH(g^{ab}, g^{a}, g^{b}) = g$

Okamato Conference Key Shari Bob选择随机数r, 发送给Alice $x=g^r$ ，Alice选择随机数s, 发送 $y=x^s$ 给Bob 。Bob计算 $y^{r^{-1}}$ 。破解需要计算 $OK_g(g^{ab}, g^{a}) = g^{b}$ 。

上述函数和 Diffie-Hellman 的等价性 在 [SS] 中有相关研究。

THEOREM 1.3 上述协议中的最重要 $\sqrt{\log p}$ bits 是难以计算的，除非 Diffie-Hellman 函数本身容易计算。

我们在这里指出，这些应用并不直接来自上述内容。它还提出了密码方案的新变体：例如，在ElGamal 方案中，要加密一个消息 m , 如果我们只需要隐藏m的前k位，可以使用简化的加法操作，而不是乘法： m + DH_g(g^a, g^b)。

A new variant of key-exchange protocol 我们建议一个Diffie-Hellman 密钥交换的变种，计算其密钥的MSB是困难的。

下面我们讨论因式分解的应用。

THEOREM 1.4 (根据提示因式分解) 令 $n = pq, k \ge \sqrt{\log n}$ , 给定随机数 $x_1, \cdots, x_k$ , 其中 $x_i\mod p &lt; p/2^{3\sqrt{\log n}}$ , 则n可在多项式时间内分解。

这很容易从隐藏数字问题的解决方案中得出。给定x, 如果可以在亚指数(subexponential)时间内生成随机数x满足 $x\mod p &lt; p/2^{\sqrt{\log n}}$ ，则可以通过格技术在亚指数时间内因式分解。Coppersmith 在 $k = 1 , bound = n^{1/6}$ 解决了这个问题。我们的边界(bound) 更优，但是我们需要更多满足该边界的样本。对Vanstone等人的密码系统的影响在[Coppersmith 96]中进行了讨论。

Hardcore bits Pseudo-Random Generators 我们的结果无法处理当对手能够预测 $g^{ab}$ 的最高有效位时的情况。然而，我们相信我们的方法在处理这种情况下仍然是有用的。

THEOREM 1.5 如果 $DH_g(g^a, g^b) = g^{ab}$ 是困难的，那么存在一个伪随机数生成器。此外，在密钥交换之后，Alice 和 Bob无需相互交互来迭代该函数。

许多研究人员已经注意到了这个定理的各种版本。值得注意的是，Diffie-Hellman 函数不是一个单项函数，因为无法检查其输出。我们展示了可以对hard-core bits利用Goldreich-Levin定理，从 $g^{a,b}$ 中提取出密码学安全的伪随机bits。为了迭代的目的，我们将函数 $g^x \mapsto g^{x^2}$ 进行迭代使用。这个函数和 Diffie-Hellman 函数一样困难。

我们在这里指出，在多方场景中，为了避免类似 [B 95] 中因丢失会话密钥而导致的攻击，建议在下一轮标准中使用一个抗碰撞的hash函数(例如, MD5, SHA) (注：注意论文发表时间为1996年)对密钥进行hash处理，以打破代数相关性。提取 hard-core bits 使用了较弱的 hash 函数(例如模2的内积， 或 $ax+b \mod p$ )，而hash值则可以用作 (伪)随机函数的密钥，用于生成可证明不相关的会话密钥，用于不同会话之间。

[ssst0n3]

2 Proofs of the main results

本节我们表述了两个 HNP 的算法。为了便于表示，我们假定素数p 和 $\mathbb {Z}_p^{*}$ 的生成元是固定的。本届中，令 $n = \log p$ 。

[ssst0n3]

2.1 使用 $\sqrt{\log p}$ Bits

本节的主要定理证明了HNP可以通过使用一个输出 $\sqrt{\log p}$ bits 的oracle函数解决。

THEOREM 2.1 令 $\alpha$ 是 [1, p - 1] 范围内的整数。令 $O(x)=MSB_k(\alpha g^x \mod p), k = 3 \lfloor \sqrt{\log_2p\rfloor}$ 。则存在一个算法，通过oracle函数O，可在多项式时间( $\log p$ )内求得 $\alpha$ 。

[ssst0n3]

证明依赖于格中的舍入(rounding)技巧。因此，我们首先简要得回顾格的概念并引入相关结论。一个满秩的格L被定义为点的集合：

$$ L = \lbrace y: y=\sum_{i=1}^{d}t_ib_i, t_i \in \mathbb Z \rbrace $$

其中 $b_i$ 是 $\mathbb{R}^d$ 中线性无关的向量。集合 $\lbrace b_i \rbrace^d_{i=1}$ 被称为格基，而 d 是格的维度。我们用 $||v||$ 表示向量 $v\in \mathbb R^d$ 的 $L_2$ 范数 ( $\sqrt{\sum b_i^2}$ )。

由Babai提出的一个重要的结果表明，如何根据给定的格 $L$ 和点 $v$ , 找到最接近 $v$ 的格点。使用 Lenstra, Lenstra, Lovasz 的格基归约算法可以证明以下结论。

THEOREM 2.2

令 $L$ 是 d 维的格，给定一个点 $v\in \mathbb R^d$ ，存在一个多项式时间的算法 , 可找到格点 $w \in L$ , 使得

$$ || v - w || \le 2^{\frac{d}{2}-1} min \lbrace || v - b || : b \in L \rbrace $$

[ssst0n3]

Proof of Theorem 2.1 我们展示了一种概率性的预期在多项式时间内的算法，可恢复隐藏的数字 $\alpha$ 。令 $d=\sqrt{\log p}$ 。算法首先在范围 [1, p-1] 内独立且均匀地随机选择整数 $x_1, \cdots, x_d$ 。然后计算 $t_i = g^{x_i} \mod p$ （译者勘误：原文为 $t_i = g^{r_i} \mod p$ ），并用 $x_1, \cdots, x_d, 0$
（译者勘误：原文为 $r_1, \cdots, r_d, 0$ ）查询oracle ，oracle 返回值 $a_1, \cdots, a_d, a_{d+1}$ ， 根据oracle函数的定义，有 ：

$$ |(\alpha t_i \mod p)-a_i| \lt p/2^k, i=1,\cdots, d ~~ ~~ and ~~ ~~ |(\alpha \mod p)-a_{d+1}| \lt p/ 2^k \tag 1 $$

-  2^k 还是 2^{k+1} ? MSB定义和 Steven Galbraith 的 crypto-book 是 2^{k+1}

为了寻找隐藏数 $\alpha$ ，我们构造如下格 (行表示基向量)

$$ L = \begin{bmatrix} p&0&0&\cdots&0&0 \\ 0&p&0&\cdots&0&0 \\ &\vdots&&&0&\vdots \\ 0&0&0&\cdots&p&0 \\ t_1&t_2&t_3&\cdots&t_d&1 \end{bmatrix} $$

格L的维度为 d + 1, 我们将基向量中的前d个向量称为 p向量。注意当我们底部的向量乘以 $\alpha$ ，并减去适当数量的p向量时，我们将得到

$$ v_{\alpha} = (r_1, \cdots, r_d, \alpha) $$

其中对所有的 $i \le d$ , 有 $|r_i-a_i| \lt p/2^k$ 。换句话说， 向量 $u=(a_1, \cdots, a_d, a_{d+1})$ 满足：

$$ min\lbrace || u-w || ~~ | w \in L \rbrace \le \sqrt{d+1} p/2^k $$

译者注

$a_i &lt; b \Rightarrow || a || = \sqrt{ \sum_{1\le i \le n} a_i^2} \le \sqrt{n b^2} = \sqrt{n}b $

-  2^k 还是 2^{k+1} ? MSB定义和 Steven Galbraith 的 crypto-book 是 2^{k+1}

[ssst0n3]

THEOREM 2.3

（唯一性定理）令 $\alpha$ 是 $[1, p-1]$ 范围内一个固定的数, $d = \lfloor \sqrt{log_2\enspace p} \rfloor$ ,
$k=3 \lfloor \sqrt{log_2 \enspace p} \rfloor$ 。在范围 $[1, p-1]$ 中均匀且独立地随机选择整数 $t_1, ..., t_d$ 。令 $L$ 是如上所述的格， $u=(a_1, \cdots, a_{d+1})$ 是满足条件 (1) 的一个向量。则有 $\frac{1}{2}$ 的概率有一个唯一的向量 $v\in L$ 使得 $||u-v|| \le \frac{p}{2^{k\enspace-\enspace d}}$

[ssst0n3]

Proof

上面构造的格点 $v_\alpha$ 满足 $|| u-v_\alpha || \lt p/2^{k-d}$ 是明确的，证明 $v_\alpha$ 是唯一的这样的格点需要更多工作。 令 $\beta, \gamma$ 是两个整数，我们定义 $\beta, \gamma$ 的模距离为

$$ dist_p(\beta, \gamma) = \underset{b\in \mathbb Z}{min} |\beta - \gamma -bp| $$

例如， $dist_p(1, p) = 1$ 。 假设 $\beta \neq \gamma \pmod p$ ，且它们都是属于 $[1, p-1]$ 范围内的整数。定义：

$$ A = \underset{t}{Pr} [dist_p(\beta t, \gamma t) > 2p/2^{k-d}] $$

其中 t 是在 $[1, p-1]$ 范围内均匀随机选择的整数，有：

$$ A = \underset{t}{Pr} [\frac{2p}{2^{k-d}} \lt (\beta - \gamma)t \mod p < p - \frac{2p}{2^{k-d}}] = \frac{\lfloor p-\frac{2p}{2^{k \enspace - \enspace d}}\rfloor - \lceil \frac{2p}{2^{k\enspace -\enspace d}} \rceil}{p-1} \le 1- \frac{5}{2^{k-d}} $$