Si P = NP, ¿qué es criptográficamente seguro? [duplicar]

Question

Si P = NP, ¿qué es criptográficamente seguro? [duplicar]

#1 de aaveg (0 votos)
#2 de dr jimbob (0 votos)

0

Lo sé, lo sé: "Si P = NP" es una suposición realmente grande y de alto impacto.

Pero esto es hipotético.

Quiero decir, claramente RSA (y métodos similares de ofuscación) probablemente se volverían totalmente irrelevantes, ¿o no? Ser solucionable en tiempo polinómico en vez de exponencial sería un golpe importante para su operación, pero ¿podrían hacer uso de claves públicas / privadas tan grandes (si P = NP, entonces es probable que sean más eficientes los localizadores de números primos) que las grietas? ¿Sigue siendo algo "difícil?"

En su mayoría son solo puntos de discusión. En cuanto a la pregunta en bruto: ¿Qué métodos de criptografía no dependen en última instancia de P! = NP?

passwords cryptography encryption

pregunta Curious 15.03.2014 - 13:43

fuente

2 respuestas

Lea otras preguntas en las etiquetas passwords cryptography encryption

¿Las cookies transitorias para la administración de sesiones no aumentan la efectividad de MITM? Problemas de acceso ASDM ASA5505 de Cisco [cerrado]

score 0 · Answer 1

Cualquier esquema de criptografía clásica es de naturaleza algorítmica, es decir, cualquier esquema de criptografía clásica se puede romper (en principio). El próximo campo de la información cuántica creo que algún día podrá hacer que la comunicación sea segura. Si desea leer más sobre los protocolos de distribución de claves cuánticas, intente buscar: el protocolo BB84, el protocolo B92 y el protocolo eckert.

score 0 · Answer 2

Depende. Si P = NP, pero el mejor algoritmo para resolver un NP general completo como SAT es decir O (N ^ 10) con constantes adecuadamente grandes, entonces, a pesar de ser polinomial, nuestra criptografía convencional para los valores de N utilizados hoy en día seguirá siendo válida. Si P = NP con soluciones para un problema general de NP completo que se dice O (N ^ 3) con constantes adecuadamente pequeñas, entonces una gran cantidad de criptografía se volverá bastante débil.

La verificación de la primalidad ya es bastante eficiente (no es un tiempo exponencial), por lo que una reducción de SAT a P no necesariamente aceleraría las búsquedas de números primos de manera significativa.