Supongamos que y mañana aparece un algoritmo de tiempo lineal rápido para SAT. De repente, RSA es inseguro, gran parte de nuestro sistema de comunicación moderno está roto y necesitamos reconsiderar cómo mantener secretos entre nosotros.
Pregunta: ¿Existe una buena referencia única (o lista corta) para obtener una visión general de lo que es posible en criptografía (y en el campo aliado de "seguridad") sin suposiciones de intratabilidad? Esto podría salvar la civilización algún día, y también sería bueno leerlo mientras tanto.
Discusión: La mayoría de las tareas criptográficas que estudiamos ahora (OWF, PRG, PKE) son probablemente imposibles en el mundo (un mundo denominado "Algorithmica" en un influyente ensayo de Impagliazzo), pero algunas cosas siguen siendo posibles: comunicación con una almohadilla de una sola vez ; distribuido compartición de secretos ; recuperación de información privada ; y algunas otras cosas bonitas. (Ciertos tipos de mecanismos físicos, como cajas bloqueadas , dispositivos que implementan transferencias inconscientes y estados cuánticos también pueden ser útiles. Por supuesto, siempre hay algún tipo de suposición física sobre quién puede ver qué información).
Se puede distinguir entre la seguridad teórica de la información (que funciona contra un adversario computacionalmente ilimitado) y la seguridad "incondicional" (que puede requerir un adversario limitado, pero aún muestra seguridad bajo supuestos no comprobados). Estoy más interesado en el caso de la teoría de la información.
Para empezar, aquí hay una bibliografía de seguridad teórica de la información (que, para mi propósito, es inmanejablemente larga y dispar).
fuente
Respuestas:
Las frases clave que probablemente esté buscando son "criptografía teórica de la información" y "criptografía cuántica". Buscar en la literatura sobre estos temas le dará mucho trabajo del tipo que está buscando. Algunos ejemplos destacados a continuación:
Para confidencialidad: el pad de una sola vez, el canal de escuchas telefónicas de Wyner, el intercambio secreto, el intercambio de claves cuánticas, etc.
Para integridad y autenticación: funciones hash universales.
Para el anonimato: comunicación anónima (p. Ej., Redes DC, esquemas basados en cebolla, redes p2p basadas en la mezcla rápida de caminatas aleatorias), protocolos de límite de distancia.
Para seguridad basada en suposiciones físicas: PUF (funciones físicamente no razonables), códigos de integridad (Capkun et al.), Criptografía cuántica, seguridad usando TPM o hardware resistente a la manipulación.
Hay muchos documentos sobre esos temas; demasiados para resumir todos los resultados en la literatura.
fuente
Esta es una pregunta bastante compleja, ya que realmente no tenemos una buena visión general del área. En parte, esto se debe al hecho de que la teoría de la información y la comunidad criptográfica han estado trabajando en temas similares sin realmente interactuar lo suficiente entre sí. Muchos buenos puntos se han dado anteriormente. Solo me gustaría agregar algunas observaciones adicionales:
Hemos tenido una gran cantidad de trabajos relacionados con el problema del acuerdo de clave secreta (y la comunicación segura) con una configuración determinada. Aquí, una configuración significa, por ejemplo, que las partes en el sistema (por ejemplo, Alice, Bob y la adversaria Eve) comparten información correlacionada proveniente de una distribución de probabilidad tripartita. Una configuración alternativa podría consistir en canales ruidosos (por ejemplo, Alice puede enviar información a Bob y Eve a través de canales ruidosos). Además, Alice y Bob están conectados a través de un canal de comunicación (que puede o no estar autenticado). Esta línea de trabajo comenzó con Aaron Wyner en los años 70, quien introdujo el modelo de canal Wiretap, y fue limpiado por Maurer y otros en los años 90. Además, muchas técnicas en esta área (amplificación de privacidad, la reconciliación de la información) terminó siendo utilizada en la configuración de distribución cuántica de claves (QKD). Hasta la fecha, se está realizando una buena cantidad de trabajo, por ejemplo, en áreas relacionadas, como extractores no maleables, etc. El modelo de almacenamiento limitado también es un entorno diferente al anterior, pero utiliza técnicas similares y tiene características similares. metas.
Más allá del simple intercambio secreto, encontrará una gran cantidad de trabajos sobre computación multipartita (MPC) teóricamente segura de información. En particular, la línea de trabajos iniciada por el protocolo BGW es completamente teórica de información.
Además, no estoy seguro de hasta dónde llega el alcance de la pregunta: si, por ejemplo, P = NP se cumple, pero de alguna manera podemos justificar la presencia de un oráculo aleatorio en el cielo, entonces la criptografía simétrica todavía es posible. A veces, tales modelos se utilizan para demostrar la seguridad de ciertas construcciones criptográficas (como funciones hash o cifrados de bloque), y las técnicas son completamente teóricas de la información.
Las técnicas teóricas de la información en criptografía también aparecen a menudo como una herramienta intermedia en los resultados teóricos de la complejidad, pero creo que esto está más allá del alcance de la pregunta. (Ver el trabajo de Maurer en sistemas aleatorios y en la amplificación de indistinguibilidad como un ejemplo de este tipo de trabajo).
fuente
Algunos grupos de investigación en Europa han seguido esta línea de investigación; más específicamente, debido a mi interés en la teoría de la información, me he encontrado con el trabajo de Ueli Maurer y su escuela, que es significativo desde el punto de vista puramente teórico de la información (con el que estoy más familiarizado) y también ofrece algunos enfoques prácticos de información seguridad teórica
En relación con la línea de trabajo anterior, algunos lugares que quizás desee considerar mirar son la tesis doctoral de Christian Cachin y también Renato Renner (más cuántico).
Por supuesto, hay un enfoque completamente diferente con palabras clave que incluyen BB84, Preskill-Shor, Artur Ekert, etc.
Lo anterior, por supuesto, solo refleja mi experiencia limitada, y seguramente hay muchos más enfoques y líneas de trabajo interesantes.
fuente