暗号化のトリックで難しい問題が少し簡単になる |クアンタマガジン

難しい問題を解決する最善の方法は何ですか?これは、計算複雑性理論と呼ばれるコンピューター サイエンスのサブ分野の中心となる問題です。答えるのは難しい質問ですが、裏返すと簡単になります。最悪のアプローチは、ほとんどの場合試行錯誤であり、うまくいくまで考えられる解決策を組み込むことになります。しかし、いくつかの問題については、単に代替手段がないようです。最悪のアプローチが最良のアプローチでもあるのです。

研究者らは、本当にそうなのかどうかについて長い間疑問を抱いてきた、と述べた。 ラーフル・イランゴ, マサチューセッツ工科大学で複雑性理論を研究している大学院生。 「『推測と確認が最適な問題はありますか?』と尋ねることもできます。」

複雑性理論の専門家は多くの計算問題を研究しており、難しい問題であっても、純粋な試行錯誤よりも解決策を見つけるのが少し簡単になる、ある種の賢い手順またはアルゴリズムを認めていることがよくあります。数少ない例外の中には、いわゆる圧縮問題があり、その目的はデータセットの最短の記述を見つけることです。

しかし昨年11月、2つの研究者グループが 単独で 発見 圧縮問題に対する別のアルゴリズム。考えられるすべての答えをチェックするよりもわずかに高速です。新しいアプローチは、25 年前に暗号学者によって別の問題を攻撃するために発明されたアルゴリズムを適応させることで機能します。制限が XNUMX つだけあります。データ セットのサイズに合わせてアルゴリズムを調整する必要があります。

「それらは本当に美しく、重要な結果です」と述べました。 エリック・アレンダー、ラトガース大学の理論コンピューター科学者。

硬度の定義

新しい結果は、複雑性理論の出現よりずっと前に、ソ連で最初に研究された問題を調査した最新のものである。 「私が小学生になる前に、ロシアの人々はこれを策定していました」とアレンダー氏は語った。

これらソ連の研究者たちが研究した特定の計算問題は、最小回路サイズ問題と呼ばれるもので、コンピュータハードウェアの設計者が常に直面する問題に似ている。電子回路がどのように動作するかについての完全な仕様が与えられた場合、その仕事を行う最も単純な回路を見つけることができますか? 「徹底的な検索」にほぼ相当するロシア語の「ペレボール」なしにこの問題を解決する方法を誰も知りませんでした。

最小回路サイズの問題は、圧縮問題の一例です。回路の動作を長いビット列 (0 と 1) で記述し、より少ないビットを使用して同じ動作を再現する方法があるかどうかを検討できます。考えられるすべての回路レイアウトをチェックするには時間がかかり、文字列内のビット数が増えるにつれて時間がかかります。

この種の指数関数的な増加は、難しい計算問題の特徴です。しかし、すべての難しい問題が同じように難しいわけではありません。実行時間は依然として指数関数的に増加しますが、完全な検索よりも高速なアルゴリズムを備えたものもあります。現代の言葉で言えば、最も重要な問題は、圧縮問題に対してそのようなアルゴリズムが存在するかどうかです。

1959 年、セルゲイ ヤブロンスキーという著名な研究者は、最小回路サイズの問題を解決するには徹底的な探索が実際に唯一の方法であることを証明したと主張しました。しかし、彼の証明にはいくつかの抜け穴が残されていました。当時欠陥に気づいた研究者もいたが、ヤブロンスキーは他の研究者のほとんどがペレボールの問題に取り組むのを思いとどまらせるほどの影響力を持っていた。

その後数十年間、圧縮問題を研究する研究者はほとんどおらず、ペレボールの問題は主に複雑性理論の先史時代の脚注として知られていました。この問題に広く注目が集まるようになったのは、研究者らが圧縮の問題と暗号の基礎との間に興味深い関連性があることを発見した後、つい最近のことです。

一方通行

最新の暗号化では、難しい計算問題を使用して秘密メッセージを保護します。ただし、計算の強度が役立つのは、非対称である場合、つまり、コード化されたメッセージを解読するのは難しくても、そもそもメッセージをエンコードするのは難しくない場合に限られます。

すべての暗号化スキームにおいて、この非対称性の原因は、入力ビット文字列を同じ長さの出力文字列に変換する一方向関数と呼ばれる数学的オブジェクトです。一方向関数への入力が与えられると、出力を計算するのは簡単ですが、出力が与えられると、関数を反転する、つまりリバース エンジニアリングして入力を回復するのは困難です。

「暗号学者は、非常に効率的に計算可能で、逆変換が非常に困難な一方向関数を本当に望んでいます」とアレンダー氏は言う。多くの数学関数にはこの性質があるようで、これらの関数を逆にすることの難しさは、さまざまな計算問題を解くことが明らかに難しいことに起因しています。

残念ながら、暗号学者には、これらの関数のいずれかが本当に反転が難しいかどうかはわかりません。実際、真の一方向関数が存在しない可能性もあります。この不確実性は依然として存在します。なぜなら、複雑性理論家は 50年間奮闘した 一見難しい問題が実際には難しいことを証明するために。もしそうでなく、研究者がこれらの問題に対する超高速アルゴリズムを発見した場合、それは暗号学にとって悲惨なことになるでしょう。一方通行の道路でスピード違反の車を突然両方向に誘導するのと同じです。

計算の難しさの包括的な理解は依然としてとらえどころのないものですが、暗号学者は最近、一方向性関数の統一理論に向けて刺激的な進歩を遂げています。 2020 年に、テルアビブ大学の暗号学者が大きな一歩を踏み出しました。 ラファエルパス と彼の大学院生 ヤンイー・リウ 一方向性関数が存在することを証明した 密接につながっている 時間制限のあるコルモゴロフ複雑性問題と呼ばれる特定の圧縮問題に対処します。

その 1 つの問題がほとんどの入力に対して実際に解決するのが難しい場合、パスとリューの結果は、証明が難しい一方向関数を構築する方法のレシピを生成します。この関数は、他の計算問題がはるかに簡単であることが判明した場合でも、安全であることが保証されています。研究者が予想していたよりも。しかし、時間制限のあるコルモゴロフの複雑さの問題を解決するための高速アルゴリズムがあれば、暗号化は運命づけられており、どんな関数も簡単に逆転できます。この問題の難易度に基づく一方向関数は、可能な限り最も安全な関数、つまりすべてを支配する一方向関数です。

データ構造に基づく構築

パスとリューの発見は、暗号の基礎をより深く理解するために複雑性理論を使用する一連の研究の最新章でした。しかし、それは、その関係を逆転させる方法も示唆しました。時間制限のあるコルモゴロフ複雑性問題と関数逆転が等価であるということは、どちらかの問題についての洞察があれば、もう一方の問題についてより多くのことが明らかになる可能性があることを意味します。暗号学者は、暗号化手法の弱点をより深く理解するために、数十年にわたって関数反転アルゴリズムを研究してきました。研究者たちは、これらのアルゴリズムが複雑性理論における長年の疑問の解決に役立つのではないかと考え始めました。

多くの計算問題と同様、関数反転は徹底的な探索によって解決できます。出力文字列が与えられた場合、正しい答えが得られるものが見つかるまで、考えられるすべての入力を関数に接続するだけです。

1980 年、暗号学者のマーティン ヘルマンは、これ以上の改善が可能かどうかの研究を開始しました。これは、ソ連の数学者たちが数十年前に圧縮問題について抱いていたのと同じ質問でした。ヘルマン 発見 はい、それは可能です。データ構造と呼ばれる数学的オブジェクトを使用して、事前に追加の作業を行うつもりであれば可能です。

データ構造は基本的に、反転される関数に関する情報を格納するテーブルであり、データ構造を構築するには、戦略的に選択された特定の入力に対する関数の出力を計算する必要があります。これらすべての計算には「非常に長い時間がかかる可能性がある」と述べた。 ライアン·ウィリアムズ、MITの複雑性理論家。 「しかし、考え方としては、これは一度限り、そして最後まで行われるということです。」多くの異なる出力を与えて同じ関数を逆にしようとしている場合、たとえば、同じ方法で暗号化された多くの異なるメッセージをデコードする場合、事前にこの作業を行うことは価値があるかもしれません。

もちろん、追加の情報を保存するにはスペースが必要になるため、この戦略を極端に実行すると、どのコンピュータにも収まらない高速なプログラムが作成される可能性があります。 Hellman は、彼のアルゴリズムがスペースをあまり取らずに、網羅的な検索よりわずかに速く、ほとんどの関数を反転できるようにする賢いデータ構造を設計しました。そして 2000 年に、暗号学者のアモス・フィアットとモニ・ナオールが で すべての関数に対するヘルマンの引数。

2020 年のパスとリューの躍進の後、これらの古い結果が突然新たに意味のあるものになりました。 Fiat-Naor アルゴリズムは、網羅的な検索よりも速く任意の関数を反転できます。圧縮の問題にも効果があるでしょうか?

不均一

この問題を最初に提起した研究者は複雑性理論家でした ラフル・サンタナム オックスフォード大学の教授とその大学院生 ハンリン・レン。彼らはそうしました 2021紙 これは、圧縮の問題と関数の反転が研究者が認識していたよりもさらに複雑に絡み合っていることを証明しました。

パスとリューは、時間制限のあるコルモゴロフの複雑性問題が難しい場合、関数の反転も難しいはずであり、その逆も同様であることを証明しました。しかし、問題は難しい場合もありますが、それでも徹底的な検索よりも少し優れた解決策が認められます。 Santhanam と Ren は、ある問題に対して徹底的な検索が必要かどうかと、別の問題に対しても必要かどうかの間に密接な関係があることを示しました。

彼らの結果は、「均一」アルゴリズムと「非均一」アルゴリズムと呼ばれる、研究者がよく研究する 20 つの広範なクラスのアルゴリズムに対して異なる意味を持ちました。統一アルゴリズムは、すべての入力に対して同じ手順に従います。たとえば、数値のリストを並べ替える統一プログラムは、リストにエントリが 20,000 個であっても XNUMX 個であっても、同じように機能します。不均一アルゴリズムでは、代わりに、異なる長さの入力に対して異なる手順が使用されます。

Fiat-Naor アルゴリズムで使用されるデータ構造は、常に特定の関数に合わせて調整されます。 10 ビット文字列をスクランブルする関数を反転するには、スクランブルが同じ方法で行われる場合でも、20 ビット文字列をスクランブルする関数を反転する場合に必要なデータ構造とは異なるデータ構造が必要です。そのため、Fiat-Naor は不均一なアルゴリズムになります。

Santhanam と Ren の結果は、Fiat-Naor アルゴリズムを圧縮問題を解決するアルゴリズムに変換できる可能性があることを示唆しました。しかし、アルゴリズムをある問題から別の問題に適応させるのは簡単ではなかったので、彼らはその問題をそれ以上追求しませんでした。

1年後、ナオールの暗号化への貢献を祝うワークショップでフィアットが古典的なアルゴリズムについて講演したのを聞いた後、パスは同じアイデアに思い当たった。 「関数反転を使用するというこのアイデアは、それ以来私の頭の片隅にありました」と彼は言いました。彼はその後、テルアビブ大学の研究者とともにこの問題に本格的に取り組み始めました。 ノーム・メイザー.

一方、イランゴ氏は、カリフォルニア州バークレーのサイモンズ理論コンピューティング研究所を訪問した際に、サンタナム氏を含む他の研究者らと議論した後、この問題を攻撃することを思いついた。 「それは、単に物事を投げかけているような、非常に偶然な会話の1つから生まれました」とサンタナムは言いました。イランゴは後にウィリアムズと協力し、 平原修一、東京の国立情報学研究所の複雑性理論の専門家。

難しい部分は、圧縮問題を解決するために、Fiat-Naor アルゴリズムの中心となるデータ構造を不均一アルゴリズムに埋め込む方法を見つけることでした。この種の埋め込みを行うための標準的な手順はありますが、アルゴリズムの速度が低下し、徹底的な検索に対する利点が失われてしまいます。 2 つのチームは、Fiat-Naor データ構造を組み込むより賢い方法を発見し、すべての入力に対して機能し、徹底的な検索よりも高速な圧縮問題のアルゴリズムを取得しました。

2 つのアルゴリズムの詳細は若干異なります。 Ilango とその共著者によるものは、たとえ検索を最も単純な可能性に限定したとしても、徹底的な検索よりも高速であり、時間制限のあるコルモゴロフの複雑さ、最小回路サイズの問題など、すべての圧縮問題に適用されます。しかし、中心となる考え方はどちらのアルゴリズムでも同じでした。暗号化の技術は、この新しい領域でその価​​値を証明しました。

反転収束

不均一なアルゴリズムの新しい証明により、当然の疑問が生じます。「均一なアルゴリズムはどうなるのでしょうか?」圧縮問題を使用して徹底的に検索するよりも早く圧縮問題を解決する方法はありますか?

最近の一連の結果は、そのようなアルゴリズムは任意の関数を反転するための統一アルゴリズムと同等であることを示唆しています。これは、暗号学者が何十年も探し求めて失敗してきたものです。そのため、多くの研究者はその可能性は低いと考えています。

「とても驚かれるでしょう」とサンタナムさんは語った。 「それには全く新しいアイデアが必要になるでしょう。」

しかしアレンダー氏は、研究者はその可能性を軽視すべきではないと述べた。 「私にとって有効な仮説は、何かを行うのに不均一な方法がある場合、均一な方法がある可能性が非常に高いということです」と彼は言いました。

いずれにせよ、この研究により、複雑性理論家は暗号における古い疑問に新たに興味を持つようになりました。 ユヴァル・アイシャイイスラエルのハイファにあるテクニオンの暗号学者は、それが最もエキサイティングな点だと語った。

「さまざまなコミュニティ間の関心がこのように集まっているのを見ることができて本当にうれしいです」と彼は言いました。 「それは科学にとって素晴らしいことだと思います。」