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. 6, pp. 1–10, 2024 doi: 10.23919/cje.2022.00.387 |
[1] |
D. H. Lehmer, “Mathematical methods in large-scale computing units,” in Proceedings of A Second Symposium on Large-Scale Digital Calculating Machinery, 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=±2q±2r,” 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.
|