結城浩
2003年4月1日
今日もせっせと暗号本を書いている。
ところで、 最近あちこちで話題の「CDB」（またはCrDB）について少し書いておきます。 「CDB」というのは"Cryptographical Database"の略で、 日本語でいうなら「暗号学的データベース」といえるでしょう。 まだ日本語の定訳はないらしいです。
でも、内容を詳しく調べてみると、これをデータベースと呼ぶのは言い過ぎでして、 「高速な検索技法」と呼ぶのが正しいかと思います。 でもなかなか発想は斬新です。 SHA-1のようなメッセージダイジェスト関数を用いて、 超高速なデータ格納と検索ができるのが特徴。
簡単に解説してみましょう。
暗号技術で使用されるメッセージダイジェスト関数（一方向ハッシュ関数）は、 任意長のビットを固定長に圧縮（もちろん不可逆圧縮）する。 たとえばMD5ならば128ビット、SHA-1ならば160ビットに圧縮する。 通常は圧縮した結果のハッシュ値は、 もとのメッセージの正真性(完全性)のチェックに用いる。
CDBの開発者であるEvih Cra教授は、 このハッシュ値をデータベースのインデクスとして用いることを思いついた。 いま、データベースに格納したいキーとバリューの組があったとしよう。 まず、そのキーのハッシュ値を計算する。 そしてそのハッシュ値をインデクスにしてバリューを格納する。 まあ、簡単に言えば、ハッシュ値を配列の添字にしちゃうわけだ。 同じキーからは常に同じハッシュ値が計算されるから、 探し出したいバリューは、 何とオーダー１で検索できることになる。 つまり事実上、コストはハッシュ値の計算にかかる時間だけ。
もしも、異なる二つのキーのハッシュ値が衝突したらどうなるかって？ そこがメッセージダイジェスト関数のすばらしいところ。 ハッシュ値が衝突することは極めて極めて低い確率でしか起こらない。 MD5よりは、SHA-1を使うべきでしょうけれど。
以上が「暗号学的データベース」(CDB)の核心です。
メッセージダイジェスト関数は暗号技術の1つではあるけれど、 暗号ではないため、輸出規制などにはひっかからないのもうまい。 また、これをハードウェア化することも考えられるため、 このCDBの権利をめぐって、 チップメーカーなどが水面下で動いているらしい。 最近のちょっとホットな話題。
結城は、 Evih Cra教授自身が書いた短い解説記事"CDB: New Directions in Cryptographical Database"を翻訳してみました。 現在、公開の許可願いを教授にメールで出しているところです。
先日の「暗号学的データベース」は毎年恒例のエイプリルフール日記です。 「CDB」や「Evih Cra教授」や「"CDB: New Directions in Cryptographical Database"」という論文、全部存在しません。 存在してもそれは偶然の産物です。 Evih Craはarchiveの逆つづりで、 「New Directions in Cryptographical Database」というのは、Diffie-Hellmannの論文「New Directions in Cryptography」のもじりです。 Cryptographic Databaseというものは存在するらしいですが別物です。
改めてクイズとしましょう。
暗号クイズ
2003年4月1日の日記で、私は「暗号学的データベース」という話題をお話しました。
ここで書いた「暗号学的データベース」という技術は、 現実的には実現不可能です。 なぜですか。
もっと具体的にしましょうか。 たとえば、以下の擬似コードは現実的には実現不可能です。 なぜですか。
class CryptographicalDatabase {
String[] database;
public CryptographicalDatabase() {
database = $2^{160}$個のStringの配列を確保;
}
public void putData(String key, String value) {
添字 = keyのSHA-1のハッシュ値を計算する;
if (衝突が起きたかどうかを判定) {
実行時例外をthrowする
}
database[添字] = value;
}
public String getData(String key) {
添字 = keyのSHA-1のハッシュ値を計算する;
return database[添字];
}
}
4月1日と4月7日に出したクイズの解答を書きます。
一言で言えば、$2^{160}$の配列を作ることは事実上不可能だからです。
160ビットの値を添字に持つ配列を作ってみましょうか。 1個の値を格納するのに1個原子を使うとします（本当はもっと原子が必要でしょうけれど）。 すると、$2^{160}$個($10^{48}$個以上)の原子が必要になります。 ところで、地球を構成している原子の数はおおよそ$10^{51}$個ですから、 配列を構成するのに地球上の原子の1000分の1を使う必要があります。 おおざっぱに言えば、地球を立方体だと考えて、 10×10×10のマス目に区切ったときの一個分ってことですね。
もちろん、これは非現実的なサイズになります。