Reason Coppersmith fails here?

Question

Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$.

$P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and $y_1$ through $y_{\lceil\log Q\rceil}$ and solve $$(\sum_{i=0}^{\lceil\log P\rceil}2^ix_i)(\sum_{i=0}^{\lceil\log Q\rceil}2^iy_i)=N.$$

The polynomial $$f(x_1,\dots,x_{\lceil\log P\rceil},y_1,\dots,y_{\lceil\log Q\rceil})=(\sum_{i=0}^{\lceil\log P\rceil}2^ix_i)(\sum_{i=0}^{\lceil\log Q\rceil}2^iy_i)-N$$ should be irreducible. Howgrave-Graham condition says roots of $$f(x_1,\dots,x_{\lceil\log P\rceil},y_1,\dots,y_{\lceil\log Q\rceil})\equiv0\bmod R$$ at an $R\in\mathbb N$ are roots of $$f(x_1,\dots,x_{\lceil\log P\rceil},y_1,\dots,y_{\lceil\log Q\rceil})=0$$ over $\mathbb Z$ if $$\|f(x_1X_1,\dots,x_{\lceil\log P\rceil}X_{\lceil\log P\rceil},y_1Y_1,\dots,y_{\lceil\log Q\rceil}Y_{\lceil\log Q\rceil})\|<\frac{R}{\sqrt{\lceil\log P\rceil\lceil\log Q\rceil}}$$ (here $X_i=Y_j=1$) is satisfied. I can take a very large prime $R\gg N$ and make it satisfy the Howgrave-Graham condition.

Howgrave-Graham is itself insufficient and is only a necessary condition. However the bounds needed for Coppersmith might be improvable if we had a free hand in size of $R$.

Does Coppersmith's algorithm help even though it might be exponential time because of the degree of the polynomials involved? Only problem is we cannot guarantee independence of polynomials generated from lattice with LLL reduced basis because of non-bivariate nature. However will this heuristically make sense? I think it should not but I do not see reason why not.

The reason it should not is we could have used the same argument for $$XY=N$$ and approached with $$XY-N\equiv0\bmod R$$ at prime $R\gg N$ by using some other weighted shifts of $XY-N$ to generate lattice instead of $X^{i_1}Y^{i_2}(XY-N)^jN^{m-j}$ if done $\bmod N^m$ which might lead to much better bounds. In this case we have bivariate polynomial and Coppersmith's algorithm guarantees independence. I think there is a bound on what $R$ should be and some relation to $N$.

1. If $R$ can be bigger than $N$ then how big can it be and what relation with $N$ does it satisfy?

2. Complexity of Coppersmith is discussed in page $46$ in https://pure.tue.nl/ws/files/1796260/200711750.pdf. It seems Coppersmith's method is in $P$ only if number unknowns is fixed. Is this complexity true. If so what exactly is complexity of Coppersmith's method?

Answer 1

For starter, your polynomial is reducible over the integer, so it can not be used to generate a linearly independent basis by the LLL algorithm.

There are many constraints imposed on the polynomials $f(x_0,x_1,...,x_n)$, such as

a) $f$ is irreducible over the integer, actually absolutely irreducible.

b) The variables $x_0$, ..., $x_n$ satisfy certain algebraic conditions.

c) The total degree $\deg(f)=d$ restricts the bounds of the roots $|x_i| <W^{c d}$, where $W$ is the weight of the polynomial, and $c>0$ is a constant.

d) Etc.

Some heuristic for polynomials of 3 variables was considered by Bauer in her thesis.

1. Aurelie Bauer; Antoine Joux; Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables, ); EUROCRYPT 2007, LNCS 4515, pp. 361–378, 2007.