**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.

**Category / Keywords: **public-key cryptography / Multivariate Coppersmith's method, Implicit Hint Factoring, RSA

**Publication Info: **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.

**Date: **received 7 May 2010, withdrawn 13 May 2010

**Contact author: **raphael marinier at polytechnique edu

**Available format(s): **(-- withdrawn --)

**Version: **20100513:190515 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]