
-
Previous Article
Capacity of random channels with large alphabets
- AMC Home
- This Issue
-
Next Article
Quadratic residue codes over $\mathbb{F}_{p^r}+{u_1}\mathbb{F}_{p^r}+{u_2}\mathbb{F}_{p^r}+...+{u_t}\mathbb{F}_ {p^r}$
Analysis of Hidden Number Problem with Hidden Multiplier
Indian Institute of Technology Madras, Sardar Patel Road, Chennai 600036, India |
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}$.
References:
[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. Google Scholar |
[11] |
R. L. Rivest, A. Shamir and D. A. Wagner, Time lock puzzles and timed release cryptography, Technical report, MIT/LCS/TR-684. Google Scholar |
[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. Google Scholar |
show all references
References:
[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. Google Scholar |
[11] |
R. L. Rivest, A. Shamir and D. A. Wagner, Time lock puzzles and timed release cryptography, Technical report, MIT/LCS/TR-684. Google Scholar |
[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. Google Scholar |
|
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 |
|
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] |
Karthikeyan Rajagopal, Serdar Cicek, Akif Akgul, Sajad Jafari, Anitha Karthikeyan. Chaotic cuttlesh: king of camouage with self-excited and hidden flows, its fractional-order form and communication designs with fractional form. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2019205 |
2018 Impact Factor: 0.879
Tools
Metrics
Other articles
by authors
[Back to Top]