ローカルでデコード可能なコード

ローカルにデコード可能なコード（LDC ）は、破損している可能性のあるコードワードの少数のビットを調べる（または照会する）だけで、元のメッセージの1ビットを高い確率でデコードできるエラー訂正コードです。^{[1] [2] [3]} この特性は、たとえば、情報がノイズの多いチャネルを介して送信されており、特定の時点でデータの小さなサブセットのみが必要であり、メッセージ全体を一度にデコードする必要がない状況で役立ちます。ローカルにデコード可能なコードは、ローカルにテスト可能なコードのサブセットではありませんが、両者の間には重複する部分があります。^[4]

コードワードは、コードワードに一定の冗長性を導入するアルゴリズムを使用して元のメッセージから生成されます。したがって、コードワードは常に元のメッセージよりも長くなります。この冗長性はコードワード全体に分散されており、エラーがあっても元のメッセージを高い確率で復元できます。コードワードの冗長性が高いほど、エラーに対する耐性が高まり、元のメッセージの一部を復元するために必要なクエリが少なくなります。

より正式には、- ローカルにデコード可能なコードは、 - ビットのメッセージを- ビットのコードワードにエンコードします。これにより、コードワードのビットのみを照会するランダム化デコード アルゴリズムを使用することで、最大でコードワードの の位置が破損している 場合でも、メッセージの任意のビットを確率で復元できます。${\displaystyle (q,\delta ,\epsilon )}$${\displaystyle n}$${\displaystyle x}$${\displaystyle N}$${\displaystyle C(x)}$${\displaystyle x_{i}}$${\displaystyle 1-\epsilon }$${\displaystyle q}$${\displaystyle C(x)}$${\displaystyle \delta N}$

さらに、完全に滑らかなローカルデコーダとは、破損していないコードワードへのアクセスが与えられた場合に常に正しい出力を生成することに加えて、すべての と に対して、ビットを復元するためのクエリが にわたって均一であるようなデコーダです。^[5] （表記は 集合 を表します）。非公式には、これは、任意のビットをデコードするために必要なクエリの集合がコードワード全体に均一に分布していることを意味します。 ${\displaystyle j\in [q]}$${\displaystyle i\in [n]}$${\displaystyle j^{th}}$${\displaystyle i^{th}}$${\displaystyle [N]}$${\displaystyle [y]}$${\displaystyle \{1,\ldots ,y\}}$

ローカルリストデコーダーは、ローカルデコーダーのもう1つの興味深いサブセットです。リストデコードは、コードワードが 以上の場所で破損している場合に役立ちます。ここで、 は2つのコードワード間の最小ハミング距離です。この場合、破損したコードワードからの距離内に複数のコードワードが存在する可能性があるため、元のメッセージのどれがエンコードされたかを正確に特定することはできなくなります。ただし、半径 が与えられている場合、破損したコードワード以内のコードワードにエンコードされるメッセージのセットを特定することは可能です。メッセージセットのサイズの上限は、およびによって決定できます。^[6]${\displaystyle \delta /2}$${\displaystyle \delta}$${\displaystyle \delta}$${\displaystyle \epsilon }$${\displaystyle \epsilon }$${\displaystyle \delta}$${\displaystyle \epsilon }$

ローカルにデコード可能なコードは連結することもできる。この場合、メッセージはまず 1 つの方式でエンコードされ、その結果のコードワードは別の方式で再度エンコードされる。(この文脈では、連結は学者が通常合成と呼ばれるものを指すために使用する用語であることに注意してください。 ^[5]を参照)。これは、たとえば、最初のコードがレートに関して望ましい特性を持っているが、非バイナリ アルファベットでコードワードを生成するなど、望ましくない特性を持っている場合に便利です。2 番目のコードは、非バイナリ アルファベットでの最初のエンコードの結果をバイナリ アルファベットに変換できます。最終的なエンコードは依然としてローカルにデコード可能であり、エンコードの両方のレイヤーをデコードするための追加手順が必要です。^[7]

コードのレートとは、メッセージ長とコードワード長の比率を指します。また、メッセージの 1 ビットを回復するために必要なクエリの数は、コードのクエリ複雑度と呼ばれます。 ${\displaystyle {\frac {|x|}{|C(x)|}}}$

コードの速度はクエリの複雑度と反比例しますが、このトレードオフの正確な形は大きな未解決問題です。^{[8] [9]} コードワードを1つの位置だけでクエリするLDCは存在せず、クエリの複雑度が2の場合の最適なコードワードサイズは、元のメッセージのサイズに対して指数関数的であることがわかっています。^[8] ただし、クエリの複雑度が2を超えるコードについては、厳密に下限がわかっているわけではありません。 コードワード長の側面からトレードオフにアプローチすると、コードワード長がメッセージ長に比例する唯一の既知のコードは、クエリの複雑度が[ ^{8] [更新が必要]} です。 また、コードワードが元のメッセージのサイズに対して多項式で、クエリの複雑度が多対数である中間のコードもあります。^[8]${\displaystyle k^{\epsilon}}$${\displaystyle \epsilon >0}$

局所的にデコード可能なコードは、データの伝送と保存、複雑性理論、データ構造、ランダム化解除、フォールトトレラント計算の理論、および秘密情報検索スキームに応用されています。^[9]

ローカルにデコード可能なコードは、ノイズの多いチャネルでのデータ送信に特に便利です。アダマールコード（リード・ミュラーコードの特殊なケース）は、1971年にマリナー9号によって火星の写真を地球に送信するために使用されました。5回繰り返しコード（各ビットが5回繰り返される）よりもこのコードが選ばれたのは、ピクセルあたりに送信されるビット数がほぼ同じである場合、エラー訂正の能力が高かったためです。（アダマールコードは、一般的な前方誤り訂正の傘下にあり、たまたまローカルにデコード可能であるだけです。火星からの送信をデコードするために実際に使用されたアルゴリズムは、一般的なエラー訂正方式でした。）^[10]

LDC は、時間の経過とともに媒体が部分的に破損したり、読み取りデバイスがエラーを起こしたりする可能性があるデータ ストレージにも役立ちます。どちらの場合も、LDC を使用すると、エラーが比較的少ない場合、エラーがあっても情報を回復できます。さらに、LDC では元のメッセージ全体をデコードする必要はありません。ユーザーは元のメッセージ全体をデコードする必要はなく、特定の部分だけをデコードできます。^[11]

複雑性理論におけるローカルにデコード可能なコードの応用の 1 つは、困難性の増幅です。多項式コードワード長と多対数クエリ複雑性を持つ LDC を使用すると、 最悪のケースの入力では解決が難しい関数を取り、平均的なケースの入力では計算が難しい関数を設計できます。 ${\displaystyle L:\{0,1\}^{n}\rightarrow \{0,1\}}$${\displaystyle L':\{0,1\}^{N}\rightarrow \{0,1\}}$

長さの入力だけに限定して考えると、 を長さ のバイナリ文字列 として見ることができます。ここで、各ビットは各 に対応します。一定の割合のエラーを許容する多項式長のローカルにデコード可能な多項式コードを使用して、 を表す文字列をエンコードし、長さ の新しい文字列を作成できます。この新しい文字列は、長さ の入力に関する新しい問題を定義するものと考えられます。が平均して簡単に解ける場合、つまり、入力の大部分で正しく解くことができる場合、エンコードに使用される LDC の特性により、 を使用してすべての入力で確率的に計算できます。したがって、ほとんどの入力に対する の解は、すべての入力で解くことを可能にしますが、最悪の場合の入力では難しいという仮定と矛盾します。 ^{[5] [8] [12]}${\displaystyle L}$${\displaystyle t}$${\displaystyle L}$${\displaystyle 2^{t}}$${\displaystyle L(x)}$${\displaystyle x\in \{0,1\}^{t}}$${\displaystyle C}$${\displaystyle L}$${\displaystyle 2^{O(t)}=2^{t'}}$${\displaystyle L'}$${\displaystyle t'}$${\displaystyle L'}$${\displaystyle L'}$${\displaystyle 1-\epsilon }$${\displaystyle L'}$${\displaystyle L}$${\displaystyle L'}$${\displaystyle L}$${\displaystyle L}$

プライベート情報検索スキームにより、ユーザーはデータベースを所有するサーバーから、どのアイテムが検索されたかを明らかにすることなくアイテムを取得できます。プライバシーを確​​保する一般的な方法の 1 つは、通信しない別々のサーバーを用意し、各サーバーにデータベースのコピーを保持することです。適切なスキームがあれば、ユーザーは各サーバーにクエリを実行できます。クエリは個別にはユーザーが探しているビットを明らかにしませんが、それらを合わせると、ユーザーがデータベース内の特定のビットを判別するのに十分な情報が得られます。^{[3] [11]}${\displaystyle k}$

この設定では、ローカルにデコード可能なコードが応用できることは容易にわかります。完全に滑らかな - クエリ ローカルにデコード可能なコードから - サーバ秘密情報スキームを生成する一般的な手順は次のとおりです。 ${\displaystyle k}$${\displaystyle k}$

を、 - ビットのメッセージを - ビットのコードワードにエンコードする完全に滑らかな LDC とします。前処理ステップとして、各サーバーは- ビットのデータベースをコード で エンコードするため、各サーバーは- ビットのコードワードを格納します。のビットを取得したいユーザーは、のローカル復号化アルゴリズムを使用してを計算できるような一連のクエリをランダムに生成します。ユーザーは各クエリを異なるサーバーに送信し、各サーバーは要求されたビットで応答します。次に、ユーザーは応答からを計算します。 ^{[8] [11]} 復号化アルゴリズムは完全に滑らかなので、各クエリはコードワード全体に均一に分散されます。したがって、個々のサーバーはユーザーの意図に関する情報を取得できず、サーバーが通信しない限りプロトコルは非公開です。^[11]${\displaystyle C}$${\displaystyle n}$${\displaystyle N}$${\displaystyle k}$${\displaystyle S_{1},\ldots ,S_{k}}$${\displaystyle n}$${\displaystyle x}$${\displaystyle C}$${\displaystyle N}$${\displaystyle C(x)}$${\displaystyle i^{th}}$${\displaystyle x}$${\displaystyle k}$${\displaystyle q_{1},\ldots q_{k}}$${\displaystyle x_{i}}$${\displaystyle C(x)_{q_{1}},\ldots C(x)_{q_{k}}}$${\displaystyle A}$${\displaystyle C}$${\displaystyle A}$${\displaystyle x_{i}}$${\displaystyle q_{j}}$

アダマール(またはウォルシュ-アダマール) コードは、長さ の文字列を長さ のコードワードにマッピングする、単純なローカル デコード可能なコードの例です。文字列のコードワードは次のように構成されます。すべての に対して、コードワードの ビットはに等しくなります(mod 2)。すべてのコードワードは、他のすべてのコードワードとのハミング距離が であることが簡単にわかります。 ${\displaystyle k}$${\displaystyle 2^{k}}$${\displaystyle x\in \{0,1\}^{k}}$${\displaystyle a_{j}\in \{0,1\}^{k}}$${\displaystyle j^{th}}$${\displaystyle x\odot a_{j}}$${\displaystyle x\odot y=\sum \limits _{i=1}^{k}x_{i}y_{i}}$${\displaystyle {\frac {n}{2}}}$

ローカル復号アルゴリズムのクエリ複雑度は 2 で、コードワードのビットの破損が 未満であれば、元のメッセージ全体を高い確率で復号できます。 の場合、コードワードの破損箇所が一部であれば、ローカル復号アルゴリズムは確率 で元のメッセージのビットを復元できます。 ${\displaystyle {\frac {1}{4}}}$${\displaystyle \rho <{\frac {1}{4}}}$${\displaystyle \rho}$${\displaystyle i^{th}}$${\displaystyle 1-2\rho }$

証明: コードワードとインデックスが与えられた場合、元のメッセージのビットを復元するアルゴリズムは次のように機能します。 ${\displaystyle H}$${\displaystyle i}$${\displaystyle i^{th}}$${\displaystyle x}$

の位置が 1 で、他の位置が 0 であるのベクトル を参照します。の場合、は に対応する の1 つのビットを表します。 アルゴリズムはランダム ベクトルとベクトル(ここで はビット単位の XORを表します) を選択します。 アルゴリズムは(mod 2) を出力します。 ${\displaystyle e^{j}}$${\displaystyle \{0,1\}^{k}}$${\displaystyle j^{th}}$${\displaystyle y\in \{0,1\}^{k}}$${\displaystyle f(y)}$${\displaystyle H}$${\displaystyle x\odot y}$${\displaystyle y\in \{0,1\}^{k}}$${\displaystyle y'=y\oplus e^{i}}$${\displaystyle \oplus}$${\displaystyle f(y)\oplus f(y')}$

正確性: 直線性により、

${\displaystyle (x\odot y)\oplus (x\odot y')=(x\odot y)\oplus (x\odot (y\oplus e^{i}))=(x\odot y)\oplus (x\odot y)\oplus (x\odot e^{i})=x\odot e^{i}}$

しかし、したがって、と が良好な確率で存在することを示す必要があるだけです。 ${\displaystyle (x\odot e^{i})=x_{i}}$${\displaystyle f(y)=x\odot y}$${\displaystyle f(y')=x\odot y'}$

と は一様分布しているので（従属関係にあるにもかかわらず）、和集合はおよび が少なくとも の確率でとなることを意味します。注: 成功の確率を高めるために、異なるランダムベクトルを使用して手順を繰り返し、多数決をとることができます。 ^[13]${\displaystyle y}$${\displaystyle y'}$${\displaystyle f(y)=x\odot y}$${\displaystyle f(y')=x\odot y'}$${\displaystyle 1-2\rho }$

リード・マラー符号のローカル復号化の背後にある主な考え方は、多項式補間です。リード・マラー符号の背後にある重要な概念は、変数上の次数 の多変数多項式です。メッセージは、一連の定義済みポイントでの多項式の評価として扱われます。これらの値を符号化するために、多項式がそれらから外挿され、コードワードはすべての可能なポイントでのその多項式の評価です。高レベルでは、この多項式のポイントを復号化するために、復号化アルゴリズムは、対象のポイント を通過する直線上のポイントのセットを選択します。次に、コードワードに対して 内のポイントでの多項式の評価を照会し、その多項式を補間します。その後、 を生成するポイントで多項式を評価するのは簡単です。この回りくどい評価方法は、(a) 同じポイントを通る異なる直線を使用してアルゴリズムを繰り返すことで正確性の確率を高めることができ、(b) 照会がコードワード全体に均一に分散されるため便利です。 ${\displaystyle d}$${\displaystyle l}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle x}$

より正式には、 を有限体とし、 をとなる数とします。パラメータを持つリード・ミュラー符号は関数 RM です。これは、の全次数上のすべての-変数多項式を のすべての入力上の の値にマッピングします。つまり、入力は定義済み点の値 の補間によって指定された形式の多項式であり 、出力はすべての に対するシーケンスです。^[14]${\displaystyle \mathbb {F} }$${\displaystyle l,d}$${\displaystyle d<|\mathbb {F} |}$${\displaystyle \mathbb {F} ,l,d}$${\displaystyle \mathbb {F} ^{\binom {l+d}{d}}\rightarrow \mathbb {F} ^{|\mathbb {F} |^{l}}}$${\displaystyle l}$${\displaystyle P}$${\displaystyle \mathbb {F} }$${\displaystyle d}$${\displaystyle P}$${\displaystyle \mathbb {F} ^{l}}$${\displaystyle P(x_{1},\ldots ,x_{l})=\sum \limits _{i_{1}+\ldots +i_{l}\leq d}c_{i_{1},\ldots ,i_{l}}x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots x_{l}^{i_{l}}}$${\displaystyle {\binom {l+d}{d}}}$${\displaystyle \{P(x_{1},\ldots ,x_{l})\}}$${\displaystyle x_{1},\ldots ,x_{l}\in \mathbb {F} }$

点 における次数多項式の値を復元するために、ローカルデコーダはを通るランダムなアフィン直線を射出します。次に、その直線上の点を選択し、それを使用して多項式を補間し、結果が となる点で評価します。これを行うために、アルゴリズムはベクトルを一様にランダムに選択し、を通る直線を検討します。アルゴリズムはの任意のサブセット ( ) を選択し、すべての について点に対応するコードワードの座標を照会して値 を取得します。次に、多項式補間を使用して、すべてのについてとなる次数以下の一意の単変量多項式を復元します。次に、 の値を取得するために、 を評価します。元のメッセージの単一の値を復元するには、多項式を定義する点の 1 つを選択します。^{[8] [14]}${\displaystyle d}$${\displaystyle w\in \mathbb {F} ^{n}}$${\displaystyle w}$${\displaystyle d+1}$${\displaystyle w}$${\displaystyle v\in \mathbb {F} ^{n}}$${\displaystyle L=\{w+\lambda v\mid \lambda \in \mathbb {F} \}}$${\displaystyle w}$${\displaystyle S}$${\displaystyle \mathbb {F} }$${\displaystyle |S|=d+1}$${\displaystyle w+\lambda v}$${\displaystyle \lambda \in S}$${\displaystyle \{e_{\lambda }\}}$${\displaystyle h}$${\displaystyle d}$${\displaystyle h(\lambda )=e_{\lambda }}$${\displaystyle \lambda \in S}$${\displaystyle w}$${\displaystyle h(0)}$${\displaystyle w}$

各クエリはコードワード全体に均一にランダムに分布する。したがって、コードワードが最大でも一部の場所で破損している場合、和集合の境界により、アルゴリズムが破損していない座標のみをサンプリングする（したがってビットを正しく復元する）確率は少なくとも である。^{[8]他の復号アルゴリズムについては、 [8]} を参照。${\displaystyle \delta }$${\displaystyle 1-(d+1)\delta }$

• 個人情報の検索
• 線形暗号解読