Analysis of hidden number problem with hidden multiplier

In Crypto 1996, the Hidden Number Problem was introduced by Boneh and Venkatesan. Howgrave-Graham, Nguyen and Shparlinski (Mathematics of Computation 2003) generalized this problem and called it Hidden Number Problem with Hidden Multiplier (HNPHM). It has application in security analysis of timed-release crypto. They proposed a polynomial time algorithm to solve HNPHM. They showed that one can solve it if absolute error is less than m0.20 for some positive integer m. They improved this bound up to m0.25 heuristically. It was also proved that one can not solve HNPHM if error is larger than m0.5. In this paper, we show that one can solve HNPHM in polynomial time heuristically if error is bounded by m0.5.