ハッシュ関数
概要
ハッシュ関数（hash function）とは、大きな有限集合から $\mathbb Z_m=\{0,1,\dots,m-1\}$ のような小さな集合への写像で、元を短い値で要約するために使うものである。定義域のほうが大きいので異なる元が同じ値になる衝突は必ず存在し、辞書を作るハッシュ表では、関数を普遍族から無作為に選ぶことで、どの $n$ 個の鍵に対しても同じ棚に入る鍵の個数の期待値が $1+(n-1)/m$ 以下になる。暗号では衝突を見つけにくいこと（衝突困難性）を求めるが、各値の逆像の大きさがそろい、定義域が値の個数より十分大きい $m$ 通りの値の関数では約 $\sqrt m$ 個の無作為な入力で衝突が見つかり（誕生日攻撃）、位数が素数の巡回群で $H(x,y)=g^xu^y$ とおけば衝突を見つけることは $u$ の離散対数を求めることより易しくない。
前提知識: 誕生日のパラドックス, 合同式, 期待値, 離散対数
大きな集合の元に、小さな範囲の番号を割り当てたい場面は多い。単語の辞書を作るなら、単語から $0$ 以上 $m$ 未満の番号を計算して、その番号の棚に単語をしまえば、探すときも同じ番号の棚だけを見ればよい。このように、大きな集合から小さな集合への写像で、元を「要約」するために使うものを ハッシュ関数（hash function）という。定義域のほうが大きいので、異なる元が同じ値になること（衝突）は避けられない。
この記事では、衝突をどう扱うかを 2 つの立場から述べる。1 つは辞書（ハッシュ表）のための立場で、関数を 族から無作為に選ぶ ことで、どんな入力に対しても衝突が平均的に少ないことを保証する（普遍族、thm-hash-universal・thm-hash-table）。もう 1 つは暗号の立場で、衝突は存在するが 見つけるのが難しい ことを求める（衝突困難性）。誕生日のパラドックス により、各値の逆像の大きさがそろい、定義域が値の個数より十分大きい関数では、値の個数の平方根程度の個数の入力で衝突が見つかること（prop-hash-birthday）と、離散対数 の難しさから衝突を見つけにくい関数が作れること（thm-hash-dlog）を証明する。
定義
以下、$m\ge1$ について $\mathbb Z_m:=\{0,1,\dots,m-1\}$ とし、整数 $z$ について $z\bmod m\in\mathbb Z_m$ は $z$ を $m$ で割った余りとする。
有限集合 $U$ から $\mathbb Z_m$ への写像 $h$ を ハッシュ関数 といい、$h(x)$ を $x$ の ハッシュ値 という。$x\ne y$ かつ $h(x)=h(y)$ となる組 $\{x,y\}$ を $h$ の 衝突（collision）という。
$h\colon U\to\mathbb Z_m$ とし、$n\ge1$ について $\lvert U\rvert>(n-1)m$ とする。このとき、$n$ 個の相異なる元で、ハッシュ値がすべて等しいものがある。とくに $\lvert U\rvert>m$ なら衝突がある。
各 $t\in\mathbb Z_m$ について $h^{-1}(t)$ の元の個数がすべて $n-1$ 以下なら、$\lvert U\rvert=\sum_t\lvert h^{-1}(t)\rvert\le(n-1)m$ となり仮定に反する（鳩の巣原理）。$\square$
したがって、1 つの関数 $h$ を固定してしまうと、その $h$ を知る相手は同じ値になる $n$ 個の入力を選べる。ハッシュ表なら $n$ 個がすべて同じ棚に入り、探す手間は $n$ に比例する。そこで、関数を族から無作為に選ぶ。
有限集合 $K$ の各元 $k$ にハッシュ関数 $h_k\colon U\to\mathbb Z_m$ が対応しているとし、$k$ を $K$ から一様に無作為に選ぶ。
- 相異なるすべての $x,y\in U$ について $\Pr_k[h_k(x)=h_k(y)]\le1/m$ のとき、$\{h_k\}_{k\in K}$ を 普遍族（universal family）という。
- 相異なるすべての $x,y\in U$ と、すべての $s,t\in\mathbb Z_m$ について $\Pr_k[h_k(x)=s,\ h_k(y)=t]=1/m^2$ のとき、対ごとに独立な族（pairwise independent family）という。
対ごとに独立な族は普遍族である。実際、$\Pr_k[h_k(x)=h_k(y)]=\sum_{t}\Pr_k[h_k(x)=t,\ h_k(y)=t]=m\cdot\frac1{m^2}=\frac1m$ である。$U$ から $\mathbb Z_m$ への写像すべての族（関数そのものを一様に選ぶ）は対ごとに独立だが、関数を表すのに $\lvert U\rvert\log_2m$ ビットほど要るので実用にならない。少ない鍵で済む族を作るのが次の節である（Sho08 §8.7、pp. 252–258）。
普遍族の構成
$p$ を素数とし、$K=\mathbb Z_p\times\mathbb Z_p$ の元 $(a,b)$ に $h_{a,b}(x):=(ax+b)\bmod p$（$U=\mathbb Z_p$、$m=p$）を対応させると、対ごとに独立な族である。
$x\ne y$ を固定する。写像 $(a,b)\mapsto(ax+b,\ ay+b)$（法 $p$）は、$\mathbb Z_p$ が体で行列 $\begin{pmatrix}x&1\\y&1\end{pmatrix}$ の行列式 $x-y$ が $0$ でないので、$\mathbb Z_p^2$ の全単射である。よって $(h_{a,b}(x),h_{a,b}(y))$ は $\mathbb Z_p^2$ 上の一様分布に従う。$\square$
値の範囲を $p$ より小さい $m$ にしたいときは、余りをもう一度とる。このとき対ごとの独立性は失われるが、普遍性は残る。
$p$ を素数、$1\le m\le p$ とし、$K=\{1,\dots,p-1\}\times\mathbb Z_p$ の元 $(a,b)$ に
$$
h_{a,b}(x):=\bigl((ax+b)\bmod p\bigr)\bmod m\qquad(x\in\mathbb Z_p)
$$
を対応させる。この族は普遍族である。
$x\ne y$ を固定し、$r:=(ax+b)\bmod p$、$s:=(ay+b)\bmod p$ とおく。prop-hash-affine の証明と同じく $(a,b)\mapsto(r,s)$ は $\mathbb Z_p^2$ の全単射であり、$r=s$ は $a(x-y)\equiv0$、すなわち $a=0$ と同値である。よって $(a,b)$ が $K$ 全体を動くとき、$(r,s)$ は $r\ne s$ となる組 $p(p-1)$ 個のそれぞれをちょうど 1 回ずつとる。
衝突は $r\equiv s\pmod m$ のときに起こる。$r$ を固定すると、$s\in\mathbb Z_p$、$s\ne r$、$s\equiv r\pmod m$ となる $s$ の個数は、$\mathbb Z_p$ のうち $r$ と法 $m$ で合同なもの（高々 $\lceil p/m\rceil$ 個）から $r$ 自身を除いた数なので、
$$
\Bigl\lceil\frac pm\Bigr\rceil-1\le\frac{p+m-1}m-1=\frac{p-1}m
$$
個以下である。$r$ は $p$ 通りなので、衝突する $(r,s)$ は $p(p-1)/m$ 個以下で、確率は $\frac{p(p-1)/m}{p(p-1)}=\frac1m$ 以下である。$\square$
Sho08 Example 8.38（pp. 256–257）は同じ族を確率変数の言葉で扱っている。長い入力 $(s_1,\dots,s_\ell)\in\mathbb Z_p^\ell$ には、$s\mapsto r_0+r_1s_1+\dots+r_\ell s_\ell$ の形の族が対ごとに独立になる（同書 Example 8.37、p. 255）。
ハッシュ表
$n$ 個の鍵の集合 $I\subset U$ を、関数 $h$ で $m$ 個の棚（リスト）に分けてしまうのが ハッシュ表 である。鍵 $x$ を探す手間は、$x$ と同じ棚に入っている鍵の個数 $L_x:=\lvert\{y\in I\mid h(y)=h(x)\}\rvert$ に比例する。
$\{h_k\}$ を $U$ から $\mathbb Z_m$ への普遍族、$I\subset U$ を $n$ 個の元の集合とし、$k$ を一様に選ぶ。
- 任意の $x\in U$ について、$x\in I$ なら $E[L_x]\le1+\frac{n-1}m$、$x\notin I$ なら $E[L_x]\le\frac nm$ である。
- $I$ の中の衝突の個数 $C:=\lvert\{\{y,z\}\subset I\mid y\ne z,\ h_k(y)=h_k(z)\}\rvert$ について $E[C]\le\binom n2\frac1m$ である。とくに $m\ge n^2$ なら、$I$ の中に衝突がない確率は $\frac12$ より大きい。
- $L_x=\sum_{y\in I}\mathbf 1\{h_k(y)=h_k(x)\}$ と書ける。期待値 の線形性により $E[L_x]=\sum_{y\in I}\Pr[h_k(y)=h_k(x)]$ で、$y=x$ の項は $1$、$y\ne x$ の項は普遍性により $\frac1m$ 以下である。$x\in I$ なら $y=x$ の項が 1 つと残り $n-1$ 項、$x\notin I$ なら $n$ 項がすべて $\frac1m$ 以下である。
- 同様に $C=\sum_{\{y,z\}}\mathbf 1\{h_k(y)=h_k(z)\}$（和は $I$ の 2 元部分集合 $\binom n2$ 個にわたる）なので $E[C]\le\binom n2\frac1m$ である。$C$ は $0$ 以上の整数なので $\mathbf 1\{C\ge1\}\le C$ であり、$\Pr[C\ge1]\le E[C]\le\frac{n(n-1)}{2m}< \frac12$（$m\ge n^2$ のとき）である。$\square$
1 から、$m$ を鍵の個数 $n$ 程度にとれば、どの鍵を探す手間も平均して定数で抑えられる（Sho08 Example 8.34、pp. 252–253）。大事なのは、この期待値が鍵の集合 $I$ の選び方によらず、関数の選び方についてとられていることである。2 は、最初に $n^2$ 個の棚を用意すれば、数回選び直すだけで衝突のない関数が見つかることを意味する。
$p=13$、$m=4$ とする。固定した関数 $h(x)=x\bmod4$ では、$I=\{0,4,8,12\}$ の $4$ 個がすべて棚 $0$ に入り、$L_0=4$ である。thm-hash-universal の族では、$x=0$、$y=4$ が衝突する $(a,b)$ は $156$ 組中 $30$ 組で、確率は $\frac5{26}=0.192\ldots\le\frac14$ である。
$n=10$ 個の鍵を普遍族で $m=100$ 個の棚に入れると $E[C]\le\frac{45}{100}$ なので、衝突のない確率は $0.55$ 以上である。関数そのものを一様に選ぶ（対ごとに独立な族の一つ）と、衝突のない確率は $\frac{100\cdot99\cdots91}{100^{10}}=0.628\ldots$ である。
衝突困難性
ファイルの改ざんの検出や電子署名では、長いデータ $x$ の代わりに短いハッシュ値 $h(x)$ を保管・署名する。このとき関数 $h$ は公開されており、攻撃者は $h$ を知ったうえで $h(x)=h(x')$ となる別のデータ $x'$ を作ろうとする。prop-hash-pigeonhole により衝突は必ず存在するので、求めるのは「存在しない」ことではなく「見つけるのが難しい」ことである。
公開の母数（鍵）で決まるハッシュ関数の族について、母数が与えられてから衝突を出力する効率のよい手順のどれもが、無視できるほど小さい確率でしか成功しないとき、その族は 衝突困難（collision resistant）であるという。
母数を入れるのは、固定した 1 つの関数なら衝突の組を書き込んだだけの手順が存在してしまうからである（BS23 Attack Game 8.1・Definition 8.1 と直後の説明、p. 290）。「効率がよい」「無視できる」は、母数の大きさに対する多項式時間と、どんな多項式の逆数よりも速く $0$ に近づくことを指す。次の命題は、値の個数 $m$ に対して $\sqrt m$ 程度の手間で衝突が見つかることを示す。
$h\colon U\to\mathbb Z_m$ は各値の逆像の元の個数がすべて $\lvert U\rvert/m$ に等しいとする。$x_1,\dots,x_n$ を $U$ から独立に一様に選ぶと、$x_i\ne x_j$ かつ $h(x_i)=h(x_j)$ となる $i< j$ が存在する確率は
$$
1-\exp\Bigl(-\frac{n(n-1)}{2m}\Bigr)-\frac{n(n-1)}{2\lvert U\rvert}
$$
以上である。
逆像の大きさがそろっているので、$h(x_1),\dots,h(x_n)$ は $\mathbb Z_m$ 上で独立に一様に分布する。値のどれか 2 つが一致する事象を $A$ とすると、誕生日のパラドックス の定理「全員の誕生日が異なる確率の評価」（$N=m$）により $\Pr[A]\ge1-\exp(-\frac{n(n-1)}{2m})$ である。入力のどれか 2 つが一致する事象を $B$ とすると、同じ記事の命題「一致の確率の上界」（$N=\lvert U\rvert$）により $\Pr[B]\le\frac{n(n-1)}{2\lvert U\rvert}$ である。$A$ が起きて $B$ が起きなければ、値が一致した 2 つの入力は異なり衝突になる。$\Pr[A\setminus B]\ge\Pr[A]-\Pr[B]$ から主張が従う。$\square$
$m=2^{32}$ なら、$n\approx1.18\cdot2^{16}$ 個の入力で値の一致の確率が $\frac12$ を超え、$\lvert U\rvert$ が十分大きければ、ほぼその確率で衝突が見つかる。したがって $\ell$ ビットの値を返すハッシュ関数は、約 $2^{\ell/2}$ 回の計算で衝突が見つかる。256 ビットの値を返す SHA256（BS23 p. 294）でも約 $2^{128}$ 回が上限である。逆像の大きさがそろっていない関数でも、値のどれか 2 つが一致する確率は $1-\exp(-\frac{n(n-1)}{2m})$ 以上である（同書 Corollary B.2、pp. 1101–1103。この記事では証明しない）。
衝突困難性を何の仮定もなしに示す代わりに、よく研究された問題の難しさに帰着させることができる。以下、$G$ を位数が素数 $q$ の巡回群、$g$ をその生成元とし、指数は $\mathbb Z_q$ の元とみなす（離散対数）。
$u\in G$ とし、$H\colon\mathbb Z_q\times\mathbb Z_q\to G$ を $H(x,y):=g^xu^y$ で定める。$H$ の衝突 $(x,y)\ne(x',y')$、$H(x,y)=H(x',y')$ が与えられると、$y\ne y'$ であり
$$
\log_gu=(x-x')(y'-y)^{-1}\quad(\mathbb Z_q\text{ での計算})
$$
である。したがって、一様に選んだ $u$ に対して確率 $\varepsilon$ で $H$ の衝突を出力する手順があれば、それに引き算と $\mathbb Z_q$ での逆元の計算を加えるだけで、一様に選んだ $u$ の離散対数を確率 $\varepsilon$ で求める手順が得られる。
$g^xu^y=g^{x'}u^{y'}$ より $g^{x-x'}=u^{y'-y}$ である。$y=y'$ なら $g^{x-x'}=1$ で、$g$ の位数が $q$ なので $x=x'$ となり、$(x,y)\ne(x',y')$ に反する。よって $y'-y\ne0$ で、$q$ が素数なので $\mathbb Z_q$ で逆元 $w$ をもつ。両辺を $w$ 乗すると $u=u^{(y'-y)w}=g^{(x-x')w}$ である。逆元は 拡張Euclidの互除法 で効率よく計算できるので、後半も従う。$\square$
$H$ は $q^2$ 個の入力を $q$ 個の値に縮める。離散対数が難しいという仮定のもとで、$H$ は衝突困難である（BS23 Fact 10.3・Theorem 10.4、pp. 414–415）。
$p=23$ の平方剰余のなす位数 $q=11$ の部分群で、$g=2$（$2^{11}\equiv1\pmod{23}$）、$u=9$ とする。$H(3,4)=2^3\cdot9^4\equiv8\cdot6\equiv2$、$H(1,0)=2$ なので、$(3,4)$ と $(1,0)$ は衝突である。thm-hash-dlog により $\log_29=(3-1)(0-4)^{-1}=2\cdot7^{-1}=2\cdot8=16\equiv5\pmod{11}$ で、実際 $2^5=32\equiv9\pmod{23}$ である。逆に $\log_gu=5$ を知っている人は、$(x,y)$ と $(x+5,y-1)$ という衝突をいくらでも作れる。$u$ は誰も離散対数を知らない形で選ぶ必要がある。
反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 関数を族から無作為に選ぶ（thm-hash-table） | 固定した $h(x)=x\bmod4$、$I=\{0,4,8,12\}$ | $L_0=4$ で、$1+\frac{n-1}m=\frac74$ を超える |
| $p$ が素数（thm-hash-universal） | $p$ の代わりに $4$：$((ax+b)\bmod4)\bmod2$、$a\in\{1,2,3\}$、$b\in\mathbb Z_4$ | $x=0$、$y=2$ がいつも衝突し、確率 $1>\frac12$ |
| $m\ge n^2$（thm-hash-table の 2） | 関数そのものを一様に選び、$n=m=10$ | 衝突のない確率が $10!/10^{10}=0.00036\ldots<\frac12$ |
| 群の位数が素数（thm-hash-dlog） | $G=(\mathbb Z/23\mathbb Z)^\times$（位数 $22$）、$g=5$、$u=2$ | $H(x,y)=H(x,y+11)$ がいつも成り立ち、この形の衝突からは $\log_gu$ が求まらない |
表の各行の確かめを開く
2 行目：$(2a+b)\bmod4$ と $b\bmod4$ の偶奇は等しい（$4$ が偶数なので、$4$ で割った余りの偶奇は元の数の偶奇と同じ）ので、$h(0)=h(2)$ がすべての鍵で成り立つ。
4 行目：$5$ は法 $23$ の原始根で、$u=2=5^2$ は平方剰余なので $2^{11}\equiv1\pmod{23}$ である。よって $H(x,y+11)=H(x,y)\cdot2^{11}=H(x,y)$ で、たとえば $H(0,0)=H(0,11)=1$ は衝突だが、$y'-y=11$ は法 $22$ で逆元をもたず、証明の最後の段が使えない。この衝突は $\log_52$ を知らなくても作れる。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
