哈希链 (Hash Chain)

哈希链通常用于认证的过程中，在哈希链之前主要是使用的是 身份-密码 验证的方式。 1981年，Lamport¹ 提出使用哈希函数的方式代替传统的验证方式。 这种哈希链的形式在后来的实际生活中也有着广泛的应用，而且对后来区块链的出现也有一定的启发意义。

---

1. 构造

哈希链

长度为 $\ell$ 的哈希链是由长度为 $\ell$ 的序列 $\{x_1,x_2,...,x_\ell\}$ 组成的，其中，对于 $0< i\leq \ell$，有 $x_i=H(x_{i+1})$，其中 $H:\{0,1\}^*\rightarrow\{0,1\}^k$ 是一个密码哈希函数。

一般提到认证协议（identification protocol），一般分为两个部分：注册（registration）和认证（identification）。

• 注册： $P$ 随机选取 $x_0\in_R\{0,1\}^k$，计算 $x_\ell=H^\ell(x_0)$，然后将 $x_\ell$ 发送给 $V$，$V$ 将 $x_\ell$ 作为 $v$ 保存起来； $P$ 与 $V$ 各自留有一个计数器 $i$，$i$ 的初始值为 $0$；
• 认证： $P$ 计算 $x_{\ell-i}=H^{\ell-i}(x_0)$ 并将 $x_{\ell-i}$ 发送给 $V$；$V$ 在收到 $x_{\ell-i}$ 之后，计算 $H(x_{\ell-i})\overset{?}{=}v$ 是否成立，如果成立，则将 $v$ 的值重新设置为 $x_{\ell-i}$。

Hint

现实中的 $\ell$ 一般取得比较大，如 $\ell=2^32$

Hint

$P$ 的空间复杂度是 $O(\log \ell)$，$V$ 的空间复杂度是 $O(1)$；

注册过程，$P$ 的计算复杂度是 $O(\ell)$，$V$ 的计算复杂度是 $O(1)$；

认证过程，$P$ 的计算复杂度是 $O(\log \ell)$，$V$ 的计算复杂度仍然是 $O(1)$。

---

1. L. Lamport, “Password authentication with insecure communication,” Communications of the ACM, vol. 24, no. 11, pp. 770–772, 1981. ↩