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 clave 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 datos en un momento particular y no hay necesidad de decodificar el mensaje completo de una vez. Tenga en cuenta que los códigos decodificables localmente no son un subconjunto de códigos comprobables localmente , aunque existe cierta superposición entre los dos. ^[4]

Las palabras clave se generan a partir del mensaje original utilizando un algoritmo que introduce una cierta cantidad de redundancia en la palabra clave; por 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 buena probabilidad incluso en presencia de errores. Cuanto más redundante sea la palabra clave, más resistente será a los errores y se necesitarán menos consultas para recuperar una parte del mensaje original.

Descripción general

Más formalmente, un código decodificable localmente codifica un mensaje de bits en una palabra de código de bits de modo que cualquier bit del mensaje pueda recuperarse con probabilidad mediante el uso de un algoritmo de decodificación aleatorio que consulta sólo bits de la palabra de código , incluso si se trata de ubicaciones de la palabra clave se ha corrompido. ${\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 fluido 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 . ^[5] (La notación denota el conjunto ). Informalmente, esto significa que el conjunto de consultas necesarias para decodificar cualquier bit determinado se distribuye uniformemente en la palabra clave. ${\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á corrupta en más de lugares, donde está la distancia mínima de Hamming entre dos palabras de código. En este caso, ya no es posible identificar exactamente qué mensaje original se ha codificado, ya que podría haber varias palabras de código a una distancia de la palabra de código corrupta. Sin embargo, dado un radio , es posible identificar el conjunto de mensajes que codifican palabras clave que se encuentran dentro de la palabra clave corrupta. Un límite superior en el tamaño del conjunto de mensajes puede ser determinado por y . ^[6] ${\displaystyle \delta /2}$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \delta }$ ${\displaystyle \epsilon }$

Los códigos decodificables localmente también se pueden concatenar, 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 utilizado por los estudiosos para referirse a lo que suele denominarse composición ; véase ^[5] ). Esto podría resultar ú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 de código sobre un alfabeto no binario. Luego, el segundo código puede transformar el resultado de la primera codificación sobre un alfabeto no binario en un alfabeto binario. La codificación final todavía se puede descodificar localmente y requiere pasos adicionales para decodificar ambas capas de codificación. ^[7]

Longitud de la palabra clave y complejidad de la consulta

La velocidad de un código se refiere a la relación entre la longitud del mensaje y la longitud de la palabra clave: , 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 velocidad de un código está inversamente relacionada con la complejidad de la consulta, pero la forma exacta de esta compensación es un importante problema abierto. ^{[8] [9]} Se sabe que no hay PMA 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 consulta 2 es exponencial en el tamaño del mensaje original. ^[8] Sin embargo, no se conocen límites inferiores estrictos para los códigos con una complejidad de consulta superior a 2. Al abordar la compensación 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 polinómicas en el tamaño del mensaje original y complejidad de consulta polilogarítmica. ^[8] ${\displaystyle k^{\epsilon }}$ ${\displaystyle \epsilon >0}$

Aplicaciones

Los códigos decodificables localmente tienen aplicaciones para la transmisión y el 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 fallas 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 el 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 corrección directa de errores , y resulta que es localmente descodificable; el algoritmo real utilizado para decodificar la transmisión desde Marte fue un esquema genérico de corrección de errores.) ^[10]

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

Teoría de la complejidad

Una de las aplicaciones de los códigos decodificables localmente en la teoría de la complejidad es la amplificación de la dureza. Al utilizar PMA con longitud de palabra de código polinomial y complejidad de consulta polilogarítmica, se puede tomar una función que es difícil de resolver en las entradas del peor de los casos 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\}}$

Considere limitarse únicamente a entradas de longitud. Luego lo podemos ver como una cadena binaria de longitud , donde cada bit es para cada uno . Podemos utilizar un código de longitud polinomial localmente decodificable 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 que esta nueva cadena define un nuevo problema en las entradas de longitud. Si es fácil de resolver en promedio, es decir, podemos resolver correctamente en una gran fracción de entradas, entonces, mediante las propiedades del LDC utilizado para codificarlo, podemos utilizarlo para calcular probabilísticamente en todas las entradas. Por lo tanto, una solución para la mayoría de los insumos nos permitiría resolver todos los insumos, contradiciendo nuestra suposición de que es difícil para los insumos del peor de los casos. ^{[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 en posesión de 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 comuniquen, 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 entorno. Un procedimiento general para producir un esquema de información privada del servidor a partir de un código perfectamente fluido y decodificable localmente es el siguiente: ${\displaystyle k}$ ${\displaystyle k}$

Sea un LDC perfectamente fluido que codifique mensajes de bits en palabras de código de bits. Como paso de preprocesamiento, cada uno de los servidores codifica la base de datos de bits con el código , por lo que ahora cada servidor almacena la palabra clave de bits . Un usuario interesado en obtener el bit de genera aleatoriamente un conjunto de consultas que pueden calcularse utilizando el algoritmo de decodificación local de . 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 fluido, cada consulta se distribuye uniformemente sobre la palabra clave; 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 clave de longitud . La palabra clave para una cadena se construye de la siguiente manera: para cada , el bit de la palabra clave es igual a , donde (mod 2). Es fácil ver que cada palabra en clave tiene una distancia de Hamming de cualquier otra palabra en clave. ${\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 2 y todo el mensaje original se puede decodificar con una buena probabilidad si la palabra clave está corrupta en menos de sus bits. Porque , si la palabra clave está corrupta 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 en 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}$

Nos referimos al vector que tiene 1 en la posición y 0 en otros lugares. For , denota el bit único 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 sólo tenemos que 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 uniformemente distribuidos (aunque sean dependientes), la unión ligada implica que y con probabilidad 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 códigos Reed-Muller es la interpolación polinomial . El concepto clave detrás de un código Reed-Muller es un polinomio de grado multivariado 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 puntos e interpola ese polinomio. Entonces es sencillo evaluar el polinomio en el punto que producirá . Esta forma indirecta de evaluación es útil porque (a) el algoritmo se puede repetir usando 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 campo finito y sean números con . El código Reed-Muller con parámetros es la función RM: que asigna cada polinomio variable 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 grados en un punto , el decodificador local dispara una línea afín aleatoria . Luego selecciona puntos en esa línea, que usa para interpolar el polinomio y luego evaluarlo en el punto donde está el resultado . Para hacerlo, el algoritmo elige un vector uniformemente al azar y considera la línea que pasa por . El algoritmo elige un subconjunto arbitrario de , dónde y consulta las coordenadas de la palabra clave que corresponden a puntos para todos y obtiene valores . Luego utiliza la interpolación polinómica para recuperar el polinomio univariado único con un grado menor o igual que para todos . Luego, para obtener el valor de , simplemente evalúa . Para recuperar un único valor del mensaje original, se 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 uniformemente y al azar sobre la palabra clave. Por lo tanto, si la palabra clave está corrompida como máximo en una fracción de ubicaciones, por el límite de unión, la probabilidad de que el algoritmo muestree sólo coordenadas no corrompidas (y por lo tanto recupere correctamente el bit) es al menos . ^[8] Para otros algoritmos de decodificación, consulte. ^[8] ${\displaystyle \delta }$ ${\displaystyle 1-(d+1)\delta }$

Ver también

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

Referencias

1. Serguéi Yekhanin. "Códigos decodificables localmente: una breve encuesta" (PDF) .
2. Rafael 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 la codificación en complejidad computacional" (PDF) .
6. Arora, Sanjeev ; Barac, Booz (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 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