「破られない暗号」を求めて
量子時代へ暗号学者の探求

メールをチェックしたり、銀行口座にログインしたり、シグナル（Signal）でメッセージをやりとりしたりするとき、私たちのパスワードや認証情報は暗号（秘密を使用してデータを隠すロック方式）によって保護されている。暗号はサイバー世界の南京錠のようなもので、適切な鍵があればデータを解錠できる。鍵がなければ、手間のかかるブルートフォース（力任せ）の手法、つまり弓のこやブロートーチに相当するデジタル技術に頼らざるを得ない。

オンライン・セキュリティの信頼性は、数学に根ざしている。暗号方式は、「一方向性関数」と呼ばれる数学の問題群に基づいて構築されている。一方向性関数とは、一方向の計算は容易に実行できるが、逆方向の計算を効率的に実行することは、強力なコンピューターをもってしてもほぼ不可能である関数のことだ。いわば、空港のレンタカー会社の出口の路面に設置されている逆走防止用のスパイクのようなものだ。正しい方向に走行すれば、ほとんど気づかない。逆走すれば、遠くへ行くことはできない（そして新しいタイヤが必要になる）。

しかし、問題がある。数学者は真の一方向性関数が存在するのではないかと考えているが、そのことを証明するには至っていないのだ。彼らは、私たちが実際に使う暗号のベースとなっている厄介な数学的問題を解くことが不可能であること、あるいは極めて非現実的であることすら証明できていない。単に、問題を分解する適切な数学的手段がまだ見つかっていないだけなのかもしれない。これは、すべての暗号につきまとう難問だ。私たちのデータは、それを保護する仕組みを解読する方法を、（少なくともまだ）誰も知らないという事実によって安全が確保されているのである。 

心配しなければならないのは、現在のハッカーだけではない。セキュリティの専門家たちは、量子コンピューターというまだ具現化していない脅威について長い間警告してきた。将来、量子コンピューターは、今日の最先端の暗号のベースとなっている数学的問題を素早く解くプログラムを実行できるようになるかもしれない。そうなると、個人の金融情報や医療情報、その他の情報が危険に晒されることになる。ハッカーは、今日の暗号化されたデータを盗み出してどこかに保管しておき、新しいピッキングの技術が登場するのをただ待っているのかもしれない。

コンピューター科学者、数学者、暗号学者たちは、今日の従来型コンピューターだけでなく、未来の量子マシンからの攻撃にも耐えられる新しい暗号アルゴリズムを見つけ出そうとしている。彼らが求めているのは、従来型コンピューターや量子コンピューターからの攻撃に耐えうるほど堅牢でありながら、サイバースペースで簡単に実装できる、手強く厄介な数学的問題なのだ。

残念なことに、従来型コンピューターでも量子コンピューターでも解決するのが困難であることが証明された問題は、まだ1種類も見つかっていない（暗号の世界では、「困難な問題」とは、その解法にあまりにも膨大な数のステップやあまりにも膨大な量のコンピューティング能力を必要とする問題を指す）。もし一方向性関数が存在しないのであれば、欠陥を見つけては、巧妙なハッカーをブロックするためにより強力な暗号方式を開発するという、暗号学者たちによるモグラ叩きは無限に続くことになる。

「一方向性関数が存在するかどうかという問題は、本当に最も重要な問題です」と、イスラエルのテルアビブ大学の理論コンピューター科学者、ラファエル・パス教授は言う。この難問は1970年代、現在「計算複雑性理論」として知られる研究分野の黎明期にさかのぼる。50年以上にわたって、理論家や暗号学者は、そのような関数の存在性を証明する方法を探してきた。おそらく、私たちが一方向性であることを期待したり、そうかもしれないと思ったりしている問題は、実はもっと容易で、解ける問題なのかもしれない。

パス教授は、一方向性関数が他の多くの未解決問題とどのように関連しているかを探求している。これは、他の理論家たちを引き付けている有望な研究分野となっている。同時に、暗号の実用的な側面に重点を置く人々は、（困難性を証明できないとしても）量子コンピューターに対抗できるほど堅牢であるように思われる新たな暗号方式を求めて研究を進めている。

過去7年間、最良の候補を見つける仕事は、米国国立標準技術研究所（National Institute of Standards and Technology：NIST）が主導してきた。NISTは、一般に使用される暗号アルゴリズムの収集、テスト、標準化を担う米国の政府機関である。NISTは何十もの「ポスト量子」アルゴリズム候補を一連の厳しいテストにかけ、外部のテストに利用できるようにしてきた。その結果、候補はいくつかの最終候補に絞られた。そしてNISTは2023年8月に、量子攻撃に対抗するのに十分な堅牢性を備えていると考えられるアプローチを採用したアルゴリズムとして、「クリスタルズ・カイバー（CRYSTALS-Kyber）」が、2024年までに公式に一般利用に推奨される最初のアルゴリズムになると発表した。その後、企業や政府がデータの暗号化にこのアルゴリズムを採用することになる。

CRYSTALS-Kyberは期待に応えられるだろうか。その答えは、近い将来のサイバーセキュリティの動向を決める要素となるだろう。しかし、問題決着には程遠い。歴史が示唆するように、解読不可能性への信頼は見当違いであることがよくあり、長年にわたり、一見難攻不落に見える暗号候補が驚くほど単純な攻撃によって破られてきた。コンピューター科学者たちは、ポスト量子アルゴリズムが本当に難攻不落なのか、それとも単にそう信じられているだけなのか確信が持てず、微妙な岐路に立たされている。これは現代の暗号セキュリティの核心に関わる問題だ。

解読不可能性に関する通念と現実

秘密のメッセージの安全を確保することは、難しい数学の問題と常に結びついていたわけではない。最近まで、暗号はほとんど数学的ではなかった。古代ギリシャでは、軍事指導者たちがスキュタレーを使ってメッセージを暗号化していた。スキュタレーとは、円筒形の装置で、一見支離滅裂な文字が並ぶ細長い紙を巻きつけると隠されたメッセージが現れる。数世紀後の古代ローマの歴史家の記録には、ユリウス・カエサルが使用したとされる、メッセージの各アルファベットを3つずつ前にシフトさせる暗号が登場した（たとえば、dはaに置き換えらる）。

歴史上でも現代でも、秘密の暗号は頻繁に破られている。16世紀、スコットランド女王のメアリーは、従姉妹のエリザベス1世に幽閉されていた数十年の間、何百通もの手紙を暗号化するために、複雑な記号ベースの暗号を使用した。その手紙のほとんどは、自身の自由を確保し、王位を取り戻すことを目的としていた。彼女の目論見は成功しなかった。エリザベス1世のスパイと暗号解読者が、手紙を盗み見して解読し、コピーしたのだ。彼女の運命を決定づけた手紙の中で、メアリーは「Set the six gentlemen to work（6人の紳士に仕事をさせろ）」という6つの単語でエリザベスを暗殺する計画 …