Article Contents
Article Contents

# 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 $m^{0.20}$ for some positive integer $m$ . They improved this bound up to $m^{0.25}$ heuristically. It was also proved that one can not solve HNPHM if error is larger than $m^{0.5}$ . In this paper, we show that one can solve HNPHM in polynomial time heuristically if error is bounded by $m^{0.5}$ .

Mathematics Subject Classification: Primary: 11Y16; Secondary: 94A60.

 Citation:

• Figure 1.  Upper bound of $\Delta$ for increasing values of $n$ and $m \to \infty$

Table 1.  Experimental results for different values of $m$

 $n$ $\bigg(\frac{\binom{n}{2}}{2\binom{n}{2}+2n}\bigg)\log_2 m$ $\log_2 \! m$ Experimental result LLL Algorithm time in Seconds 298 768 295 16.78 8 398 1024 395 24.39 796 2048 793 48.49 314 768 310 77.76 10 418 1024 415 108.96 837 2048 834 244.68 324 768 321 302.93 12 433 1024 429 406.54 866 2048 863 930.16 332 768 328 832.71 14 443 1024 439 1342.42 887 2048 883 2798.76 338 768 333 2283.69 16 451 1024 446 3138.10 903 2048 899 8095.19
•  [1] A. Akavia, Solving hidden number problem with one bit oracle and advice, Advances in Cryptology-CRYPTO 2009, 5677 (2009), 337-354. [2] D. Boneh and R. Venkatesan, Hardness of computing the most significant bits of secret keys in diffie-hellman and related schemes, In Crypto 1996, LNCS, 1109 (1996), 129-142.  doi: 10.1007/3-540-68697-5_11. [3] D. Boneh and R. Venkatesan, Rounding in lattices and its cryptographic applications, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), ACM, New York, (1997), 675–681. [4] N. Howgrave-Graham and N. P. Smart, Lattice attacks on digital signature schemes, Des. Codes Cryptography, 23 (2001), 283-290.  doi: 10.1023/A:1011214926272. [5] N. Howgrave-Graham, P. Q. Nguyen and I. Shparlinski, Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation, Math. Comput., 72 (2003), 1473-1485.  doi: 10.1090/S0025-5718-03-01495-9. [6] R. Kannan, Minkowski's convex body theorem and integer programming, Mathematics of Operation Research, 12 (1987), 415-440.  doi: 10.1287/moor.12.3.415. [7] T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A. Osvik, H. J. J. te Riele, A. Timofeev and P. Zimmermann, Factorization of a 768-bit RSA modulus, In Crypto 2010, LNCS, 6223 (2010), 333–350. [8] A. K. Lenstra, H. W. Lenstra Jr and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515-534.  doi: 10.1007/BF01457454. [9] A. May and M. Ritzenhofen, Implicit factoring: On polynomial time factoring given only an implicit hint, PKC 2009, LNCS, 5443 (2009), 1-14. [10] O. Regev, Lattices in computer science (lecture notes), New York University, Available at http://www.cims.nyu.edu/regev/teaching/lattices_fall_2004/index.html. [11] R. L. Rivest, A. Shamir and D. A. Wagner, Time lock puzzles and timed release cryptography, Technical report, MIT/LCS/TR-684. [12] I. E. Shparlinski, Playing hide-and-seek with numbers: The hidden number problem, lattices and exponential sums, Proc. Symp. in Appl. Math., Amer. Math. Soc., 62 (2005), 153-177. [13] J. Stren, Secret linear congruential generators are not cryptographically secure, FOCS 1987, (1987), 421-426.

Figures(1)

Tables(1)