Adversario limitado computacionalmente
En la teoría de la información , el problema del adversario delimitado computacionalmente es una forma diferente de ver el problema del envío de datos a través de un canal ruidoso. En modelos anteriores, lo mejor que se podía hacer era garantizar la decodificación correcta para errores de hasta d / 2, 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 informática disponible para el adversario. Más bien, solo se preocupa por cuántos bits de una palabra de código dada pueden cambiar y aún así tener el mensaje decodificado correctamente. En el modelo adversario delimitado computacionalmente, el canal - el adversario- está restringido a solo poder realizar una cantidad razonable de cálculo 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 podrían introducirse dada una cantidad razonable de poder de cómputo por parte del adversario. Una vez que se 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.
A primera vista, el modelo del peor de los casos parece intuitivamente ideal. La garantía de que un algoritmo tendrá éxito sin importar lo que sea, por supuesto, es muy atractiva. Sin embargo, exige demasiado. Un adversario de la vida real no puede pasar una cantidad de tiempo indefinida examinando un mensaje para encontrar el patrón de error con el que un algoritmo tendría dificultades.
Como comparación, considere el algoritmo Quicksort . En el peor de los casos, Quicksort hace comparaciones O ( n 2 ); sin embargo, tal ocurrencia es rara. Quicksort casi invariablemente hace comparaciones O ( n log n ) en su lugar, e incluso supera a otros algoritmos que pueden garantizar el comportamiento de O ( n log n ). Supongamos que un adversario desea forzar al algoritmo Quicksort a hacer comparaciones O ( n 2 ). ¡Entonces tendría que buscar en todos los 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 dado que esto tomaría O (¡ n !) tiempo, es claramente imposible que un adversario haga esto. De manera similar, no es razonable asumir que un adversario de un sistema de codificación y decodificación podría probar cada patrón de error para encontrar el más efectivo.
El modelo de ruido estocástico se puede describir como una especie de modelo de ruido "tonto". Es decir que no tiene la capacidad de adaptación para hacer frente a amenazas "inteligentes". Incluso si el atacante está limitado, es posible que pueda superar el modelo estocástico con un poco de inteligencia. 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 adverso computacionalmente limitado como un compromiso entre los dos. [1] Esto obliga a uno a considerar que los mensajes pueden pervertirse de manera consciente, incluso maliciosa, pero sin obligar al diseñador de algoritmos a preocuparse por casos raros que probablemente nunca ocurrirán.
Dado que cualquier adversario limitado computacionalmente podría en O ( n ) tiempo lanzar una moneda por 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. Lo contrario 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 eficientemente contra un adversario limitado computacionalmente, y solo a un costo adicional que es polinomio en n . [1] El siguiente método para lograr esto fue diseñado por Dick Lipton, y se tomó de: [1]
