Seguridad Demostrable y Reducciones

La seguridad demostrable demuestra que romper un esquema criptográfico es al menos tan difícil como resolver un problema que se considera intratable, al proporcionar una reducción explícita del problema que se supone difícil a cualquier ataque al esquema.

Definition

Una reducción de seguridad es una prueba que transforma cualquier adversario eficiente que rompe un esquema criptográfico en un algoritmo eficiente que resuelve un problema que se supone difícil, demostrando así que el esquema es seguro a menos que ese problema sea fácil.

Scope

Este tema cubre la metodología basada en la reducción de las pruebas criptográficas: la estructura de una reducción de seguridad, la rigurosidad y la seguridad concreta, los estilos de prueba basados en juegos y basados en simulación, el modelo de oráculo aleatorio y el modelo estándar, y los límites y críticas del enfoque. Aborda cómo se establecen y argumentan las garantías de seguridad. Excluye las suposiciones de dificultad específicas y las definiciones y modelos de adversario, que se tratan en temas relacionados.

Core questions

• ¿Cómo traduce una reducción un ataque a un esquema en una solución a un problema difícil?
• ¿Cuál es la diferencia entre las pruebas basadas en juegos y las basadas en simulación?
• ¿Qué significa la 'rigurosidad' de una reducción para los parámetros de seguridad del mundo real?
• ¿Qué son el modelo de oráculo aleatorio y el modelo estándar, y por qué el primero es controvertido?
• ¿Cuáles son los límites y las trampas comunes de los argumentos de seguridad demostrable?

Key concepts

• reducción de seguridad
• pruebas basadas en juegos
• pruebas basadas en simulación
• reducciones rigurosas vs. laxas
• seguridad concreta
• modelo de oráculo aleatorio
• modelo estándar
• ventaja despreciable
• suposición de dificultad

Key theories

Metodología de prueba reduccionista

Para probar la seguridad de un esquema, se asume un adversario que lo rompe y se construye, utilizando ese adversario como subrutina, un algoritmo que resuelve el problema difícil subyacente; así, un ataque exitoso contradeciría la suposición de dificultad.

El modelo de oráculo aleatorio

Muchos esquemas eficientes se demuestran seguros idealizando una función hash como un oráculo verdaderamente aleatorio; el modelo permite pruebas para construcciones prácticas, pero es heurístico, ya que ninguna función real es un oráculo aleatorio.

Mechanisms

En una reducción, el probador asume un adversario hipotético que rompe el esquema con una ventaja no despreciable y construye un envoltorio que incrusta una instancia del problema difícil en la vista del adversario, ejecuta al adversario y utiliza su salida para resolver el problema. Las pruebas basadas en juegos proceden a través de una secuencia de juegos indistinguibles desde el esquema real hasta uno en el que el adversario claramente no puede ganar. La rigurosidad de la reducción —cuánta ventaja y tiempo de ejecución se pierden— determina los tamaños de clave necesarios para un nivel de seguridad objetivo.

Clinical relevance

La seguridad demostrable es el estándar por el cual los esquemas criptográficos ganan confianza y estandarización: los procesos AES, SHA-3 y post-cuánticos del NIST sopesaron en gran medida las pruebas de seguridad, y protocolos como TLS 1.3 fueron acompañados por análisis reduccionistas y verificados por máquina. Comprender las reducciones permite a los profesionales juzgar lo que una afirmación de seguridad garantiza y no garantiza, y elegir parámetros que tengan en cuenta la rigurosidad de la reducción.

Evidence & guidelines

La práctica moderna favorece las pruebas en el modelo estándar cuando es factible y trata las pruebas de oráculo aleatorio como evidencia heurística sólida en lugar de garantías absolutas. Los marcos asistidos por herramientas (EasyCrypt, CryptoVerif) proporcionan pruebas verificadas por máquina. El análisis de seguridad concreto (exacto), que cuantifica la ventaja del adversario en función de los recursos, se prefiere sobre las declaraciones puramente asintóticas para establecer parámetros reales.

History

La metodología reduccionista surgió con la revolución definicional de principios de la década de 1980 y se sistematizó a lo largo de la década de 1990. Bellare y Rogaway introdujeron el modelo de oráculo aleatorio (1993) para probar la seguridad de esquemas prácticos, y más tarde el análisis de 'seguridad concreta' para cuantificar las garantías. El resultado de Canetti, Goldreich y Halevi de 1998, que mostraba esquemas seguros en el modelo de oráculo aleatorio pero inseguros cuando se instanciaban, agudizó el debate sobre los modelos idealizados.

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

¿Una prueba de seguridad significa que un esquema nunca puede ser roto?

No. Una prueba demuestra que romper el esquema implica resolver un problema que se supone difícil dentro de un modelo especificado. Si la suposición falla, el modelo no es realista o la implementación se desvía del esquema analizado, los ataques siguen siendo posibles. Las pruebas reducen, pero no eliminan, el riesgo.

¿Por qué el modelo de oráculo aleatorio se considera controvertido?

Modela una función hash como una función perfectamente aleatoria, lo cual ninguna función concreta es realmente. Las pruebas en este modelo son una fuerte evidencia y permiten esquemas eficientes, pero existen esquemas (artificiales) seguros en el modelo pero inseguros una vez que el oráculo es reemplazado por cualquier hash real, por lo que tales pruebas son heurísticas.