Código no maleable

Para conocer el esquema de funcionamiento del código no maleable, debemos comprender el experimento básico en el que se basa. A continuación, se describe el método de tres pasos para realizar un experimento de manipulación .

1. Un mensaje de origen${\displaystyle s}$se codifica mediante un procedimiento (posiblemente aleatorio)${\displaystyle Enc}$, lo que produce una palabra clave${\displaystyle c}$=${\displaystyle Enc(s)}$.
2. La palabra clave se modifica mediante alguna función de manipulación.${\displaystyle f\in F}$a una palabra clave errónea${\displaystyle c^{*}}$=${\displaystyle f(c)}$.
3. La palabra clave errónea${\displaystyle c^{*}}$se decodifica mediante un procedimiento${\displaystyle Dec}$lo que da como resultado un mensaje decodificado ${\displaystyle s^{*}}$=${\displaystyle Dec(c^{*})}$.

El experimento de manipulación puede utilizarse para modelar varios escenarios interesantes del mundo real, como la transmisión de datos a través de un canal ruidoso o la manipulación maliciosa de datos almacenados en la memoria de un dispositivo físico. Con esta base experimental, nos gustaría desarrollar procedimientos especiales de codificación/decodificación.${\displaystyle (Enc,Dec)}$, que nos brindan algunas garantías significativas sobre los resultados del experimento de manipulación mencionado anteriormente, para familias grandes e interesantes.${\displaystyle F}$de funciones de manipulación. A continuación se presentan varias posibilidades para el tipo de garantías que podemos esperar. ^{[ 2 ]}

Una garantía muy natural, denominada corrección de errores , consistiría en exigir que, para cualquier función de manipulación y cualquier mensaje fuente s , el experimento de manipulación siempre produzca el mensaje decodificado correcto. ${\displaystyle s^{*}=s}$. ^{[ 3 ]}

Una garantía más débil, denominada detección de errores , requiere que el experimento de manipulación siempre dé como resultado el valor correcto.${\displaystyle s^{*}=s}$o un símbolo especial${\displaystyle s^{*}=\perp }$lo que indica que se ha detectado manipulación. Esta noción de detección de errores es una garantía más débil que la corrección de errores, y se puede lograr para funciones de manipulación F más grandes.

Como ejemplo muy concreto, estudiamos la no maleabilidad con respecto a la familia de funciones.${\displaystyle f}$que especifican, para cada bit de la palabra clave${\displaystyle c}$, ya sea mantenerlo como está, invertirlo, establecerlo a 0, establecerlo a 1. Es decir, cada bit de la palabra clave se modifica arbitrariamente pero independientemente del valor de los demás bits de la palabra clave. A esto lo llamamos la familia de "manipulación independiente bit a bit".${\displaystyle F_{BIT}}$Nótese que esta familia contiene funciones constantes.${\displaystyle F_{const}}$y funciones de error constante${\displaystyle F_{err}}$como subconjuntos. Por lo tanto, como ya hemos mencionado, no es posible lograr la corrección ni la detección de errores con respecto a esta familia. Sin embargo, a continuación se muestra un código eficiente y no maleable para esta potente familia.

Con${\displaystyle F_{BIT}}$Denotamos la familia que contiene todas las funciones de manipulación que manipulan cada bit de forma independiente. Formalmente, esta familia contiene todas las funciones${\displaystyle f_{i}:\left\{{0},{1}\right\}^{n}\to \left\{{0},{1}\right\}^{n}}$ que se definen mediante n funciones${\displaystyle f_{i}:\left\{{0},{1}\right\}\to \left\{{0},{1}\right\}}$(para i=1...n) como${\displaystyle f(c_{1}..c_{n})=f_{1}(c_{1})..f_{n}(c_{n})}$Tenga en cuenta que solo hay 4 opciones posibles para cada una.${\displaystyle f_{i}}$(es decir, cómo modificar un bit en particular) y los denominamos "establecer a 0", "establecer a 1", "invertir", "mantener", donde los significados deberían ser intuitivos. A esta familia la llamamos familia de manipulación independiente a nivel de bits.

• Enfoque de método probabilístico

Para cualquier familia de funciones "suficientemente pequeña"${\displaystyle F}$Existe un esquema de codificación (posiblemente ineficiente) que no es maleable con respecto a F. Además, para una familia de funciones fija "suficientemente pequeña"${\displaystyle F}$Un esquema de codificación aleatoria probablemente no sea maleable con respecto a F con una probabilidad abrumadora. Desafortunadamente, los esquemas de codificación aleatoria no pueden representarse de manera eficiente, ni es probable que la función de codificación/decodificación sea eficiente. Por lo tanto, este resultado debe interpretarse simplemente como una muestra de "posibilidad" y un objetivo que debemos esforzarnos por alcanzar de manera constructiva. Además, este resultado también resalta la diferencia entre "corrección/detección de errores" y "no maleabilidad", ya que un resultado de esta forma no podría ser válido para las nociones anteriores.

• Enfoque del modelo de oráculo aleatorio

No está claro qué implica realmente la cota del teorema ^{[ 4 ]} de este tipo. Por ejemplo, nos dice que existen códigos no maleables con respecto a todas las funciones eficientes, pero esto es engañoso, ya que sabemos que los códigos no maleables eficientes (y en última instancia, solo nos interesan estos) no pueden ser no maleables con respecto a esta clase. Sin embargo, el resultado del método probabilístico sí nos proporciona códigos que son no maleables con respecto a clases muy generales de funciones en el modelo de oráculo aleatorio.

En este modelo, consideramos dos formas de interactuar con el sistema:

Ejecutar(${\displaystyle x}$): Un usuario puede proporcionar al sistema consultas Execute(x), para${\displaystyle x\in \left\{{0},{1}\right\}^{u}}$, en cuyo caso el sistema calcula${\displaystyle (y,s^{'})\gets G(x,s)}$actualiza el estado del sistema a${\displaystyle s:=s^{'}}$y resultados${\displaystyle y}$.

Manosear(${\displaystyle f}$) : También consideramos los ataques de manipulación contra el sistema, modelados por Tamper(${\displaystyle f}$comandos, para funciones${\displaystyle f:\left\{{0},{1}\right\}^{n}\to \left\{{0},{1}\right\}^{n}}$. Al recibir dicho comando, el estado del sistema se establece en${\displaystyle s:=f(s)}$.

Un atacante que también puede interactuar con el sistema a través de consultas Tamper puede potencialmente obtener mucha más información sobre el estado secreto, incluso recuperarlo por completo. Por lo tanto, nos gustaría tener un método general para proteger los sistemas contra ataques de manipulación, de modo que la capacidad de emitir consultas Tamper (al menos para funciones f en alguna familia grande)${\displaystyle F}$) no puede proporcionar al atacante información adicional. Al utilizar código no maleable para este propósito, llegamos a la conclusión: Sea${\displaystyle (Enc,Dec)}$ser cualquier esquema de codificación que no sea maleable con respecto a${\displaystyle F}$, entonces${\displaystyle (Enc,Dec)}$También se puede simular manipulación con respecto a${\displaystyle F}$.