ポスト量子セキュリティに関する読みやすい日刊投稿シリーズを始めます。でも、:)何日続くのか全く分かりません。さて、見てみましょう。 1日目:ショールのアルゴリズムと量子黙示録(?) 私たちのセキュリティスタックのほとんど(RSA、ECC、Diffie-Hellman)は、一つの前提に基づいています:整数分解と離散ログは「ハード」であるということです。古典的なシリコンでは、そうです。RSA-2048を解読するには、宇宙の年齢よりも単純に時間がかかるだけです。 しかしこれは物理法則ではありません。それは古典的な計算の限界です。 1994年、ピーター・ショアは量子コンピュータ上で効率的に解けることを示しました。Shorのアルゴリズムは単にキーを力技で操作するだけではありません。量子フーリエ変換(QFT[量子場論ではありません 笑])を用いて関数 f(x) = a^x mod N の周期を求めます。一度生理期間が決まれば、その要素が揃います。 そして、一度因子が揃えば、秘密鍵は死にます。秘密鍵は公開鍵から再構成可能だからです。複雑さの変化こそが本当の「黙示録」なのです。サブ指数時間から多項式時間O((log N)^3)へと移動します。10倍のスピードアップの話ではありません。CRQCで数兆年もかかる時間に移行する話です。 RSAと同様に、ECC(楕円曲線暗号)も安全ではありません。効率的な代数群構造のため、256ビットのECC鍵を破る際にはRSA-2048よりも論理キュービット数が少なくて済みます。 --- 読んでくれてありがとう!明日は、なぜHNDL(今収穫・復号化)の脅威が、ポスト量子移行を今こそ必要だと説明します。 (映像:ピーター・ショア)