Es la versión de grado total y $x,y$ ¿es correcta la versión de grado del teorema de Coppersmith?

Question

Las notas aquí https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf tienen la nota "Pequeño exponente de descifrado $d$ : hasta ahora el mejor ataque conocido recupera $d$ si es inferior a $N^{.292}$ . Esto utiliza una versión bivariada de Coppersmith que carece de una prueba rigurosa de corrección, pero parece funcionar bien en la práctica'. Parece que el documento en cuestión de Coppersmith es https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf y en particular el Teorema 2, el Corolario 2 y el Teorema 3.

1. En 'A Note on the Bivariate Coppersmith Theorem' de Jean-Sébastien Coron et al se publicó una versión corregida del Corolario 2 que sigue al Teorema 2, por lo que supongo que el Teorema 2 está bien. Sin embargo, no dice nada sobre el Teorema 3. El enlace correspondiente es https://link.springer.com/content/pdf/10.1007%2Fs00145-012-9121-x.pdf . ¿Sabemos si el teorema 3 de 'Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities' de Don Coppersmith también es válido?

2. En la versión conferencia https://nymity.ch/anomalous-tor-keys/pdf/Coppersmith1996a.pdf en el teorema $3$ tiene un resultado en el que los límites de las raíces dependen del grado individual ( $\delta$ es $x$ -y $\tau$ es $y$ -grado) en lugar del grado total. No parece que esta versión aparece en la versión de la revista en la introducción en este post. ¿Es correcta esta versión del teorema? ¿Hay referencias que aparecen más allá de esta publicación de la conferencia?

Answer 1

Me pidieron que comentara aquí, pero esta pregunta parece más relevante para el stackexchange de criptografía. ¿Sería apropiado un traslado?

De todos modos, aquí hay tres cuestiones.

1. Creo que el mismo argumento que presentamos en nuestro Nota sobre el teorema bivariante de Coppersmith también se aplica al Teorema 3, pero no he realizado el cálculo completo. Dado que debería funcionar exactamente igual, no debería ser difícil adaptar la prueba para estar seguro.

2. La observación que sigue al Teorema 3 en la versión de la revista del artículo de Coppersmith aborda la cuestión de los grados distintos en $x$ y $y$ (sin pruebas, pero no es un ejercicio difícil hacerlo).

3. El punto más importante es que el problema menor con la búsqueda exhaustiva es no a lo que se refiere Peikert sobre la falta de una versión bivariante rigurosa de Coppersmith. Lo que se necesita para el ataque Boneh-Durfee de exponente pequeño contra RSA es una versión del teorema de Coppersmith les deux en dos variables y módulo $N$ y no sabemos cómo conseguirlo con rigor.

   El problema es que la técnica de reducción reticular de Coppersmith da polinomios linealmente independientes que desaparecen en las raíces que queremos, pero para recuperarlos realmente, necesitamos que los polinomios sean algebraicamente independientes, y esta condición de independencia algebraica es difícil de establecer. En ataques prácticos reales, parece cumplirse esencialmente todo el tiempo, por lo que los criptoanalistas suelen contentarse con suponer heurísticamente que se cumple la condición. Sin embargo, también se pueden encontrar casos en los que la heurística falla, por lo que se ha trabajado para intentar obtener algoritmos con pruebas completamente rigurosas, con un éxito limitado hasta el momento.

   En la tesis doctoral de Aurélie Bauer puede encontrarse un amplio debate sobre este problema, Hacia una generalización rigurosa de los métodos de Coppersmith Métodos de Coppersmith para la búsqueda de pequeñas raíces de pôlynomes (UVSQ, 2008). Uno de los resultados de la tesis es un versión rigurosa de Coppersmith en 3 variables sobre los enteros que se acerca, pero desgraciadamente no lo suficiente, a lo que se necesita para Boneh-Durfee.