Código decodificable localmente

Tipo de código de corrección de errores

Un código decodificable localmente ( LDC ) es un código de corrección de errores que permite decodificar un solo bit del mensaje original con alta probabilidad examinando (o consultando) solo una pequeña cantidad de bits de una palabra de código posiblemente corrupta . ^{[1] [2] [3]} Esta propiedad podría ser útil, por ejemplo, en un contexto donde la información se transmite a través de un canal ruidoso, y solo se requiere un pequeño subconjunto de los datos en un momento particular y no hay necesidad de decodificar todo el mensaje a la vez. Tenga en cuenta que los códigos decodificables localmente no son un subconjunto de los códigos comprobables localmente , aunque existe cierta superposición entre los dos. ^[4]

Las palabras clave se generan a partir del mensaje original mediante un algoritmo que introduce una cierta cantidad de redundancia en la palabra clave; por lo tanto, la palabra clave siempre es más larga que el mensaje original. Esta redundancia se distribuye a lo largo de la palabra clave y permite recuperar el mensaje original con una buena probabilidad incluso en presencia de errores. Cuanto más redundante sea la palabra clave, más resistente será a los errores y menos consultas se necesitarán para recuperar un poco del mensaje original.

Descripción general

Más formalmente, un código decodificable localmente codifica un mensaje de -bit en una palabra código de -bit de modo que cualquier bit del mensaje se puede recuperar con probabilidad utilizando un algoritmo de decodificación aleatorio que consulta solo bits de la palabra código , incluso si hasta ubicaciones de la palabra código han sido dañadas. ${\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}$

Además, un decodificador local perfectamente suave es un decodificador tal que, además de generar siempre la salida correcta dado el acceso a una palabra de código no corrupta, para cada y la consulta para recuperar el bit es uniforme sobre . ^[5] (La notación denota el conjunto ). De manera informal, esto significa que el conjunto de consultas necesarias para decodificar cualquier bit dado se distribuye uniformemente sobre la palabra de código. ${\displaystyle j\in [q]}$ ${\displaystyle i\in [n]}$ ${\displaystyle j^{th}}$ ${\displaystyle i^{th}}$ ${\displaystyle [N]}$ ${\displaystyle [y]}$ ${\displaystyle \{1,\ldots ,y\}}$

Los decodificadores de listas locales son otro subconjunto interesante de decodificadores locales. La decodificación de listas es útil cuando una palabra de código está dañada en más de lugares, donde es la distancia mínima de Hamming entre dos palabras de código. En este caso, ya no es posible identificar exactamente qué mensaje original ha sido codificado, ya que podría haber múltiples palabras de código dentro de la distancia de la palabra de código dañada. Sin embargo, dado un radio , es posible identificar el conjunto de mensajes que codifican palabras de código que están dentro de la distancia de la palabra de código dañada. Un límite superior en el tamaño del conjunto de mensajes puede determinarse mediante y . ^[6] ${\displaystyle \delta /2}$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \delta }$ ${\displaystyle \epsilon }$

Los códigos decodificables localmente también pueden concatenarse, donde un mensaje se codifica primero usando un esquema, y ​​la palabra clave resultante se codifica nuevamente usando un esquema diferente. (Nótese que, en este contexto, concatenación es el término usado por los académicos para referirse a lo que usualmente se llama composición ; vea ^[5] ). Esto podría ser útil si, por ejemplo, el primer código tiene algunas propiedades deseables con respecto a la velocidad, pero tiene alguna propiedad indeseable, como producir una palabra clave sobre un alfabeto no binario. El segundo código puede entonces transformar el resultado de la primera codificación sobre un alfabeto no binario a un alfabeto binario. La codificación final todavía es decodificable localmente, y requiere pasos adicionales para decodificar ambas capas de codificación. ^[7]

Longitud de la palabra clave y complejidad de la consulta

La tasa de un código se refiere a la relación entre la longitud de su mensaje y la longitud de la palabra de código: , y la cantidad de consultas necesarias para recuperar 1 bit del mensaje se denomina complejidad de consulta de un código. ${\displaystyle {\frac {|x|}{|C(x)|}}}$

La tasa de un código está inversamente relacionada con la complejidad de la consulta, pero la forma exacta de este equilibrio es un importante problema abierto. ^{[8] [9]} Se sabe que no hay LDC que consulten la palabra de código en una sola posición, y que el tamaño óptimo de la palabra de código para la complejidad de la consulta 2 es exponencial en el tamaño del mensaje original. ^[8] Sin embargo, no hay límites inferiores estrictos conocidos para códigos con una complejidad de consulta mayor que 2. Acercándose al equilibrio desde el lado de la longitud de la palabra de código, los únicos códigos conocidos con una longitud de palabra de código proporcional a la longitud del mensaje tienen una complejidad de consulta para ^{[8] [ necesita actualización ]} También hay códigos intermedios, que tienen palabras de código polinomiales en el tamaño del mensaje original y una complejidad de consulta polilogarítmica. ^[8] ${\displaystyle k^{\epsilon }}$ ${\displaystyle \epsilon >0}$

Aplicaciones

Los códigos decodificables localmente tienen aplicaciones en la transmisión y almacenamiento de datos, la teoría de la complejidad, las estructuras de datos, la desaleatorización, la teoría de la computación tolerante a fallos y los esquemas de recuperación de información privada. ^[9]

Transmisión y almacenamiento de datos

Los códigos decodificables localmente son especialmente útiles para la transmisión de datos a través de canales ruidosos. El código Hadamard (un caso especial de los códigos Reed Muller) fue utilizado en 1971 por la Mariner 9 para transmitir imágenes de Marte a la Tierra. Se eligió en lugar de un código de 5 repeticiones (donde cada bit se repite 5 veces) porque, para aproximadamente el mismo número de bits transmitidos por píxel, tenía una mayor capacidad de corrección de errores. (El código Hadamard cae bajo el paraguas general de la corrección de errores hacia adelante , y resulta ser decodificable localmente; el algoritmo real utilizado para decodificar la transmisión desde Marte fue un esquema de corrección de errores genérico.) ^[10]

Los LDC también son útiles para el almacenamiento de datos, en cuyo caso el medio puede corromperse parcialmente con el tiempo o el dispositivo de lectura puede sufrir errores. En ambos casos, un LDC permitirá recuperar la información a pesar de los errores, siempre que sean relativamente pocos. Además, los LDC no requieren que se decodifique todo el mensaje original; un usuario puede decodificar una parte específica del mensaje original sin necesidad de decodificarlo todo. ^[11]

Teoría de la complejidad

Una de las aplicaciones de los códigos localmente decodificables en la teoría de la complejidad es la amplificación de la dureza. Si se utilizan códigos localmente decodificables con una longitud de palabra de código polinómica y una complejidad de consulta polilogarítmica, se puede tomar una función que es difícil de resolver en las entradas del peor caso y diseñar una función que es difícil de calcular en las entradas del caso promedio. ${\displaystyle L:\{0,1\}^{n}\rightarrow \{0,1\}}$ ${\displaystyle L':\{0,1\}^{N}\rightarrow \{0,1\}}$

Consideremos que está limitado a entradas de longitud únicamente . Entonces podemos verlo como una cadena binaria de longitud , donde cada bit es para cada . Podemos usar un código decodificable localmente de longitud polinómica con complejidad de consulta polilogarítmica que tolera una fracción constante de errores para codificar la cadena que representa para crear una nueva cadena de longitud . Pensamos en esta nueva cadena como la definición de un nuevo problema en entradas de longitud . Si es fácil de resolver en promedio, es decir, podemos resolver correctamente en una gran fracción de entradas, entonces por las propiedades del LDC usado para codificarlo, podemos usar para calcular de manera probabilística en todas las entradas. Por lo tanto, una solución para para la mayoría de las entradas nos permitiría resolver en todas las entradas, contradiciendo nuestra suposición de que es difícil en las entradas del peor caso. ^{[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}$

Esquemas de recuperación de información privada

Un esquema de recuperación de información privada permite a un usuario recuperar un elemento de un servidor que posee una base de datos sin revelar qué elemento se recupera. Una forma común de garantizar la privacidad es tener servidores separados, que no se comunican, cada uno con una copia de la base de datos. Dado un esquema apropiado, el usuario puede realizar consultas a cada servidor que individualmente no revelan qué bit está buscando el usuario, pero que en conjunto proporcionan suficiente información para que el usuario pueda determinar el bit particular de interés en la base de datos. ^{[3] [11]} ${\displaystyle k}$

Se puede ver fácilmente que los códigos decodificables localmente tienen aplicaciones en este contexto. Un procedimiento general para producir un esquema de información privada de servidor a partir de un código decodificable localmente de consulta perfectamente uniforme es el siguiente: ${\displaystyle k}$ ${\displaystyle k}$

Sea un LDC perfectamente uniforme que codifica mensajes de -bit en palabras de código de -bit. Como paso de preprocesamiento, cada uno de los servidores codifica la base de datos de -bit con el código , por lo que ahora cada servidor almacena la palabra de código de -bit . Un usuario interesado en obtener el bit de genera aleatoriamente un conjunto de consultas de modo que se pueda calcular a partir de utilizando el algoritmo de decodificación local para . El usuario envía cada consulta a un servidor diferente y cada servidor responde con el bit solicitado. Luego, el usuario utiliza para calcular a partir de las respuestas. ^{[8] [11]} Debido a que el algoritmo de decodificación es perfectamente uniforme, cada consulta se distribuye uniformemente sobre la palabra de código; por lo tanto, ningún servidor individual puede obtener información sobre las intenciones del usuario, por lo que el protocolo es privado mientras los servidores no se comuniquen. ^[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}}$

Ejemplos

El código Hadamard

El código Hadamard (o Walsh-Hadamard) es un ejemplo de un código simple decodificable localmente que asigna una cadena de longitud a una palabra de código de longitud . La palabra de código para una cadena se construye de la siguiente manera: para cada , el bit de la palabra de código es igual a , donde (mod 2). Es fácil ver que cada palabra de código tiene una distancia de Hamming de con respecto a cada otra palabra de código. ${\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}}}$

El algoritmo de decodificación local tiene una complejidad de consulta de 2 y se puede decodificar todo el mensaje original con buena probabilidad si la palabra clave está dañada en menos de sus bits. Por ejemplo , si la palabra clave está dañada en una fracción de lugares, un algoritmo de decodificación local puede recuperar el bit del mensaje original con probabilidad . ${\displaystyle {\frac {1}{4}}}$ ${\displaystyle \rho <{\frac {1}{4}}}$ ${\displaystyle \rho }$ ${\displaystyle i^{th}}$ ${\displaystyle 1-2\rho }$

Prueba: Dada una palabra clave y un índice , el algoritmo para recuperar el bit del mensaje original funciona de la siguiente manera: ${\displaystyle H}$ ${\displaystyle i}$ ${\displaystyle i^{th}}$ ${\displaystyle x}$

Hagamos referencia al vector en que tiene 1 en la posición y 0 en el resto. Para , denota el bit único en que corresponde a . El algoritmo elige un vector aleatorio y el vector (donde denota XOR bit a bit ). El algoritmo genera (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')}$

Corrección: Por linealidad,

${\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}}$

Pero , simplemente necesitamos demostrarlo y con buena probabilidad. ${\displaystyle (x\odot e^{i})=x_{i}}$ ${\displaystyle f(y)=x\odot y}$ ${\displaystyle f(y')=x\odot y'}$

Dado que y están distribuidos uniformemente (aunque son dependientes), el límite de unión implica que y con una probabilidad de al menos . Nota: para amplificar la probabilidad de éxito, se puede repetir el procedimiento con diferentes vectores aleatorios y tomar la respuesta mayoritaria. ^[13] ${\displaystyle y}$ ${\displaystyle y'}$ ${\displaystyle f(y)=x\odot y}$ ${\displaystyle f(y')=x\odot y'}$ ${\displaystyle 1-2\rho }$

El código Reed-Muller

La idea principal detrás de la decodificación local de los códigos Reed-Muller es la interpolación polinómica . El concepto clave detrás de un código Reed-Muller es un polinomio multivariado de grado en variables. El mensaje se trata como la evaluación de un polinomio en un conjunto de puntos predefinidos. Para codificar estos valores, se extrapola un polinomio a partir de ellos, y la palabra clave es la evaluación de ese polinomio en todos los puntos posibles. En un nivel alto, para decodificar un punto de este polinomio, el algoritmo de decodificación elige un conjunto de puntos en una línea que pasa por el punto de interés . Luego, consulta la palabra clave para la evaluación del polinomio en los puntos en e interpola ese polinomio. Luego, es simple evaluar el polinomio en el punto que producirá . Esta forma indirecta de evaluación es útil porque (a) el algoritmo se puede repetir utilizando diferentes líneas a través del mismo punto para mejorar la probabilidad de corrección, y (b) las consultas se distribuyen uniformemente en la palabra clave. ${\displaystyle d}$ ${\displaystyle l}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle x}$

Más formalmente, sea un cuerpo finito, y sean números con . El código Reed-Muller con parámetros es la función RM : que asigna cada polinomio de variable sobre de grado total a los valores de en todas las entradas en . Es decir, la entrada es un polinomio de la forma especificada por la interpolación de los valores de los puntos predefinidos y la salida es la secuencia para cada . ^[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} }$

Para recuperar el valor de un polinomio de grado en un punto , el decodificador local dispara una línea afín aleatoria a través de . Luego, elige puntos en esa línea, que utiliza para interpolar el polinomio y luego evaluarlo en el punto donde el resultado es . Para ello, el algoritmo elige un vector de manera uniforme al azar y considera la línea que pasa por . El algoritmo elige un subconjunto arbitrario de , donde , y consulta las coordenadas de la palabra de código que corresponden a los puntos para todos y obtiene valores . Luego, utiliza la interpolación polinómica para recuperar el único polinomio univariante con grado menor o igual a tal que para todos . Luego, para obtener el valor de , simplemente evalúa . Para recuperar un solo valor del mensaje original, uno elige ser uno de los puntos que define el polinomio. ^{[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}$

Cada consulta individual se distribuye de manera uniforme y aleatoria sobre la palabra clave. Por lo tanto, si la palabra clave está dañada como máximo en una fracción de ubicaciones, por el límite de unión, la probabilidad de que el algoritmo muestree solo coordenadas no dañadas (y, por lo tanto, recupere correctamente el bit) es de al menos . ^[8] Para otros algoritmos de decodificación, consulte. ^[8] ${\displaystyle \delta }$ ${\displaystyle 1-(d+1)\delta }$

Véase también

• Recuperación de información privada
• Criptoanálisis lineal

Referencias

1. Sergey Yekhanin. "Códigos localmente decodificables: un breve estudio" (PDF) .
2. Rafail Ostrovsky; Omkant Pandey; Amit Sahai. "Códigos privados decodificables localmente" (PDF) .
3. Sergey Yekhanin. Nuevos códigos decodificables localmente y esquemas de recuperación de información privada, Informe técnico ECCC TR06-127, 2006.
4. Kaufman, Tali ; Viderman, Michael. "Códigos comprobables localmente frente a códigos decodificables localmente".
5. Luca Trevisan. "Algunas aplicaciones de la teoría de codificación en la complejidad computacional" (PDF) .
6. Arora, Sanjeev ; Barak, Boaz (2009). "Sección 19.5". Complejidad computacional: un enfoque moderno. Cambridge . ISBN 978-0-521-42426-4.
7. Arora y Barak 2009, Sección 19.4.3
8. Sergey Yekhanin. "Códigos decodificables localmente" (PDF) .
9. Sergey Yekhanin. "Códigos decodificables localmente" (PDF) .
10. "Combinatoria en el espacio: el sistema de telemetría del Mariner 9" (PDF) .
11. Sergey Yekhanin. "Recuperación de información privada" (PDF) .
12. Arora y Barak 2009, Sección 19.4
13. Arora y Barak 2009, Sección 11.5.2
14. Arora y Barak 2009, sección 19.4.2