内容アドレス格納庫

$B = \{0,1\}^{*}$ を有限バイト列全体、$b$ を正整数とする。写像 $H : B \to \{0,1\}^{b}$ が暗号学的ハッシュ関数であるとは、次の性質が（計算量的な意味で）成り立つことをいう。

• （衝突困難性）$H(x) = H(y)$ かつ $x \neq y$ となる $(x, y)$ を現実的な計算資源で求められない。
• （原像困難性）$y \in \{0,1\}^{b}$ が与えられたとき、$H(x) = y$ となる $x$ を現実的な計算資源で求められない。

いま有限集合 $S \subseteq B$ を格納するとき、$x \in S$ を鍵 $H(x)$ のもとに保存し、取り出しも $H(x)$ で行う方式を内容アドレス格納庫（content-addressable store）という。この方式では、鍵は内容から決まり、内容が変われば必ず鍵も変わる。