CryptoBook
Search…
Extensions of Coppersmith algorithm
The Coppersmith algorithm can be made even more general. There are two main extensions, first to an unknown modulus, then to multivariate polynomials.

# Unknown modulus

This extension of Coppersmith allows one to find small roots modulo an unknown some unknown factor of a number. More specifically, suppose that we have some unknown factor
$b$
of
$N$
such that
$b
and some monic polynomial
$f$
of degree
$d$
such that
$f(x_0)=0\pmod b$
for some
$x_0
. Then we can find
$x_0$
in time polynomial in
$\log N,d$
.
One key reason why this is possible is because we dont need to explicitly know the modulus to determine if a small root exists, i.e.
$\left\lVert f(Bx)\right\rVert_2\leq\frac b{\sqrt{d+1}}\leq\frac{N^{\beta}}{\sqrt{d+1}}$
is sufficient for a root less than
$B$
to exist. The algorithm here is extremely similar to the Coppersmith algorithm, except we add more polynomials into the lattice. The polynomials that we will use are
\begin{align*} g_{i,j}(x)&=N^{h-j}f(x)^jx^i&0\leq i
The lattice
$L$
generated by these polynomials would have
$\dim(L)=dh+t=n\quad\text{vol}(L)=N^{\frac{dh(h+1)}{2}}B^{\frac{(n-1)n}2}$
As we require the shortest vector to have length at most
$\frac{N^{\beta h}}{\sqrt{n}}$
, repeating the computations from the previous section, we obtain
$B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}}$
It turns out that the maxima of
$\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$
is
$\frac{\beta^2}d$
as
$n,h\to\infty$
. One way to achieve this is by setting
$n=\frac d\beta h$
and we obtain
$B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{(h-1)\beta^2}{dh-\beta}}$
and this indeed achieves the
$O\left(N^{\frac{\beta^2}d}\right)$
bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big
$h,n$
such that the remainding bits can be brute forced in constant time while the algorithm still remains in polynomial time.

# Exercises

1) We show that the maximum of
$\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$
is indeed
$\frac{\beta^2}d$
. We can assume that
$d\geq2,h\geq1,0<\beta\leq1,n\geq2$
. Since
$\frac h{n-1}\left(2\beta-d\frac{h+1}{n}\right)$
and
$\frac h{n-1}<\frac{h+1}n$
, the maximum occurs when
$h,n\to\infty$
and
$\frac h{n-1},\frac{h+1}n\to x$
, hence we have reduced this to maximizing
$2\beta x-dx^2$
which achieves its maximum of
$\frac{\beta^2}d$
at
$x=\frac\beta d$
.