Analysis of Hidden Number Problem with Hidden Multiplier

Previous 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}$
AMC Home
This Issue
Next Article
Capacity of random channels with large alphabets

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

Analysis of Hidden Number Problem with Hidden Multiplier

Santanu Sarkar

Indian Institute of Technology Madras, Sardar Patel Road, Chennai 600036, India

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

Keywords: Hidden Number Problem with Hidden Multiplier, lattice, LLL algorithm, sequence.

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

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:

[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.

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.
[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.

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

Figure Options

Download full-size image

Download as PowerPoint slide

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

Table Options

Download as excel

$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, 0 (0) : 0-0. 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, 2017, 13 (5) : 1-10. doi: 10.3934/jimo.2018132
[19]	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
[20]	G.F. Webb. The prime number periodical cicada problem. Discrete & Continuous Dynamical Systems - B, 2001, 1 (3) : 387-399. doi: 10.3934/dcdsb.2001.1.387

2018 Impact Factor: 0.879

Tools

Metrics

Tools

Article outline

Figures and Tables

2018 Impact Factor: 0.879

Tools

Figures and Tables

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences