A Lattice-Based Method for Recovering the Unknown Parameters of Truncated Multiple Recursive Generators with Constant

YU Hanbing; ZHENG Qunxiong

doi:10.23919/cje.2022.00.387

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > Uncorrected proof

Hanbing YU and Qunxiong ZHENG, “A Lattice-Based Method for Recovering the Unknown Parameters of Truncated Multiple Recursive Generators with Constant,” Chinese Journal of Electronics, vol. 33, no. 3, pp. 1–10, 2024 doi: 10.23919/cje.2022.00.387

Citation:

Hanbing YU and Qunxiong ZHENG, “A Lattice-Based Method for Recovering the Unknown Parameters of Truncated Multiple Recursive Generators with Constant,” Chinese Journal of Electronics, vol. 33, no. 3, pp. 1–10, 2024 doi: 10.23919/cje.2022.00.387

Citation:

PDF( 2935 KB)

A Lattice-Based Method for Recovering the Unknown Parameters of Truncated Multiple Recursive Generators with Constant

doi: 10.23919/cje.2022.00.387

YU Hanbing,
ZHENG Qunxiong^,

1.
PLA Strategic Support Force Information Engineering University, Zhengzhou 450001, China

More Information

Author Bio:
Hanbing YU was born in Henan Province, China, in 1998. She received the B.E. degree in cryptography from Information Engineering University, Zhengzhou, China, in 2020 and is currently pursuing the M.S. degree in cryptography. Her research field is cryptography. (Email: hbing_yu@163.com)

Qunxiong ZHENG was born in Fujian Province, China, in 1984. He received the M.S. and Ph.D. degrees in applied mathematics from Information Engineering University, Zhengzhou, China, in 2009 and 2013, respectively. His research field is cryptography. (Email: qunxiong_zheng@163.com)
Corresponding author: Email: qunxiong_zheng@163.com
Received Date: 2022-11-13
Accepted Date: 2023-02-14

Available Online: 2023-07-12

Abstract

Abstract

Multiple recursive generators with constant, the high-order extension of linear congruence generators, are an important class of pseudorandom number generators that are widely used in cryptography. The predictability of truncated sequences output by multiple recursive generators with constant that predicting the whole sequences by the truncated high-order bits of the sequences is a cryptographically crucial problem. This paper studies the predictability of truncated multiple recursive generators with constant. Given a few truncated digits of high-order bits output by a multiple recursive generator with constant, we first convert the multiple recursive generator with constant to multiple recursive generator and then adopt the method we proposed recently to recover the modulus, the coefficients, and the differences of initial state. In particular, we give an estimation of the number of truncated digits required for recovering the differences of initial state by using the expected norm of target vector. We prove by exponential sums that the number of truncated digits required for uniquely determining both the initial state and the constant is finite and give an upper bound. Extensive experiments confirm the correctness of our method.
- Multiple recursive generator with constant,
- Lattice reduction,
- Truncated prediction,
- Exponential sums

FullText(HTML)

References(37)

References

[1]	D. H. Lehmer, “Mathematical methods in large-scale computing units,” in Proceedings of A Second Symposium on Large-Scale Digital Calculating Machinery, Harvard University Press, Cambridge, United Kingdom, pp.141–146, 1951.
[2]	R. R. Coveyou and R. D. Macpherson, “Fourier analysis of uniform random number generators,” Journal of ACM, vol. 14, no. 1, pp. 100–119, 1967. doi: 10.1145/321371.321379
[3]	S. Hallgren, “Linear congruential generators over elliptic curves,” Carnegie Mellon University, Technical Report, CS-94-143, pp.1–10, 1994.
[4]	L. Mérai, “Predicting the elliptic curve congruential generator,” Applicable Algebra in Engineering, Communication and Computing, vol. 28, no. 3, pp. 193–203, 2017. doi: 10.1007/s00200-016-0303-x
[5]	T. Mefenza and D. Vergnaud, “Inferring sequences produced by elliptic curve generators using coppersmith’s methods,” Theoretical Computer Science, vol. 830-831, pp. 20–42, 2020. doi: 10.1016/j.tcs.2020.04.025
[6]	J. Gutierrez, “Attacking the linear congruential generator on elliptic curves via lattice techniques,” Cryptography and Communications, vol. 14, no. 3, pp. 505–525, 2022. doi: 10.1007/s12095-021-00535-6
[7]	P. L’Ecuyer and R. Touzin, “Fast combined multiple recursive generators with multipliers of the form a=±2^q±2^r,” in 2000 Winter Simulation Conference Proceedings (Cat. No. 00CH37165), Orlando, FL, USA, pp.683–689, 2000.
[8]	L. Y. Deng and H. Q. Xu, “A system of high-dimensional, efficient, long-cycle and portable uniform random number generators,” ACM Transactions on Modeling and Computer Simulation, vol. 13, no. 4, pp. 299–309, 2003. doi: 10.1145/945511.945513
[9]	L. Y. Deng, “Efficient and portable multiple recursive generators of large order,” ACM Transactions on Modeling and Computer Simulation, vol. 15, no. 1, pp. 1–13, 2005. doi: 10.1145/1044322.1044323
[10]	L. Y. Deng, J. J. H. Shiau, H. H. S. Lu, et al., “Secure and fast encryption (SAFE) with classical random number generators,” ACM Transactions on Mathematical Software, vol. 44, no. 4, article no. 45, 2018. doi: 10.1145/3212673
[11]	J. B. Plumstead, “Inferring a sequence generated by a linear congruence,” in 23rd Annual Symposium on Foundations of Computer Science, Chicago, IL, USA, pp.153–159, 1982.
[12]	A. M. Frieze, J. Hastad, R. Kannan, et al., “Reconstructing truncated integer variables satisfying linear congruences,” SIAM Journal of Computing, vol. 17, no. 2, pp. 262–280, 1988. doi: 10.1137/0217016
[13]	J. L. Massey, “Shift-register synthesis and BCH decoding,” IEEE Transactions on Information Theory, vol. 15, no. 1, pp. 122–127, 1969. doi: 10.1109/TIT.1969.1054260
[14]	E. R. Berlekamp, Algebraic Coding Theory. McGraw-Hill, New York, NY, USA, pp. 178−188, 1968.
[15]	J. A. Reeds and N. J. A. Sloane, “Shift register synthesis (modulo m),” SIAM Journal on Computing, vol. 14, no. 3, pp. 505–513, 1985. doi: 10.1137/0214038
[16]	M. Q. Huang, “Analysis and cryptologic evaluation of primitive sequences over an integer residue ring,” Ph. D. Thesis, Graduate School of USTC, Academia Sinica, Beijing, China, pp. 20–23, 1988. (in Chinese)
[17]	A. S. Kuzmin and A. A. Nechaev, “Linear recurring sequences over Galois rings,” Algebra and Logic, vol. 34, no. 2, pp. 87–100, 1995. doi: 10.1007/BF00750162
[18]	J. B. Yang, “Reconstructing truncated sequences derived from primitive sequences over inter residue rings,” Master Thesis, PLA Information Engineering University, Zhengzhou, pp. 9−13, 2017. (in Chinese)
[19]	D. Coppersmith, “Finding a small root of a univariate modular equation,” in International Conference on the Theory and Application of Cryptographic Techniques, Advances in Cryptology-EUROCRYPT’96, U. Maurer, Ed. Springer, Saragossa, Spain, vol. 1070, pp.155–165, 1996.
[20]	H. Y. Sun, X. Y. Zhu, and Q. X. Zheng, “Predicting truncated multiple recursive generators with unknown parameters,” Designs, Codes and Cryptography, vol. 88, no. 6, pp. 1083–1102, 2020. doi: 10.1007/s10623-020-00729-8
[21]	H. B. Yu, Q. X. Zheng, Y. J. Liu, et al., “An improved method for predicting truncated multiple recursive generators with unknown parameters,” Designs, Codes and Cryptography, vol. 91, no. 5, pp. 1713–1736, 2023. doi: 10.1007/s10623-022-01175-4
[22]	R. Kannan, “Minkowski’s convex body theorem and integer programming,” Mathematics of Operations Research, vol. 12, no. 3, pp. 415–440, 1987. doi: 10.1287/moor.12.3.415
[23]	H. Y. Sun, X. Y. Zhu, and Q. X. Zheng, “Reconstructing truncated sequences derived from second-order linear congruential generator with unknown coefficients,” Journal of Cryptologic Research, vol. 6, no. 4, pp. 496–511, 2019. (in Chinese) doi: 10.13868/j.cnki.jcr.000318
[24]	M. Ward, “The arithmetical theory of linear recurring series,” Transactions of the American Mathematical Society, vol. 35, no. 3, pp. 600–628, 1933. doi: 10.1090/S0002-9947-1933-1501705-4
[25]	H. J. Chen and W. F. Qi, “On the distinctness of maximal length sequences over Z/(pq) modulo 2,” Finite Fields and Their Applications, vol. 15, no. 1, pp. 23–39, 2009. doi: 10.1016/j.ffa.2008.07.005
[26]	P. Q. Nguyen, “Hermite’s constant and lattice algorithms,” in The LLL Algorithm-Survey and Applications, P. Q. Nguyen and B. Vallée, Eds. Springer, Berlin, Heidelberg, pp.19–69, 2010.
[27]	M. Ajtai, “Generating random lattices according to the invariant distribution,” Draft of March, 2006.
[28]	N. Gama and P. Q. Nguyen, “Predicting lattice reduction,” in 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology-EUROCRYPT 2008, N. Smart, Ed. Springer, Istanbul, Turkey, vol.4965, pp.31–51, 2008.
[29]	P. Q. Nguyen and D. Stehlé, “LLL on the average,” in 7th International Symposium on Algorithmic Number Theory, ANTS-VII, F. Hess, S. Pauli, and M. Pohst, Eds. Springer, Berlin, Germany, vol.4076, pp.238–256, 2006.
[30]	A. K. Lenstra, H. W. Jr. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” Mathematische Annalen, vol. 261, no. 4, pp. 515–534, 1982. doi: 10.1007/BF01457454
[31]	C. P. Schnorr and M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems,” Mathematical Programming, vol. 66, no. 1, pp. 181–199, 1994. doi: 10.1007/BF01581144
[32]	R. Kannan, “Improved algorithms for integer programming and related lattice problems,” in Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, MA, USA, pp.193–206, 1983.
[33]	M. Ajtai, R. Kumar, and D. Sivakumar, “A sieve algorithm for the shortest lattice vector problem,” in Proceedings on 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Crete, Greece, pp.601–610, 2001.
[34]	N. M. Korobov, Exponential Sums and Their Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands, pp. 56–58, 1992.
[35]	Q. X. Zheng, D. D. Lin, and W. F. Qi, “Distribution properties of binary sequences derived from primitive sequences modulo square-free odd integers,” in 14th International Conference on Information Security and Cryptology, Inscrypt 2018, F. C. Guo, X. Y. Huang, and M. Yung, Eds. Springer, Fuzhou, China, vol.11449, pp.568–585, 2018.
[36]	M. R. Albrecht and N. Heninger, “On bounded distance decoding with predicate: Breaking the “lattice barrier” for the hidden number problem,” in 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology-EUROCRYPT 2021, A. Canteaut and F. X. Standaert, Eds. Springer, Zagreb, Croatia, vol.12696, pp.528–558, 2021.
[37]	The FPLLL Development Team, “FPLLL: A lattice reduction library,” Available at: https://github.com/fplll/fpylll, 2016, August 3.