はじめに
小学校などでは「タイムカプセル」という文化がある。箱の中にメッセージなどを入れ、20年後といった決められた未来まで地中に埋めておき、その時間になった際に地中から取り出しメッセージを開封するというようなものである。しかし、タイムカプセルは悪意ある人間が20年といった時間が経過する前に地中から掘り起こしてメッセージを盗み見るといった攻撃が可能であり、脆弱といえる。“Time-Lock Puzzles”は未来のおおむね狙った時刻にメッセージを開封できるという性質を持つ暗号のテクニックであり、タイムカプセルの他にたとえばオークションの最低価格がオークションの開始まで分からなくしておくといった応用が考えられる。この記事ではまずTime-Lock Puzzlesについて説明し、説明するために必要な数学などの知識について述べる。そしてTime-Lock Puzzlesの具体的なプロトコルを説明する。
この記事を読んで質問や改善点を見つけた場合は、気軽にコメントなどで指摘してほしい。
Time-Lock Puzzlesの性質
まず、Time-Lock Puzzlesの詳細のまえに性質について述べる。Time-Lock Puzzlesは次のような性質がある。
- Time-Lock Puzzlesは（ある程度）狙った時間の後にメッセージを開封できる
- Time-Lock Puzzlesは時間が経過した後に自動的にメッセージが開封されるわけではない
- ある“パズル”の解読に、パズルの作成者がおおむね意図した時間がかかる
- Time-Lock Puzzlesの解読はコンピューターを並列化しても高速化しない
いま、ある時間$T$秒後の未来にメッセージを送信したいアリスと、メッセージを開封したいボブがいるとする。この2人は次のようにTime-Lock Puzzlesのプロトコルを実行する。
- アリスは解読に$T$秒必要なパズルを高速に作成する。そしてこのパズルの解を対称鍵としてメッセージを暗号化する
- アリスは(1)のパズルと暗号文をボブへ送信する
- ボブはパズルの解読を開始する
- ボブは$T$秒後にパズルを解読し、その解を利用して暗号文を復号しメッセージを得る
ここで1つのポイントは、パズルの出題者アリスはパズルを高速に作成できる一方で、パズルの解読者ボブは解読に$T$秒かかってしまうことである。またボブはどれだけコンピューターを並列化したとしても、それによってパズルの解読は高速化しない。
べき剰余とオイラー関数とバイナリ法
具体的なプロトコルを説明する前に、まずは数学的な性質を少々解説する。
今、巨大な素数$p, q$とその2つを素因数に持つ合成数$n = pq$があり、またオイラー関数1を$\phi$とする。$\phi(n)$は$n$の素因数$p, q$を用いて次のように計算できる。
\phi(n) = (p - 1)(q - 1) \label{1}\tag{1}
そして、任意の数$x, a$について関数$\phi$がオイラー関数であるとき次が成り立つ。
a^{\phi(x)} \equiv 1 \pmod{x} \label{2}\tag{2}
さて、任意の$g, x, p$ついて$g^{2^x} \bmod p$という計算があるとする。$x$が少ない場合は$g$を$2^x$乗してから剰余を求めればよいため、剰余の計算は1回でよい。しかし$x$が巨大な場合は$g^{2^x}$が巨大となり、メモリが巨大に必要となり現実的な計算ではなくなる。したがって、次のような等しい関係を用いることがある。
g^{2^x} \bmod p = \underbrace{\left(\left((g \bmod p) \times (g \bmod p)\right) \bmod p \times \dots \times (g \bmod p)\right) \bmod p}_{2^x}
このように乗算のたびに剰余を計算したとしても、もとの結果と等しくなる。すると剰余計算の回数が$2^x$回になることと引き換えに計算中の数値が最大で$p - 1$に抑えられるため、たとえ$x$が巨大であってもメモリが足りなくなることを回避できる。これをさらに効率化した手法としてバイナリ法と呼ばれる方法があり、これにより$g^{2^x} \bmod p$のような計算における剰余算の回数を$x$回まで減らすことができる。
Time-Lock Puzzlesプロトコル
いよいよTime-Lock Puzzlesのプロトコルを説明する。いま、ある時間$T$秒後の未来にメッセージを送信したいアリスと、メッセージを開封したいボブがいるとする。また、彼らの世界のコンピューターはおおむね1秒間に$s$回の剰余計算を実行できるものとする。このとき、2人は次のようにTime-Lock Puzzlesのプロトコルを実行する。
- アリスは巨大な2つの素数$p, q$を作成し、これらの合成数$n = pq$を計算する
- ただし$n$の素因数分解は$T$秒よりも時間が必要であるとする
- アリスはメッセージ$m$を対称鍵$k$を用いてAES暗号2で暗号化し、その暗号文を$C_m$とする
- ただしAES暗号によって暗号化された$C_m$の対称鍵$k$を総当たり的に特定するためには、$T$秒より時間が必要であるとする
- アリスは$a \; (1 < a < n)$を選び、$t = sT$として$C_k = k + a^{2^t} \bmod n$を求める
- $C_k$は$n$の素因数$p, q$を知るアリスにとって高速に計算できる
- アリスは組$(n, a, t, C_k, C_m)$をボブへ送信する
- ボブは$b = a^{2^t} \bmod n$となる$b$を計算する。$C_k - b \equiv k \pmod{n}$となるため、これを用いて暗号文$C_m$をAES暗号で復号しメッセージ$m$を得る
気になることといえば、(3)でアリスは高速に$a^{2^t} \bmod n$を計算できる一方で、ボブは$T$秒必要であることであると思う。まず前の節の式（$\ref{2}$）で述べたように$a^{\phi(n)} \equiv 1 \pmod{n}$である。従って$2^t$がどれだけ巨大であったとしても次が成り立つ。
a^{2^t} \equiv a^{\left(2^t \bmod \phi(n)\right)} \pmod{n}
式（$\ref{1}$）より$\phi(n) = (p - 1)(q - 1)$なので、合成数$n$の素因数$p, q$を知るアリスは$\phi(n)$の値を求めてバイナリ法を用いることで、剰余計算の数を最大でも$\log_2{(p - 1)} + \log_2{(q - 1)}$とすることができる。一方でボブは$\phi(n)$を求めるためには$n$を素因数分解する必要があり、$n$は素因数分解が$T$秒では終わらないほど十分に巨大であるため、バイナリ法で$t$回の剰余計算を実行せざるをえない。したがってボブは(4)でアリスからデータを受け取った直後から計算を初めておおむね$T$秒後に計算が終了しメッセージ$m$を得ることができる。
まとめ
このようにすることで未来に開封できる“Time-Lock Puzzles”を構成することができる。ただしボブがパズルを解読すると暗号文を復号するための鍵が確実に手に入るという保証がないため、アリスはボブに無駄な計算を使わせるといった攻撃が可能である。このような相手に損をさせるような攻撃を回避するために、パズルを解読した結果が対称鍵であるという証明をする必要があり、それを構成することが今後の課題であると思う。