テキスト メッセージを送信したり、CD を再生したり、クラウドにファイルを保存したりしたことがあるなら、エラー修正の恩恵を受けたことがあるでしょう。この革新的なアイデアの起源は 1940 年代にまで遡ります。当時、研究者たちは、後で破損した内容を簡単に元に戻せる形式であらゆるメッセージを書き換えることが可能であることに初めて気づきました。

研究者たちは長年にわたり、さまざまな方法でデータをエンコードし、さまざまな手順を使用してエラーを修正する、誤り訂正コードと呼ばれる多くの独創的なスキームを開発してきました。しかし、理論的なコンピューター科学者にとって、いわゆるローカルで修正可能なコードほど説得力のあるものはほとんどありません。これらのコードには、ほぼ矛盾しているように聞こえる 2 つの特性が同時に備わっています。つまり、コード化されたデータをほんの数箇所読み取るだけでエラーを修正できますが、攻撃者はコードを選択的に改ざんしてこの修正手順を無効にすることはできません。まるで、他の数ページをちらっと見るだけで、本から切り取ったどんなページも元に戻せるかのようです。

「それは実に魔法のような現象だ」と彼は言った トム・ガー、ケンブリッジ大学のコンピューター科学者。 「アプリオリに、そのような数学的オブジェクトが存在し得ることはまったく明らかではありません。」

しかし、この魔法には莫大な代償が伴います。ローカルで修正可能なコードの既知の例は、非常に非効率なものだけです。メッセージをエンコードすると、その長さも飛躍的に長くなります。この方法で書籍全体をエンコードすると、非常に扱いにくくなります。

コンピュータ科学者は、局所的に修正可能なより優れたコードが可能かどうかについて長い間疑問を抱いてきました。彼らは、この厳しい制限によってこれらのコードが理解しやすくなるのではないかと期待して、エラーを修正するために 20 つのクエリのみを使用するコードに特に焦点を当ててきました。しかし、この単純なケースでさえ、XNUMX年以上研究者を悩ませてきました。

今ではコンピューター科学者 プラヴェシュ・コタリ カーネギーメロン大学の博士とその大学院生 ピーター・マノハール ついに 証明 このような指数関数的なコストを回避する、ローカルで修正可能な 3 クエリのコードを構築することは不可能です。これは否定的な結果かもしれませんが、誤り訂正の限界を明らかにするものは何であれ、特に局所的に訂正可能なコードの数学が通信から遠く離れた領域で現れるため、研究者にとっては刺激的なものです。

「この結果はすごいですね」 シュバンギ・サラフ、トロント大学のコンピューター科学者。 「それは大きな進歩です。」

数の強さ

エラー訂正を理解するには、保護したいデータを一連のビット、つまり 0 と 1 として想像してください。このモデルにおけるエラーとは、ランダムな変動によるものか、意図的な改ざんによるものであるかに関係なく、0 から 1 への望ましくない反転、またはその逆のことを指します。

友人にメッセージを送信したいが、エラーによって意味が変わってしまうのではないかと心配だとします。簡単な方法の 0 つは、メッセージ内の各 000 を 1 に置き換え、各 111 を 110 に置き換えることです。友人がメッセージの一部に同じビットが 111 つ連続して含まれていないのを見れば、エラーが発生したことがわかります。また、エラーがランダムで比較的まれである場合、000 の文字列は破損した XNUMX よりも破損した XNUMX である可能性がはるかに高くなります。各トリプレット内の単純な多数決で、ほとんどのエラーを修正するのに十分です。

繰り返しコードと呼ばれるこのスキームには、単純さという長所がありますが、それ以外にお勧めできる点はほとんどありません。まず、比較的まれなエラーに対処するためだけに、すべてのメッセージの長さを 3 倍にする必要があり、2 つの隣接するエラーが発生する可能性が十分にある場合は、さらに冗長性が必要になります。さらに悪いことに、攻撃者が積極的にコードを妨害しようとした場合など、エラーがランダムでない場合には、すぐに役に立たなくなります。反復コードでは、特定のビットを修正するために必要なすべての情報が他のわずか数ビットに保存されているため、標的型攻撃に対して脆弱なままになります。

幸いなことに、多くのエラー訂正コードはより適切に機能します。有名な例としては、 リードソロモン符号、メッセージを多項式 (次のような数式) に変換することで機能します。 x² + 3x + 2 は、異なる項を加算して構成され、それぞれに変数 (例: x) を別の累乗します。リードソロモンコードを使用してメッセージをエンコードするには、メッセージ内の各文字に 1 つの項を含む多項式を構築し、その多項式をグラフ上に曲線としてプロットし、曲線上にある点の座標を保存します (少なくとも 1 つ以上の点を取得します)。文字数よりポイント）。エラーによりこれらの点のいくつかが曲線から外れる可能性がありますが、エラーが多すぎない場合は、1 つの多項式曲線だけがほとんどの点を通過します。その曲線はほぼ確実に真のメッセージに対応しています。

リードソロモン コードは非常に効率的です。エラーを修正するために追加のポイントをいくつか保存するだけで済むため、エンコードされたメッセージは元のメッセージよりわずかに長くなるだけです。また、どこかのエラーを修正するために使用される情報がエンコードされたメッセージ全体に分散されるため、繰り返しコードに大惨事をもたらすような標的を絞った破壊に対しても脆弱ではありません。

世界的に考えて、局所的に作用

リードソロモンコードの強さは相互接続性に由来します。しかし、まさにその相互関連性により、エンコードされたメッセージ内の単一のエラーを修正するには、全体を読まないと解決できません。コミュニケーションの文脈では、これは問題には思えないかもしれません。メッセージを送信している場合、おそらく受信者にすべてを読んでもらいたいと思うでしょう。しかし、これは、エラー訂正のもう 1 つの主要な用途であるデータ ストレージにおいては問題となる可能性があります。

ユーザーの電子メールをクラウド、つまり膨大な数のサーバーに保存している企業を考えてみましょう。電子メールのコレクション全体を 1 つの長いメッセージと考えることができます。ここで、1 台のサーバーがクラッシュしたとします。リードソロモン コードを使用すると、失われた 1 つのサーバーからメールを復元するには、すべてのエンコードされたデータを含む大規模な計算を実行する必要があります。 「すべてを見なければならないだろう」と彼は言った ジーヴ・ドヴィル、プリンストン大学のコンピューター科学者。 「それは何十億ものメールになる可能性があり、非常に長い時間がかかる可能性があります。」

研究者は、エンコードされたメッセージの一部のみを使用してデータを送信するコードを説明するために「ローカル」という用語を使用します。 スポットエラー または修正してください。単純な繰り返しコードにはこのような局所的な特徴がありますが、それがまさに改ざんに対して非常に脆弱な理由です。対照的に、ローカルで修正可能なコードは両方の長所を利用できます。リードソロモン コードの回復力を高める相互接続性を失うことなく、わずか数回のクエリで任意のビットのエラーを修正できます。

「これは非常に厳しい概念です」とコタリ氏は言う。

局所的に訂正可能なコードの最も有名な例は、1954 年に数学者によって発明された由緒あるエラー訂正コードのバージョンです。 デビッドミュラー & アーヴィング・リード (彼はリードソロモンコードの開発にも貢献しました)。リード・ソロモン符号と同様に、リード・ミュラー符号は、多くの項を加算した多項式を使用して長いメッセージを符号化します。

リードソロモン符号で使用される多項式には、単一の変数が含まれます。 xしたがって、より多くの項を追加する唯一の方法は、より高次の累乗を使用することです。 x。その結果、多くの点を調べなければ特定できない、多くの揺れを含む曲線が生成されます。リード・ミュラー コードでは、代わりに、各項に複数の変数を乗算したものを含めることができる多項式が使用されます。変数が増えると、それらを組み合わせる方法が増えることになり、個々の変数をそれほど高いべき乗せずに多項式の項の数を増やす方法が提供されます。

リード・ミュラー符号は非常に柔軟です。多項式に現れる最高べき乗を増やすか、変数の数を増やすか、あるいはその両方を行うことによって、より長いメッセージをエンコードできます。リードミュラー コードをローカルで修正可能にするには、各変数の最大検出力を小さな定数値に制限し、変数の数だけを増やすことで長いメッセージを処理します。

特に 2 クエリのローカル修正可能なコードの場合、その最大電力は XNUMX に設定されます。その場合、個々の変数に関する限り、メッセージをエンコードした多項式は単純な放物線を描きます。放物線の正確な形状を判断するには、曲線の XNUMX 点を調べるだけで済みます。さらに、変数が多い場合にはそのような放物線が多数存在し、そのいずれかを使用してエラーを修正できます。これが、リードミュラーコードの回復力を高めている理由です。

残念ながら、リード・ミュラー コードには重大な欠点があります。メッセージのエンコードに必要なビット数は、変数の数に応じて指数関数的に増加します。ほんの少数のクエリでエラーを修正する高度にローカルなコードが必要な場合は、長いメッセージ用に多くの変数が必要になり、Reed-Muller コードは実際にはすぐに役に立たなくなります。

「この場合の指数関数性は非常に悪いです」とドヴィル氏は語った。しかし、それは避けられないことでしょうか？

修正可能かデコード可能か?

コンピューター科学者たちは、局所的に修正可能なより効率的なコードを見つけようと試みましたが失敗し、そのようなコードはまったく不可能ではないかと疑い始めました。 2003 年に XNUMX 人の研究者が 証明 たった 2 つのクエリを使用してリード マラー コードを破る方法はないということです。しかし、それは誰でもできることです。

「3 つになると、私たちの知識は非常に大ざっぱになります」とコタリ氏は言います。

次のブレークスルーは問題をさらに複雑にします。に掲載された2つの論文で、 2008 & 2009、コンピューター科学者のセルゲイ・エカニンとクリム・エフレメンコは、リード・ミュラー コードよりも効率的な 3 クエリ コードを構築する方法を示しましたが、これらのコードは局所的に完全に修正可能ではありませんでした。代わりに、ローカルデコード可能性と呼ばれる微妙に異なるプロパティがありました。

違いを理解するために、ユーザーのデータを 1 つの長いメッセージに結合し、エラー修正コードを使用して保護するクラウド ストレージ プロバイダーをもう一度想像してみましょう。ローカルで修正可能なコードとローカルでデコード可能なコードはどちらも、わずか数回のクエリで元のメッセージの任意のビットのエラーを修正できます。

ただし、すべてのエラー訂正コードには、元のメッセージにはなかった余分なビットも必要です。メッセージをエンコードすると長くなるのはこのためです。 2 種類のコードは、これらの追加ビットの処理方法が異なります。ローカルでデコード可能なコードは、これらのビットのエラーを修正するために必要なクエリの数については保証しません。しかし、ローカルで修正可能なコードでは、余分なビットのエラーは、元のメッセージのビットのエラーとまったく同じ方法で修正できます。

「ユーザーの元のデータであろうと、冗長性やチェック情報であろうと、保存するものはすべてローカルで修正できます。」と同氏は述べています。 マドゥ スーダン、ハーバード大学のコンピューター科学者。

原理的には異なりますが、ローカル修正可能性とローカルデコード可能性は、2008 年以前は常に実際には互換性があるように見えました。ローカルでデコード可能な既知のコードはすべて、ローカルで修正可能でもありました。エカニンとエフレメンコの発見により、この XNUMX つの症状の間に根本的な違いがある可能性が高まりました。あるいは、エカニンとエフレメンコのコードを修正して、ローカルで修正できるようにすることも可能だったかもしれません。そうすれば、XNUMX つの条件は再び同等の立場になりますが、それはまた、XNUMX クエリのローカル修正可能なコードがどれほど効率的に得られるかについて研究者が誤解していたことを意味します。いずれにせよ、これまでの常識は変わらなければなりません。

ロジックの借用

コタリ氏とマノハール氏は、コンピューターサイエンスの別の分野、いわゆる制約充足問題の研究の手法を採用することで、最終的にその緊張を解決した。友人グループとディナーの計画を調整しようとすることは、ある種の制約満足の問題です。誰もが受け入れる選択肢と拒否する選択肢を持っています。あなたの仕事は、全員が満足する計画を見つけるか、そのような計画がない場合はできるだけ早くそれを見つけることです。

これら 2 つの考えられる結果の間には、本質的に非対称性があります。受け入れられる解決策を見つけるのは簡単ではないかもしれませんが、一度それを見つければ、それが機能することを他の人に納得させるのは簡単です。しかし、問題が本当に「満足できない」ものであるとわかっていても、それを証明する例がないかもしれません。

2021年、コタリ氏とマノハール氏は、カリフォルニア大学バークレー校のベンカテサン・グルスワミ氏とともに、 大きなブレークスルー それらの困難な満たされないケースを特定するための新しい理論的手法を使用した制約満足問題の研究。彼らは、この新しい方法が他の問題を解決するための強力なツールになるのではないかと考え、グルスワミの大学院生であるオマール・アルラビア氏は、ローカルでデコード可能な 3 つのクエリのコードを検討することを提案しました。

「これはいわば、ハンマーを手に持った釘のようなものでした」とコタリさんは語った。

エカニンとエフレメンコの驚くべき結果は、ローカルで復号可能な 3 クエリのコードがリード・ミュラー コードよりも効率的である可能性があることを示していました。しかし、彼らのコードは可能な限り最良のものだったのでしょうか、それとも 3 クエリのローカルでデコード可能なコードはさらに効率的になる可能性があるのでしょうか?コタリ氏、マノハール氏、グルスワミ氏、アルラビア氏は、自分たちの新しい技術が、そのようなコードの効率性の限界を証明できるかもしれないと考えた。彼らの計画は、与えられたサイズの、考えられるすべての 3 クエリのローカルでデコード可能なコードの構造を網羅する論理式を構築し、それが満たされないことを証明して、そのようなコードが存在し得ないことを示すことでした。

2022 人の研究者は XNUMX 年にその方向への第一歩を踏み出し、 新しい制限 3 クエリのローカルでデコード可能なコードの最大効率について。この結果は、研究者が他の技術で達成できたものをはるかに超えていましたが、エカニンとエフレメンコのコードよりも効率的なコードがすべて排除されるわけではありませんでした。

コタリ氏とマノハール氏は、さらに前進できるのではないかと考えた。しかし、マノハール氏が、この手法がローカルで復号可能なコードよりもローカルで修正可能なコードの場合にさらにうまく機能する可能性があることを示す簡単な裏計算を書き留めるまで、進歩は停滞しました。

数カ月後、楽観的すぎたのではないかと心配するような誤ったスタートが何度もあった後、この技術はついにその約束を果たしました。コタリ氏とマノハール氏は、研究者らが疑っていたように、ローカルで修正可能な 3 クエリのコードがリード・ミュラー コードよりも明らかにうまく機能することは不可能であることを証明しました。この指数関数的なスケーリングは根本的な制限です。彼らの結果は、局所的な修正可能性と局所的な解読可能性が、表面的には似ていても、根本的なレベルで実際には異なるという劇的な実証でもありました。後者の方が前者よりも明らかに実現しやすいのです。

Kothari 氏と Manohar 氏は、現時点ではほとんど知られていない 3 つ以上のクエリを実行できるコードを研究するためにその技術を拡張したいと考えています。そして、誤り訂正理論の進歩は、一見無関係に見える他の分野にも影響を与えることがよくあります。特に、ローカルで修正可能なコードは、 プライベートデータベースの検索 暗号学における証明への 組み合わせ論の定理。コタリ氏とマノハール氏の技術がこれらのさまざまな分野にどのような影響を与えるかを語るのは時期尚早だが、研究者らは楽観視している。

「ここには本当に美しい新しいアイデアがあります」とドヴィル氏は語った。 「可能性はたくさんあると思います。」