タイムロックパズル

最近仕事上あまり忙しくなく、暇なときに面白いものをたくさん見ました。VDF に関連する資料を探しているときに、ある問題について言及されていました：指定された時間 $T$ 後にしか解けないパズルをどのように設計するか。少し考えましたが、時間という抽象的な概念をパズルの中でどのように定量化するかは分かりませんでした。🤔

そして、この引用された論文 Time-lock puzzles and timed-release Crypto にたどり着きました。

記事を読んで初めて、この問題は実際には次のように等価であることが分かりました：アルゴリズムを設計し、 $P$ 回の計算を経なければ正しい結果を得られず、かつこのアルゴリズムの計算プロセスは並列計算によって加速されてはならない。こうすることで、1 台のマシンでしか解読できず、仮にそのマシンの最大計算能力が $S$ 秒あたりであれば、 $T = P / S$ 秒後に正しい結果を解き出すことができ、time-lock の目的を達成します。

記事では、2 つの time-lock パズルの実装方法が紹介されています。

第一の time-lock パズル設計#

アリスがボブに伝えたい情報 $M$ があり、 $T$ 秒間暗号化（ロック）する必要があります。（ここでの前提は、アリスが事前にボブの計算能力を知っている必要があることです）

暗号化#

第一ステップとして、2 つの大きな素数 $p$ と $q$ をランダムに選び、それらを掛け合わせて $n = p*q$ を得ます。同時に $\phi(n) = (p-1)*(q-1)$ を計算します。

第二ステップとして、 $t = T*S$ を計算します。ここで $S$ はボブが 1 秒間に行える $n$ の平方剰余の計算回数（いわゆる計算能力）です。

第三ステップとして、十分に安全な暗号化キー $K$ と RC5 のような暗号化アルゴリズムをランダムに生成します。

第四ステップとして、キーと暗号化アルゴリズムを使用して元の情報を暗号化し、 $C_m = RC5(K, M)$ を得ます。

第五ステップとして、ランダムな数 $a\ (1 < a < n)$ を選び、 $K$ を暗号化して $C_k = a^{2^{t}}\ (mod\ n)$ を得ます。

このステップは以下の手順で加速できます：まず $e = 2^{t}\ (mod\ \phi(n) )$ を計算し、次に $b = a^{e}\ (mod\ n)$ を計算します。

最後に、アリスは $(n, a, t, C_k, C_m)$ をボブに公開します。

解読#

ボブにとって $M$ を取得するには、キー $K$ を使って $C_m$ を解読する必要がありますが、暗号化時にすでに $K$ 自体が十分に安全であることが保証されています。ボブは $C_k$ を使って $K = C_k - a^{2^{t}}\ (mod\ n)$ を計算することしかできません。

ここには $t$ という未知数が残っており、ボブにとってはすべての $t$ を暴力的に探索する以外により良い方法はありません。

したがって、 $a^{2}, a^{4}, a^{8},a^{16},...a^{x} (t = 1,2,3,...)$ という系列の計算が必要です。この系列では、各項の計算が前の項の計算結果に依存していることが観察できます。 $a^{4} = (a^{2})^{2}, a^{8} = (a^{4})^{2}, ...$ つまり、後の値を事前に計算することはできず、並列計算によって加速することもできません。 $t$ 回の計算を経て結果を得るしかなく、以前に設定した $t = T*S$ に基づいて必要な計算時間は $T = t/S$ となり、アリスがメッセージを $T$ 秒間ロックする目的を達成します。

（ボブがどのようにして正しい $K$ を見つけたかを判断するかは、このアルゴリズムの問題には含まれません。一つの方法は、暗号化者が $sha256(K)$ を提供し、ボブが自分で検証することです。）

第二の time-lock パズル設計#

第二部は詳しく見ていませんが、直接 Claude2 に論文をアップロードし、AI に要約を手伝ってもらいました（GPT-4 が使えない場合は Claude2 を非常にお勧めします）。

ME: 第二の方法がどのように実現されるかを紹介してください。

記事で提案された第二の方法は、信頼できる代理を使用する方法で大まかに次のようになります：

複数の信頼できる代理を設定し、各代理が定期的にキーを公開します。

ユーザーはメッセージをランダムなキーで暗号化し、暗号文を得ます。

ユーザーはそのランダムなキーをキー共有スキームを通じて複数の部分に分け、異なる代理に渡します。

各代理は、未来の時間 t に公開されるキーを使用して、自分が持っている部分の子キーを暗号化します。

時間 t に、十分な数の代理が t の時点でのキーを公開します。

ユーザーはこれらのキーを使って子キーの部分を解読し、元のランダムなキーを再構築します。

最後に、このランダムなキーを使って元のメッセージを解読します。

この方法の安全性は、信頼できる代理が未来のキーを事前に漏らさないことに依存しています。また、複数の代理を設定することで、キー共有と閾値検証を通じて一定の耐障害性を実現できます。個々の代理が攻撃を受けたり無効になったりしても、十分な数の代理が正常に機能していれば、情報は予定された時間に解読されることができます。