I have reduced a cryptanalysis problem to solving for unknowns $a,b,c,d$ the Diophantine inequality $\big|a\,f\,(g+d\,h)-b\,h\,(e+c\,f)\big|<m$ with $0<c<a<m$, $0<d<b<m$.
Addition: If that helps, the context also insures $\big|a\,d-b\,c\big|<m$.
The integers $e,f,g,h,m$ are givens, with $0<e<f\,$, $0<g<h\,$, $\gcd(e,f)=1\,$, $\gcd(g,h)=1\,$, $f\approx m^3\,$, $h\approx m^3\,$. These givens are such that there is a solution, and I vaguely conjecture the later two conditions make it unlikely there are many others.
For the motivating problem, see this paper, and my refutation, that I try to extend. For an example problem (with numerical solution, matching section 5 of the paper and assuming the $x$ is unknown to the cryptanalyst), see this Mathematica code (updated to also illustrate the following).
Update: I made some progress.
- Let $r=a\,f\,(g+d\,h)-b\,h\,(e+c\,f)$. Taking this $\bmod h$ and $\bmod f$ it comes $r\equiv a\,f\,g\bmod h$ and $r\equiv b\,h\,e\bmod f$.
- Compute the integers $$\begin{array}{} \ell=\gcd(f,h)&&m'=\lceil m/\ell\rceil\\ f'=f/\ell&&h'=h/\ell\\ e'=(h'\,e)^{-1}\bmod f'&&g'=(d'\,g)^{-1}\bmod h' \end{array}$$ and define $s=r/\ell$, which is bound to be an integer.
- We have reduced the systems to a single unknown integer $s$ with $$ \begin{align} (g'\,s\bmod h')&<m\\ (e'\,s\bmod f')&<m\\ 0<\big|s\big|&<m' \end{align} $$ where the four $e'$, $f'$, $g'$, $h'$ are large known integers (like 30 decimal digits), and the other quantities and the unknown $s$ are much smaller (10 digits).
I think this can be solved efficiently (in time polynomial to the $\log$ of the parameters), perhaps with the Lenstra–Lenstra–Lovász lattice basis reduction algorithm, but I still fail.
Update: When asked nicely, Mathematica can tackle the above system. Try It Online!
I leave the question open in hope someone shows me how to mathematically solve the later system in time polynomial to the $\log$ of the parameters.