LCS35

LCS35は、1999年にロン・リベストによって設定された暗号チャレンジであり、タイムロックパズルです。チャレンジは、次の値を計算することです。

$${\displaystyle w=2^{2^{t}}{\pmod {n}}}$$

ここで、tは特定の14桁（または47ビット）の整数、すなわち79685186856218であり、nは2つの大きな素数（ここでは示されていない）の積である特定の616桁（または2048ビット）の整数である。wの値は、別の616桁の整数である暗号文zを復号するために使用できる。平文にはnの因数分解に関する隠された情報が含まれており、解を容易に検証することができる。

このチャレンジの背後にある考え方は、nの因数分解を知らずにwの値を求める唯一の既知の方法は、 t回の連続した平方根を求めることである。tの値は、ムーアの法則を考慮し、1999年のチップ速度を基準としてこの総当たり計算に約35年かかるように選ばれた。リベスト氏は、「ムーアの法則の破綻がパズルを意図よりも難しくする可能性があるのと同様に、因数分解の技術におけるブレークスルーはパズルを意図よりも簡単にするだろう」と指摘している。

このチャレンジは、現在MIT コンピューター科学および人工知能研究所の一部となっている MIT コンピューター科学研究所の創立 35 周年記念式典で設定され、その名前もそこから取られています。

LCS35チャレンジは20年後の2019年4月15日に、プログラマーのベルナール・ファブロによって解決されました。^{[1] [2]}平文は「!!!  Happy Birthday LCS  !!!」で始まります。^[3]

2019年5月14日、ロナルド・L・リベストはLCS35の新しいバージョン（CSAIL2019と名付けられました）を公開し、パズルを2034年まで拡張しました。^[4]

参考文献

1. 「LCS35 タイムロック暗号パズル」(PDF) . people.csail.mit.edu .
2. 「プログラマーがMITの20年来の暗号パズルを解く | MIT CSAIL」www.csail.mit.edu。
3. 「20年前のMIT LCS35タイムカプセル暗号パズルが解読される - 3ページ - mersenneforum.org」www.mersenneforum.org . 2019年6月5日閲覧。
4. 「CSAIL2019タイムカプセル暗号パズルの説明」people.csail.mit.edu。

外部リンク

• LCS35タイムカプセル暗号パズルの説明、ロナルド・L・リベスト
• タイムカプセル開封式