Paper 2010/263

Lattice Reduction and Polynomial Solving

Raphaël Marinier

Abstract

In this paper, we suggest a generalization of Coppersmith's method for finding integer roots of a multivariate polynomial. Our generalization allows finding integer solutions of a system of $k$ multivariate polynomial equations. We then apply our method to the so-called implicit factoring problem, which constitutes the main contribution of this paper. The problem is as follows: let $N_1 = p_1 q_1$ and $N_2 = p_2 q_2$ be two RSA moduli of same bit-size, where $q_1, q_2$ are $\alpha$-bit primes. We are given the \emph{implicit} information that $p_1$ and $p_2$ share $t$ most significant bits. We present a novel and rigorous lattice-based method that leads to the factorization of $N_1$ and $N_2$ in polynomial time as soon as $t \ge 2 \alpha + 3$. Subsequently, we heuristically generalize the method to $k$ RSA moduli $N_i = p_i q_i$ where the $p_i$'s all share $t$ most significant bits (MSBs) and obtain an improved bound on $t$ that converges to $t \ge \alpha + 3.55\ldots$ as $k$ tends to infinity. This paper extends the work of May and Ritzenhofen in \cite{DBLP:conf/pkc/MayR09}, where similar results were obtained when the $p_i$'s share least significant bits (LSBs). In \cite{sarkar2009further}, Sarkar and Maitra describe an alternative but heuristic method for only two RSA moduli, when the $p_i$'s share LSBs and/or MSBs, or bits in the middle. In the case of shared MSBs or bits in the middle and two RSA moduli, they get better experimental results in some cases, but we use much lower (at least 23 times lower) lattice dimensions. Our results rely on the following surprisingly simple algebraic relation in which the shared MSBs of p_1$ and $p_2$ cancel out: $q_1 N_2 - q_2 N_1 = q_1 q_2 (p_2 - p_1)$. This relation allows us to build a lattice whose shortest vector yields the factorization of the $N_i$'s.

Metadata
Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Published elsewhere. Some of the results contained in this Master's Thesis will be published at the PKC 2010 conference. This paper gives however a very detailed explanation of how the result published at PCK 2010 have been found. This explanation is not included in the paper that will be published. Besides, some proofs are described in more details.
Keywords
Multivariate Coppersmith's methodImplicit Hint FactoringRSA
Contact author(s)
raphael marinier @ polytechnique edu
History
2010-05-13: withdrawn
2010-05-07: received
See all versions
Short URL
https://ia.cr/2010/263
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.