On Efficiently Calculating Small Solutions of Systems of Polynomial Equations - Lattice-Based Methods and Applications to Cryptography
Maike Ritzenhofen
Abstract:
Many problems related to cryptography can be described by a polynomial equation or a system of polynomial equations. The solution of the problem then corresponds to a solution of the equation. As examples of such problems the RSA broadcast scenario as well as the problem of implicit factoring are analyzed using basic lattice-based techniques.
A more complex lattice-based algorithm to efficiently calculate small solutions of a polynomial has been introduced by Don Coppersmith in 1996. We present neccessary and sufficient conditions to extend the algorithm to systems of polynomial equations.
Finally, we apply the extended algorithm to special systems of equations, including the problem of implicit factoring, and compare it with different approaches.
Download