Código no maleable

Códigos con la propiedad de que es difícil realizar ligeras modificaciones en los mensajes

La noción de códigos no maleables fue introducida en 2009 por Dziembowski, Pietrzak y Wichs ^[1] para relajar la noción de corrección y detección de errores . De manera informal, un código no es maleable si el mensaje contenido en una palabra de código modificada es el mensaje original o un valor completamente no relacionado. Los códigos no maleables proporcionan una garantía de seguridad útil y significativa en situaciones en las que la corrección y detección de errores tradicionales son imposibles; por ejemplo, cuando el atacante puede sobrescribir por completo el mensaje codificado. Aunque dichos códigos no existen si la familia de " funciones de manipulación " F no tiene restricciones, se sabe que existen para muchas familias amplias de manipulación F.

Fondo

Experimento de manipulación

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

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

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

Corrección de errores

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

Detección de errores

Una garantía más débil, llamada detección de errores , requiere que el experimento de manipulación siempre dé como resultado el valor correcto o un símbolo especial que indique que se ha detectado una 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 un F mayor de funciones de manipulación. ${\displaystyle s^{*}=s}$ ${\displaystyle s^{*}=\perp }$

Descripción del algoritmo

Un código no maleable garantiza que el experimento de manipulación dé como resultado un mensaje decodificado correcto o que el mensaje decodificado sea completamente independiente y no esté relacionado con el mensaje fuente . En otras palabras, la noción de no maleabilidad para códigos es similar, en espíritu, a las nociones de no maleabilidad para primitivos criptográficos (como el cifrado2, los compromisos y las pruebas de conocimiento cero), introducidas por el trabajo seminal de Dolev, Dwork y Naor. ^[4] ${\displaystyle s^{*}=s}$ ${\displaystyle s^{*}}$ ${\displaystyle s}$

En comparación con la corrección de errores o la detección de errores , la formalización "correcta" de los códigos no maleables es algo más difícil de definir. Sea una variable aleatoria para el valor del mensaje decodificado, que resulta cuando ejecutamos el experimento de manipulación con source-message y tampering-function , sobre la aleatoriedad del procedimiento de codificación. Intuitivamente, deseamos decir que la distribución de es independiente del mensaje codificado . Por supuesto, también queremos permitir el caso en el que el experimento de manipulación dé como resultado (por ejemplo, si la función de manipulación es identity), que claramente depende de . ${\displaystyle Tamper_{s}^{f}}$ ${\displaystyle s}$ ${\displaystyle f}$ ${\displaystyle Tamper_{s}^{f}}$ ${\displaystyle s}$ ${\displaystyle s^{*}=s}$ ${\displaystyle s}$

Por lo tanto, requerimos que para cada función de manipulación , exista una distribución que genere valores concretos o un mismo símbolo especial, y modele fielmente la distribución de para todos en el siguiente sentido: para cada mensaje fuente , las distribuciones de y son estadísticamente cercanas cuando el símbolo se interpreta como . Es decir, simula correctamente el "resultado" del experimento de manipulación con una función sin conocer los mensajes fuente , pero se permite cierta ambigüedad al generar un mismo símbolo para indicar que el mensaje decodificado debe ser el mismo que el mensaje fuente, sin especificar cuál es el valor exacto. El hecho de que dependa solo de y no de , muestra que el resultado de es independiente de , eximiendo la igualdad. ${\displaystyle f\in F}$ ${\displaystyle D_{f}}$ ${\displaystyle s^{*}}$ ${\displaystyle *}$ ${\displaystyle Tamper_{s}^{f}}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle Tamper_{s}^{f}}$ ${\displaystyle D_{f}}$ ${\displaystyle *}$ ${\displaystyle s}$ ${\displaystyle D_{f}}$ ${\displaystyle f\in F}$ ${\displaystyle s}$ ${\displaystyle *}$ ${\displaystyle D_{f}}$ ${\displaystyle f}$ ${\displaystyle s}$ ${\displaystyle Tamper_{s}^{f}}$ ${\displaystyle s}$

Relación con la corrección/detección de errores

Obsérvese que la no maleabilidad es una garantía más débil que la corrección/detección de errores; esta última asegura que cualquier cambio en la palabra clave pueda ser corregido o al menos detectado por el procedimiento de decodificación, mientras que la primera permite modificar el mensaje, pero solo a un valor no relacionado. Sin embargo, al estudiar la corrección/detección de errores , generalmente nos limitamos a formas limitadas de manipulación que preservan alguna noción de distancia (por ejemplo, generalmente la distancia de Hamming ) entre la palabra clave original y la alterada. Por ejemplo, ya es imposible lograr la corrección/detección de errores para la familia simple de funciones que, para cada constante , incluye una función " constante " que asigna todas las entradas a . Siempre hay alguna función en que asigna todo a una palabra clave válida . Por el contrario, es trivial construir códigos que no sean maleables con respecto a , ya que la salida de una función constante es claramente independiente de su entrada. Los trabajos anteriores sobre códigos no maleables muestran que se pueden construir códigos no maleables para familias de funciones de manipulación altamente complejas para las que no se puede lograr la detección o corrección de errores. ^[1] ${\displaystyle F_{const}}$ ${\displaystyle c^{*}}$ ${\displaystyle f_{c^{*}}}$ ${\displaystyle c^{*}}$ ${\displaystyle F_{const}}$ ${\displaystyle c^{*}}$ ${\displaystyle F_{const}}$ ${\displaystyle F}$

Aplicación sobre funciones de manipulación

Manipulación independiente bit a bit

Como ejemplo muy concreto, estudiamos la no maleabilidad con respecto a la familia de funciones que especifican, para cada bit de la palabra código , si se debe mantener como está, invertirlo, ponerlo a 0, ponerlo a 1. Es decir, cada bit de la palabra código se modifica arbitrariamente pero independientemente del valor de los otros bits de la palabra código. Llamamos a esto la familia de “manipulación independiente bit a bit” . Nótese que esta familia contiene funciones constantes y funciones de error constante como subconjuntos. Por lo tanto, como hemos mencionado, no se puede lograr la corrección y detección de errores con respecto a esta familia. Sin embargo, lo siguiente puede mostrar un código no maleable eficiente para esta poderosa familia. ${\displaystyle f}$ ${\displaystyle c}$ ${\displaystyle F_{BIT}}$ ${\displaystyle F_{const}}$ ${\displaystyle F_{err}}$

Con 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 que están definidas por n funciones (para i=1...n) como . Tenga en cuenta que solo hay 4 opciones posibles para cada una (es decir, cómo modificar un bit en particular) y las llamamos "establecer en 0", "establecer en 1", "voltear", "mantener" donde los significados deberían ser intuitivos. Llamamos a la familia anterior la familia de manipulación independiente bit a bit. ${\displaystyle F_{BIT}}$ ${\displaystyle f_{i}:\left\{{0},{1}\right\}^{n}\to \left\{{0},{1}\right\}^{n}}$ ${\displaystyle f_{i}:\left\{{0},{1}\right\}\to \left\{{0},{1}\right\}}$ ${\displaystyle f(c_{1}..c_{n})=f_{1}(c_{1})..f_{n}(c_{n})}$ ${\displaystyle f_{i}}$

Todas las familias de tamaño acotado

• Enfoque del método probabilístico

Para cualquier familia de funciones "suficientemente pequeña" , existe un esquema de codificación (posiblemente ineficiente) que no es maleable con respecto a F. Además, para una familia de funciones "suficientemente pequeña" fija , es probable que un esquema de codificación aleatorio no sea maleable con respecto a F con una probabilidad abrumadora. Desafortunadamente, los esquemas de codificación aleatorios no se pueden representar de manera eficiente, ni es probable que la función de codificación/decodificación sea eficiente. Por lo tanto, este resultado simplemente debe considerarse como una muestra de "posibilidad" y un objetivo que luego 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 verdadero para las nociones anteriores. ${\displaystyle F}$ ${\displaystyle F}$

• Enfoque del modelo aleatorio de Oracle

No está claro qué implica realmente el límite 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 sólo nos interesan esos) no pueden ser no maleables con respecto a esta clase. Sin embargo, el resultado del método probabilístico nos da códigos que no son maleables con respecto a clases muy generales de funciones en el modelo de oráculo aleatorio.

Modelo de seguridad resistente a manipulaciones

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

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

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

Un atacante que también puede interactuar con el sistema a través de consultas de manipulación puede potencialmente aprender mucho más 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 de manipulación (al menos para funciones f en alguna gran familia ) no pueda proporcionar al atacante información adicional. Al usar código no maleable para este propósito, llegamos a la conclusión: Sea cualquier esquema de codificación que no sea maleable con respecto a , entonces también puede simular la manipulación con respecto a . ${\displaystyle F}$ ${\displaystyle (Enc,Dec)}$ ${\displaystyle F}$ ${\displaystyle (Enc,Dec)}$ ${\displaystyle F}$

Capacidad de códigos no maleables

1. Para cada familia con , existen códigos no maleables contra con una tasa arbitrariamente cercana a 1 − (esto se logra mediante una construcción aleatoria). ^[5] ${\displaystyle F}$ ${\displaystyle |F|\leq 2^{2^{\alpha n}}}$ ${\displaystyle F}$ ${\displaystyle \alpha }$
2. Para familias de tamaño contra el cual no existe un código no maleable de tasa 1 − (de hecho este es el caso para una familia aleatoria de este tamaño). ${\displaystyle exp(n^{O(1)}2^{\alpha n})}$ ${\displaystyle \alpha }$
3. 1 − es la mejor tasa alcanzable para la familia de funciones a las que solo se les permite alterar los primeros bits de la palabra código, lo cual es de especial interés. ${\displaystyle \alpha }$ ${\displaystyle \alpha n}$

Referencias

1. Dziembowski, Stefan; Pietrzak, Krzysztof; Wichs, Daniel (2018). "Códigos no maleables". J. ACM . 65 (4): 20:1–20:32. doi :10.1145/3178432.Véase también la versión preliminar, Archivo de ePrint de Criptología, artículo 2009/608
2. Faust, Sebastian; Mukherjee, Pratyay; Venturi, Daniele; Wichs, Daniel (2014). "Códigos no maleables eficientes y derivación de claves para circuitos de manipulación de múltiples tamaños". Avances en criptología – EUROCRYPT 2014 (PDF) . Apuntes de clase en informática. Vol. 8441. págs. 111–128. doi :10.1007/978-3-642-55220-5_7. ISBN 978-3-642-55219-9.
3. E. Shannon, Claude (1949). "Teoría de la comunicación de los sistemas secretos". Bell System Technical Journal . 28 (4): 656–715. doi :10.1002/j.1538-7305.1949.tb00928.x. hdl : 10338.dmlcz/119717 .
4. Dolev, Danny; Dwork, Cynthia; Moni, Naor (24 de marzo de 2000). "Criptografía no maleable". Revista SIAM de informática . 30 (2): http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=9A853A59C3A45DD1B67690F10232D635?doi=10.1.1.26.8267&rep=rep1&type=pdf. CiteSeerX 10.1.1.49.4643 . doi :10.1137/s0097539795291562. 
5. Cheraghchi, Mahdi; Guruswami, Venkatesan (2 de septiembre de 2013). "Capacidad de Códigos No Maleables". arXiv : 1309.0458 [cs.IT].