タイムロックパズル

最近、仕事上の事情は少ないですが、暇な時に興味深いものをたくさん見ました。VDF に関連する情報を探している時に、指定された時間（T）の後にのみ解けるパズルをどのように設計するかという問題について話がありました。最初に考えてみましたが、時間という抽象的な概念をパズルの中でどのように定量化するかはわかりませんでした。🤔

そして、この引用された論文 Time-lock puzzles and timed-release Crypto を見つけました。

論文を読んで初めて、実際にはこの問題は次のように等価であることがわかりました：特定の計算回数 P を経るまで正しい結果を得ることができるアルゴリズムを設計し、このアルゴリズムの計算プロセスが並列計算で加速されないようにすることです。したがって、解読には 1 台のマシンしか使用できず、秒間の最大計算能力が S であると仮定すると、正しい結果を得るには必ず T = P / S 秒かかり、タイムロックの目的が達成されます。

論文では、2 つのタイムロックパズルの実装方法が紹介されています。

第 1 のタイムロックパズルの設計#

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

暗号化#

ステップ 1：2 つの大きな素数 p と q をランダムに選択し、それらを掛け合わせて n = pq を計算し、同時に φ(n) = (p-1)(q-1) を計算します。
ステップ 2：t = T*S を計算します。ここで、S は Bob のマシンが n の 2 乗をモジュロ計算できる回数（つまり、計算能力）です。
ステップ 3：安全な鍵 K と、RC5 などの暗号化アルゴリズムに使用する十分に安全な鍵をランダムに生成します。
ステップ 4：鍵と暗号化アルゴリズムを使用して元の情報を暗号化し、C_m = RC5 (K, M) を得ます。
ステップ 5：ランダムな数 a（1 <a < n）を選択し、K を暗号化して C_k = a^{2^{t}} (mod n) を得ます。

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

最後に、Alice は (n, a, t, C_k, C_m) を Bob に公開します。

復号#

Bob は M を取得するために鍵 K を使用して C_m を復号する必要がありますが、暗号化時に K が十分に安全であることが保証されているため、Bob は C_k から K = C_k - a^{2^{t}} (mod n) を計算することしかできません。

ここで、t は未知の変数ですが、Bob にとっては 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 です。これにより、Alice がメッセージを T 秒間ロックする目的が達成されます。

（Bob が正しい K を見つけたかどうかを判断する方法は、このアルゴリズムの範囲外です。一つの方法は、暗号化者が Bob に自分で検証させるために sha256 (K) を提供することです。）

第 2 のタイムロックパズルの設計#

第 2 の部分は詳細には見ていませんが、論文をclaude.aiにアップロードして AI に要約してもらいました（GPT-4 が使えない場合は、Claude2 を使用することを強くお勧めします）。

私：第 2 の方法について教えてください。

論文で提案されている第 2 の方法は、信頼できる代理人を使用する方法です。大まかな手順は次のとおりです：

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

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

ユーザーはそのランダムな鍵を鍵共有スキームで複数の部分に分割し、それぞれの部分を異なる代理人に与えます。

各代理人は将来の時刻 t に公開される鍵を使用して、自分が持っている部分鍵を暗号化します。

時刻 t に、十分な数の代理人が彼らが t 時点で持っている鍵を公開します。

ユーザーはこれらの鍵を使用して部分鍵を復号し、元のランダム鍵を再構築することができます。

最後に、このランダム鍵を使用して元のメッセージを復号します。

この方法の安全性は、信頼できる代理人が未来の鍵を事前に漏洩しないことに依存しています。また、複数の代理人を設定することで、鍵共有と閾値検証による一定の耐障害性を実現できます。個々の代理人が侵害されたり機能しなくなったりしても、十分な数の代理人が正常に機能していれば、情報は予定された時間に復号されます。