¿Consecuencias de factorizar estar en P?

No se sabe que la factorización es NP-completa. Esta pregunta solicitó las consecuencias de que Factoring sea NP-completo. Curiosamente, nadie preguntó por las consecuencias de Factoring estar en P (tal vez porque esa pregunta es trivial).

Entonces mis preguntas son:

Cual seria el teorico consecuencias de Factoring estar en P? ¿Cómo la situación general de las clases de complejidad se vería afectada por tal hecho?
¿Cuáles serían las consecuencias prácticas de Factoring estar en P? Por favor, no diga que las transacciones bancarias podrían estar en peligro, ya conozco esta consecuencia trivial.

cc.complexity-theory cr.crypto-security conditional-results factoring Giorgio Camerani
fuente

Hace unos días hice una pregunta similar: "¿Cuál es el poder de P con un oráculo de factorización de enteros?" cstheory.stackexchange.com/questions/4765/…

Marzio De Biasi

También relacionado: ¿Cuáles son las consecuencias de factorizar ser NP-completo?

Kaveh

@Kaveh, la pregunta ya está vinculada a esa.

Peter Taylor

Respuestas:

Prácticamente no hay consecuencias teóricas de la complejidad de Factoring estando en P. Esto significa que no hay buenas justificaciones para factoring ser difícil, aparte de que nadie ha sido capaz de descifrarlo hasta ahora.

La factorización en tiempo polinomial permitiría tomar raíces cuadradas sobre (y también sobre una clase mucho más general de anillos también), y proporcionar algoritmos de tiempo polinomial para una serie de otros problemas de teoría de números para los cuales el cuello de botella en El algoritmo está factorizando actualmente. $Z_n$

En cuanto a las consecuencias prácticas, las transacciones bancarias probablemente no sean un gran problema: tan pronto como se supiera que el factoring estaba en P, los bancos cambiarían a otro sistema, lo que probablemente causaría solo un breve período de demoras mientras esto ocurría. implementado. Decodificar transacciones bancarias pasadas probablemente no causaría serios problemas a los bancos. Un problema mucho más grave es que toda la comunicación que antes estaba protegida por RSA ahora estaría en peligro de ser leída.

Peter Shor
fuente

Un poco fuera de tema, pero as soon as it was known that factoring was in P, the banks would switch to some other systemes en gran medida una ilusión. Descubrí en diciembre que una compañía que no hace nada más que procesar los detalles de la tarjeta de crédito estaba usando una variante de Vigenère con una clave más corta que algunas series de texto sin formato conocido. Peor aún, el director técnico de la compañía no me creería que era inseguro hasta que le envié un código de ataque. MD5, a pesar de ser ampliamente considerado roto, todavía se usa mucho en la banca.

Peter Taylor

@PeterTaylor, tan pronto como se supo que el factoring estaba en P, los bancos cambiarían a algún otro sistema es en gran medida una ilusión ". Con el precio barato actual de la memoria Flash, es completamente factible crear una solución One Time Pad para la banca, los usuarios pueda ir de vez en cuando a un cajero automático para descargar bytes aleatorios adicionales RSA es más barato y más simple..

Flávio Botelho

Tener cifrados simétricos fuertes no reemplaza los cifrados asimétricos, aunque es suficiente para ciertas tareas específicas. Te encuentras con el problema de no poder usar firmas digitales, etc.

Joe Fitzsimons

En realidad, ¡puedes tener firmas digitales con cifrados simétricos! Es mucho más engorroso y necesita una confianza mucho mayor en el tercero de confianza. Consulte los capítulos 11.6 y 11.7 del Manual de criptografía aplicada.

Flávio Botelho

@Flavio: Pero el no repudio no funciona de la misma manera, ¿verdad?

Joe Fitzsimons

RSA es uno de los esquemas de cifrado / firma más importantes que se rompe si FACTORING está en P. Sin embargo, hay muchos más. Varios (pero no todos) de ellos se basan en la suposición de que distinguir cuadrados y módulos no cuadrados de un número compuesto es difícil :

Y muchos otros esquemas. Sin embargo, tenga en cuenta que los esquemas basados en la dureza del registro discreto (digamos, el protocolo Diffie-Helmann o el esquema de cifrado / firma Elgamal ) continuarán siendo seguros.

MS Dousti
fuente

Me parece muy probable que si la factorización está en P, también lo sea el problema de registro discreto. Ciertamente lo contrario es cierto.

Joe Fitzsimons

@ Joe: Tengo los mismos sentimientos, pero ¿hay alguna prueba o evidencia matemática?

MS Dousti

a^{p q} \equiv a^{p + q - 1} (mod p q)

$a^{pq} \equiv a^{p+q-1}~(\mbox{mod } pq)$

c_{a} = \log_{N} (a^{N} mod N)

$c_a = \log_N(a^N \mbox{mod }N)$

p = x + y

$p = x + y$

q = x - y

$q = x - y$

x = \frac{c_{a} + 1}{2}

$x = \frac{c_a + 1}{2}$

y = \sqrt{x^{2} - N}

$y = \sqrt{x^2 - N}$

@ Joe: ¡Muy interesante! Su comentario me motivó a profundizar más en esto, y encontré un resultado de Eric Bach que afirma que " resolver el problema de logaritmo discreto para un módulo compuesto es exactamente tan difícil como factorizarlo y resolverlo con módulos primos " .

MS Dousti

Sin embargo, la criptografía basada en celosía debería permanecer segura.

Antimonio

$P$

Mohammad Al-Turkistany
fuente