Adversario computacionalmente limitado

Método de envío de datos

En teoría de la información , el problema del adversario limitado computacionalmente es una forma diferente de ver el problema de enviar datos a través de un canal ruidoso. En modelos anteriores, lo mejor que se podía hacer era asegurar una decodificación correcta para hasta d /2 errores, donde d era la distancia de Hamming del código. El problema de hacerlo de esta manera es que no tiene en cuenta la cantidad real de potencia de cálculo disponible para el adversario. En cambio, solo se preocupa de cuántos bits de una palabra de código dada pueden cambiar y aún así hacer que el mensaje se decodifique correctamente. En el modelo del adversario limitado computacionalmente, el canal (el adversario ) está restringido a solo poder realizar una cantidad razonable de cálculos para decidir qué bits de la palabra de código deben cambiar. En otras palabras, este modelo no necesita considerar cuántos errores se pueden manejar, sino solo cuántos errores se podrían introducir dada una cantidad razonable de potencia de cálculo por parte del adversario. Una vez que se le ha dado esta restricción al canal, es posible construir códigos que son más rápidos de codificar y decodificar en comparación con los métodos anteriores que también pueden manejar una gran cantidad de errores.

Comparación con otros modelos

Modelo del peor caso

A primera vista, el modelo del peor de los casos parece intuitivamente ideal. La garantía de que un algoritmo tendrá éxito pase lo que pase es, por supuesto, muy atractiva. Sin embargo, exige demasiado. Un adversario de la vida real no puede dedicar una cantidad indefinida de tiempo a examinar un mensaje para encontrar el patrón de error con el que un algoritmo tendría dificultades.

A modo de comparación, considere el algoritmo Quicksort . En el peor de los casos, Quicksort realiza comparaciones O( n ² ); sin embargo, tal ocurrencia es rara. Quicksort casi invariablemente realiza comparaciones O( n  log  n ) en su lugar, e incluso supera a otros algoritmos que pueden garantizar un comportamiento O( n  log  n ). Supongamos que un adversario desea forzar al algoritmo Quicksort a realizar comparaciones O( n ² ). Luego tendría que buscar todas las n ! permutaciones de la cadena de entrada y probar el algoritmo en cada una hasta que encuentre aquella para la que el algoritmo se ejecuta significativamente más lento. Pero como esto tomaría O( n !) tiempo, es claramente inviable que un adversario lo haga. De manera similar, no es razonable suponer que un adversario de un sistema de codificación y decodificación sería capaz de probar cada patrón de error para encontrar el más efectivo.

Modelo de ruido estocástico

El modelo de ruido estocástico puede describirse como una especie de modelo de ruido "tonto". Es decir, no tiene la adaptabilidad necesaria para lidiar con amenazas "inteligentes". Incluso si el atacante está limitado, aún es posible que pueda superar el modelo estocástico con un poco de astucia. El modelo estocástico no tiene una forma real de luchar contra este tipo de ataque y, como tal, no es adecuado para lidiar con el tipo de amenazas "inteligentes" contra las que sería preferible tener defensas.

---

Por lo tanto, se ha propuesto un modelo antagónico computacionalmente limitado como un compromiso entre los dos. ^[1] Esto obliga a considerar que los mensajes pueden pervertirse de manera consciente, incluso maliciosa, pero sin obligar al diseñador de un algoritmo a preocuparse por casos raros que probablemente nunca ocurrirán.

Aplicaciones

Comparación con el canal de ruido estocástico

Dado que cualquier adversario con límites computacionales podría en tiempo O( n ) lanzar una moneda para cada bit, es intuitivamente claro que cualquier sistema de codificación y decodificación que pueda funcionar contra este adversario también debe funcionar en el modelo de ruido estocástico. La inversa es menos simple; sin embargo, se puede demostrar que cualquier sistema que funcione en el modelo de ruido estocástico también puede codificar y decodificar de manera eficiente contra un adversario con límites computacionales, y solo a un costo adicional que es polinomial en n . ^[1] El siguiente método para lograr esto fue diseñado por Dick Lipton y está tomado de: ^[1]

Una ilustración del método. La primera fila muestra el mensaje codificado inicial; la segunda, después de la permutación aleatoria y la R aleatoria; la tercera, después de que el adversario agregue N; la cuarta, después de la anulación de la permutación; la quinta, el mensaje codificado con el error del adversario eliminado.

Sea un codificador para el modelo de ruido estocástico y un decodificador simple para el mismo, cada uno de los cuales se ejecuta en tiempo polinomial. Además, sea que tanto el emisor como el receptor compartan una función de permutación aleatoria y un patrón aleatorio . ${\displaystyle E()}$ ${\displaystyle D()}$ ${\displaystyle \pi }$ ${\displaystyle R}$

Para codificar: 1. Sea . ${\displaystyle X=E(M)}$

2. Sea . ${\displaystyle Y=\pi (X)\oplus R}$

3. Transmitir ${\displaystyle Y}$

Luego, para decodificar: 1. Recibir . Calcular . ${\displaystyle Y'}$ ${\displaystyle Z=\pi ^{-1}(Y'\oplus R)}$

2. Calcular . ${\displaystyle M=D(Z)}$

De manera similar a la comparación de Quicksort anterior, si el canal quiere hacer algo inteligente, primero debe probar todas las permutaciones. Sin embargo, esto no es factible para un adversario con limitaciones computacionales, por lo que lo máximo que puede hacer es crear un patrón de error aleatorio . Pero entonces: ${\displaystyle N}$

${\displaystyle Z=\pi ^{-1}(Y'\oplus R)=\pi ^{-1}(Y\oplus N\oplus R),}$

ya que por definición. ${\displaystyle Y'=Y\oplus N}$

${\displaystyle =\pi ^{-1}(Y\oplus R)\oplus N'}$, dónde ${\displaystyle N'=\pi ^{-1}(N),}$

dado que cualquier permutación es lineal con respecto a XOR,

${\displaystyle =X\oplus N',}$

según la definición anterior. ${\displaystyle Y}$

Dado que es aleatorio, es solo ruido aleatorio y podemos usar el decodificador simple para decodificar el mensaje recibido y obtenerlo . ${\displaystyle \pi }$ ${\displaystyle N'}$ ${\displaystyle M}$

Aplicaciones específicas

Suponiendo un adversario con límites computacionales, es posible diseñar un código localmente decodificable que sea eficiente y casi óptimo, con una probabilidad de error despreciable. Estos códigos se utilizan en la teoría de la complejidad para cosas como cálculos autocorrectivos, sistemas de prueba probabilísticamente comprobables y reducciones de dureza del peor de los casos al caso promedio en las construcciones de generadores pseudoaleatorios. Son útiles en criptografía como resultado de su conexión con protocolos de recuperación de información privada . También se encuentran en varias aplicaciones de bases de datos como el almacenamiento de datos tolerante a fallas . ^[2]

Además, es posible construir códigos que superen los límites conocidos para los códigos del peor de los casos, específicamente, la decodificación única con una tasa de error. ^[3] Esto se puede hacer concatenando firmas digitales con marca de tiempo en los mensajes. Un canal con límites computacionales no puede falsificar una firma; y si bien puede tener firmas pasadas válidas, el receptor puede usar la decodificación de lista y seleccionar un mensaje solo si su firma tiene la marca de tiempo correcta. ${\displaystyle 1-R}$

Véase también

• Seguridad del hormigón

Referencias

1. Lipton (6 de mayo de 2009). "Complejidad en el peor de los casos". La carta perdida de Gödel y P=NP . Consultado el 1 de abril de 2013 .
2. Ostrovsky, Pandey, Sahai. "Códigos privados decodificables localmente" (PDF) . Consultado el 1 de abril de 2013 .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )
3. Micali, Peikert; Sudan, A. Wilson. "Optimal Error Correction for Computationally Bounded Noise" (PDF) . Consultado el 1 de abril de 2013 .