マークルのパズル

マークルのパズル（英: Merkle's Puzzles）とは、ラルフ・マークルが1974年に考案した初期の公開鍵暗号システムであり、1978年に発表された。事前に秘密を共有していなくとも、メッセージを交換することで秘密を共有できる方式である。

概要

アリスとボブが通信すると仮定する。ボブはアリスに対して次のようにしてメッセージを送信できる。まず、ある程度の難しさのパズルを多数作成する。パズルはアリスがそれなりの時間の計算で解ける程度のものでなければならない。パズルは、総当り攻撃で解ける程度の短い未知の鍵を持つ暗号メッセージの形になっている。ボブはアリスに全てのパズルを送り、アリスはそこから無作為に1つを選んで解く。解いた結果には識別子とセッション鍵が含まれているので、アリスは識別子をボブに送ることで、どのセッション鍵を使うかを指示する。この時点で両者は共通の鍵を持つことになる（アリスはパズルを解くことでそれを得ており、ボブはパズルの作者なので識別子から鍵がわかる）。盗聴者がこの通信を聞いていたとしても、アリスがどのパズルを解いたのかは判らない。従って、盗聴者は鍵を得るために全てのパズルを解くしかないが、パズルが多数あるため非常に時間がかかる。

参考文献

• R. C. Merkle, "Secure Communications over Insecure Channels" Communications of the ACM 21(4), pp294–299 (April 1978).

外部リンク

• Ralph Merkle, Secure Communications over Insecure Channels (1974): 歴史
• Ralph Merkle, 1974 project proposal for CS 244 at U.C. Berkeley.