# American Institute of Mathematical Sciences

November  2017, 11(4): 805-811. doi: 10.3934/amc.2017059

## Analysis of Hidden Number Problem with Hidden Multiplier

Received  September 2016 Published  November 2017

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}$.

Citation: Santanu Sarkar. Analysis of Hidden Number Problem with Hidden Multiplier. Advances in Mathematics of Communications, 2017, 11 (4) : 805-811. doi: 10.3934/amc.2017059
##### References:

show all references

##### References:
Upper bound of $\Delta$ for increasing values of $n$ and $m \to \infty$
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
 $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] Igor E. Shparlinski. Close values of shifted modular inversions and the decisional modular inversion hidden number problem. Advances in Mathematics of Communications, 2015, 9 (2) : 169-176. doi: 10.3934/amc.2015.9.169 [2] Mustapha Ait Rami, John Moore. Partial stabilizability and hidden convexity of indefinite LQ problem. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 221-239. doi: 10.3934/naco.2016009 [3] Jinsong Xu. Reversible hidden data access algorithm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1219-1232. doi: 10.3934/dcdss.2019084 [4] F. D. Araruna, F. O. Matias, M. P. Matos, S. M. S. Souza. Hidden regularity for the Kirchhoff equation. Communications on Pure & Applied Analysis, 2008, 7 (5) : 1049-1056. doi: 10.3934/cpaa.2008.7.1049 [5] Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149 [6] Miguel Atencia, Esther García-Garaluz, Gonzalo Joya. The ratio of hidden HIV infection in Cuba. Mathematical Biosciences & Engineering, 2013, 10 (4) : 959-977. doi: 10.3934/mbe.2013.10.959 [7] Juan Luis Vázquez, Nikolaos B. Zographopoulos. Hardy type inequalities and hidden energies. Discrete & Continuous Dynamical Systems - A, 2013, 33 (11&12) : 5457-5491. doi: 10.3934/dcds.2013.33.5457 [8] Xu Zhang, Guanrong Chen. Polynomial maps with hidden complex dynamics. Discrete & Continuous Dynamical Systems - B, 2019, 24 (6) : 2941-2954. doi: 10.3934/dcdsb.2018293 [9] Qichun Wang, Chik How Tan, Pantelimon Stănică. Concatenations of the hidden weighted bit function and their cryptographic properties. Advances in Mathematics of Communications, 2014, 8 (2) : 153-165. doi: 10.3934/amc.2014.8.153 [10] Mikhail Langovoy, Akhilesh Gotmare, Martin Jaggi. Unsupervised robust nonparametric learning of hidden community properties. Mathematical Foundations of Computing, 2019, 2 (2) : 127-147. doi: 10.3934/mfc.2019010 [11] Dong-Mei Zhu, Wai-Ki Ching, Robert J. Elliott, Tak-Kuen Siu, Lianmin Zhang. Hidden Markov models with threshold effects and their applications to oil price forecasting. Journal of Industrial & Management Optimization, 2017, 13 (2) : 757-773. doi: 10.3934/jimo.2016045 [12] Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1 [13] Sujay Jayakar, Robert S. Strichartz. Average number of lattice points in a disk. Communications on Pure & Applied Analysis, 2016, 15 (1) : 1-8. doi: 10.3934/cpaa.2016.15.1 [14] Mostafa Abouei Ardakan, A. Kourank Beheshti, S. Hamid Mirmohammadi, Hamed Davari Ardakani. A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 465-480. doi: 10.3934/naco.2017029 [15] Cai-Tong Yue, Jing Liang, Bo-Fei Lang, Bo-Yang Qu. Two-hidden-layer extreme learning machine based wrist vein recognition system. Big Data & Information Analytics, 2017, 2 (1) : 59-68. doi: 10.3934/bdia.2017008 [16] Yang Shen, Tak Kuen Siu. Consumption-portfolio optimization and filtering in a hidden Markov-modulated asset price model. Journal of Industrial & Management Optimization, 2017, 13 (1) : 23-46. doi: 10.3934/jimo.2016002 [17] Eleftherios Gkioulekas, Ka Kit Tung. Is the subdominant part of the energy spectrum due to downscale energy cascade hidden in quasi-geostrophic turbulence?. Discrete & Continuous Dynamical Systems - B, 2007, 7 (2) : 293-314. doi: 10.3934/dcdsb.2007.7.293 [18] Jiaqin Wei, Zhuo Jin, Hailiang Yang. Optimal dividend policy with liability constraint under a hidden Markov regime-switching model. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1965-1993. doi: 10.3934/jimo.2018132 [19] Jianghong Bao, Dandan Chen, Yongjian Liu, Hongbo Deng. Coexisting hidden attractors in a 5D segmented disc dynamo with three types of equilibria. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6053-6069. doi: 10.3934/dcdsb.2019130 [20] Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667

2018 Impact Factor: 0.879