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

ローカルにデコード可能なコード（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]

LDCs are also useful for data storage, where the medium may become partially corrupted over time, or the reading device is subject to errors. In both cases, an LDC will allow for the recovery of information despite errors, provided that there are relatively few. In addition, LDCs do not require that the entire original message be decoded; a user can decode a specific portion of the original message without needing to decode the entire thing.^[11]

One of the applications of locally decodable codes in complexity theory is hardness amplification. Using LDCs with polynomial codeword length and polylogarithmic query complexity, one can take a function ${\displaystyle L:\{0,1\}^{n}\rightarrow \{0,1\}}$ that is hard to solve on worst case inputs and design a function ${\displaystyle L':\{0,1\}^{N}\rightarrow \{0,1\}}$ that is hard to compute on average case inputs.

Consider ${\displaystyle L}$ limited to only length ${\displaystyle t}$ inputs. Then we can see ${\displaystyle L}$ as a binary string of length ${\displaystyle 2^{t}}$, where each bit is ${\displaystyle L(x)}$ for each ${\displaystyle x\in \{0,1\}^{t}}$. We can use a polynomial length locally decodable code ${\displaystyle C}$ with polylogarithmic query complexity that tolerates some constant fraction of errors to encode the string that represents ${\displaystyle L}$ to create a new string of length ${\displaystyle 2^{O(t)}=2^{t'}}$. We think of this new string as defining a new problem ${\displaystyle L'}$ on length ${\displaystyle t'}$ inputs. If ${\displaystyle L'}$ is easy to solve on average, that is, we can solve ${\displaystyle L'}$ correctly on a large fraction ${\displaystyle 1-\epsilon }$ of inputs, then by the properties of the LDC used to encode it, we can use ${\displaystyle L'}$ to probabilistically compute ${\displaystyle L}$ on all inputs. Thus, a solution to ${\displaystyle L'}$ for most inputs would allow us to solve ${\displaystyle L}$ on all inputs, contradicting our assumption that ${\displaystyle L}$ is hard on worst case inputs.^[5][8][12]

A private information retrieval scheme allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. One common way of ensuring privacy is to have ${\displaystyle k}$ separate, non-communicating servers, each with a copy of the database. Given an appropriate scheme, the user can make queries to each server that individually do not reveal which bit the user is looking for, but which together provide enough information that the user can determine the particular bit of interest in the database.^[3][11]

One can easily see that locally decodable codes have applications in this setting. A general procedure to produce a ${\displaystyle k}$-server private information scheme from a perfectly smooth ${\displaystyle k}$-query locally decodable code is as follows:

を、 - ビットのメッセージを - ビットのコードワードにエンコードする完全に滑らかな 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 }$

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