¿Son los límites inferiores asintóticos relevantes para la criptografía?

Generalmente se considera que un límite inferior asintótico, como la dureza exponencial, implica que un problema es "inherentemente difícil". Se cree que el cifrado que es "intrínsecamente difícil" de romper es seguro.

Sin embargo, un límite inferior asintótico no descarta la posibilidad de que una clase enorme pero finita de instancias problemáticas sea fácil (por ejemplo, todas las instancias con un tamaño inferior a ). $10^{1000}$

¿Hay alguna razón para pensar que la criptografía basada en límites inferiores asintóticos conferiría algún nivel particular de seguridad? ¿Los expertos en seguridad consideran tales posibilidades, o simplemente se ignoran?

Un ejemplo es el uso de funciones de trampillas basadas en la descomposición de grandes números en sus factores primos. En un momento se pensó que esto era inherentemente difícil (creo que exponencial era la conjetura), pero ahora muchos creen que puede haber un algoritmo polinomial (como lo es para las pruebas de primalidad). A nadie parece importarle mucho la falta de un límite inferior exponencial.

Creo que se han propuesto otras funciones de trampillas que se consideran NP-hard (ver pregunta relacionada ), y algunas incluso pueden tener un límite inferior comprobado. Mi pregunta es más fundamental: ¿importa cuál es el límite inferior asintótico? Si no, ¿la seguridad práctica de cualquier código criptográfico está relacionada con algún resultado de complejidad asintótica?

complexity-theory cryptography asymptotics Micah Beck
fuente

¡Bienvenido! No es un duplicado, pero está muy relacionado: esta pregunta . Para mejorar la pregunta, proporcione ejemplos concretos en los que crea que se ignora el problema. ¡No quieres estar luchando contra los molinos de viento!

Raphael

Respuestas:

Trataré de dar una respuesta parcial, ya que no soy plenamente consciente de cómo este tema es considerado por toda la comunidad criptográfica (¿tal vez volver a publicar en crypto.SE ?).

Yo diría que hay dos "tipos" de criptógrafos: teóricos y prácticos . No intentaré distinguirlos (cada criptógrafo práctico también es un poco teórico ...) pero lo diré para la criptografía teórica: este problema realmente no importa. Para cualquier parámetro de seguridad, habrá un tamaño de instancia que proporcionará ese nivel de seguridad, y eso es generalmente todo lo que nos importa.

Los criptógrafos prácticos se preocupan mucho por el problema que mencionas. Para un parámetro de seguridad dado (digamos ), los criptógrafos intentan encontrar los protocolos más eficientes, reduciendo la constante tanto como sea posible. Busque, por ejemplo, la competencia AES o SHA-3 de NIST . Se requería que los algoritmos fueran seguros y eficientes. El problema aquí es que la noción de seguridad es algo diferente de la noción "teórica", y a veces no es realmente asintótica. $2^{1024}$

Un ejemplo concreto en el que puedo pensar es el registro discreto o el supuesto DDH (la seguridad de muchos esquemas criptográficos se basa en estos supuestos). Nosotros suponemos que por algún grupo computar el registro de toma tiempo. (No podemos estar seguros: puede ser que y este problema se pueda resolver en ). Los criptógrafos HACEN $G$ $O(|G|)$ $\text{P}=\text{NP}$ $O(\log |G|)$ preocuparse por el tiempo real que lleva calcular el registro. Más exactamente, se preocupan mucho por casos especiales para los cuales calcular el registro es fácil. En muchos documentos verá la oración "Deje que sea un grupo en el que DDH es difícil". Vea esta encuesta para familias de grupos para los cuales se cree que DDH es intratable (a menos que P = NP). $G$

Sonó.
fuente

Esta respuesta no es terriblemente satisfactoria para mí, tal vez porque no soy lo suficientemente experta como para descubrir cómo aborda mi pregunta. Es cierto que no he estudiado la teoría de la complejidad durante unos 25 años, pero entiendo muchos de los conceptos subyacentes. Después de buscar algunas de las referencias vinculadas, parece que las caracterizaciones de complejidad utilizadas son asintóticas , por lo que todavía no puedo entender cómo pueden dar garantías utilizables sobre clases de instancias finitas .

Micah Beck