Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 5/2023

10-01-2023

An improved method for predicting truncated multiple recursive generators with unknown parameters

Authors: Han-Bing Yu, Qun-Xiong Zheng, Yi-Jian Liu, Jing-Guo Bi, Yu-Fei Duan, Jing-Wen Xue, You Wu, Yue Cao, Rong Cheng, Lin Wang, Bai-Shun Sun

Published in: Designs, Codes and Cryptography | Issue 5/2023

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Multiple recursive generators are an important class of pseudorandom number generators which are widely used in cryptography. Methods to predict the whole sequences by the truncated high-order bits of the sequences are not only a crucial aspect of evaluating the security of pseudorandom number generators but also important concerns in the design of pseudorandom number generators. This paper improves the work of Sun et al. (Des Codes Cryptogr 88:1083–1102, 2020) on the predictability of truncated multiple recursive generators with unknown parameters. Given a few truncated digits of high-order bits output by a multiple recursive generator, we first apply the resultant to recover the modulus, then use the Chinese Remainder Theorem and the idea of recovering p-adic coordinates of the coefficients layer by layer to recover the coefficients, and finally employ Kannan’s embedding technique to recover the initial state. Experimental results show that our new method is superior to that of Sun et al. (2020), no matter in terms of the running time or the number of truncated digits required.
previous article The differential spectrum and boomerang spectrum of a class of locally-APN functions
next article A general family of Plotkin-optimal two-weight codes over
Footnotes
1
In the sixth (2021) National Crypto-Math Challenge, Jing-Hui Wang, Ming-Hao Xu and Xiao-Yue Hu (mentor: Zheng-Fu Lu) from Yunnan University also independently pointed that the modulus m can be recovered by computing the resultants of polynomials in \(I_{m}(\underline{a})\).
 
2
In the sixth (2021) National Crypto-Math Challenge, Jia-Le Fang (mentor: Hua Zhong) from Hangzhou Dianzi University also independently proposed the strategy of balancing each coordinate of the target vector.
 
Literature
1.
Ajtai M., Kumar R., Sivakumar D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 601–610. Association for Computing Machinery, New York, NY, USA (2001).
2.
Ajtai M.: Generating random lattices according to the invariant distribution (2006). Draft of March.
3.
Albrecht M.R., Heninger N.: On bounded distance decoding with predicate: Breaking the “lattice barrier" for the hidden number problem. In: Canteaut A., Standaert F. (eds.) Advances in Cryptology - EUROCRYPT 2021, pp. 528–558. Springer, Berlin, Heidelberg (2021).CrossRef
4.
Albrecht M.R., Ducas L., Herold G., Kirshanova E., Postlethwaite E.W., Stevens M.: The general sieve kernel and new records in lattice reduction. In: Ishai Y., Rijmen V. (eds.) Advances in Cryptology - EUROCRYPT 2019, pp. 717–746. Springer, Cham (2019).CrossRefMATH
5.
Berlekamp E.R.: Algebraic Coding Theory. McGraw-Hill, New York (1968).MATH
6.
Boyar J.: Inferring sequences produced by a linear congruential generator missing low-order bits. J. Cryptol. 1(3), 177–184 (1989).MathSciNetCrossRefMATH
7.
8.
Chen H.J., Qi W.F.: On the distinctness of maximal length sequences over \(\mathbb{Z} /(pq)\) modulo 2. Finite Fields Appl. 15(2), 23–39 (2009).MathSciNetCrossRefMATH
9.
Contini S., Shparlinski I.E.: On stern’s attack against secret truncated linear congruential generators. In: Information Security and Privacy, pp. 52–60. Springer, Berlin (2005).
10.
Coppersmith D.: Finding a small root of a univariate modular equation. In: Advances in Cryptology – EUROCRYPT’96, pp. 155–165. Springer, Berlin (1996).
11.
12.
13.
Deng L.: Efficient and portable multiple recursive generators of large order. ACM Trans. Model. Comput. Simul. 15(1), 1–13 (2005).CrossRefMATH
14.
Deng L., Xu H.Q.: A system of high-dimensional, efficient, long-cycle and portable uniform random number generators. ACM Trans. Model. Comput. Simul. 13(4), 299–309 (2003).CrossRefMATH
15.
Deng L., Shiau J.H., Lu H.H., Bowman D.: Secure and fast encryption (safe) with classical random number generators. ACM Trans. Math. Softw. 44(4), 1–17 (2018).MathSciNetCrossRefMATH
16.
17.
ETSI/SAGE: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 2: ZUC Specification (2011).
18.
Frieze A.M., Hastad J., Kannan R., Lagarias J.C., Shamir A.: Reconstructing truncated integer variables satisfying linear congruences. SIAM J. Comput. 17(2), 262–280 (1988).MathSciNetCrossRefMATH
19.
Gama N., Nguyen P.Q.: Predicting lattice reduction. In: Smart N. (ed.) Advances in Cryptology - EUROCRYPT 2008, pp. 31–51. Springer, Berlin (2008).CrossRef
20.
Gomez D., Gutierrez J., Ibeas Á., Sevilla D.: Common factors of resultants modulo \(p\). Bull. Aust. Math. Soc. 79(2), 299–302 (2009).MathSciNetCrossRefMATH
21.
Hallgren S.: Linear congruential generators over elliptic curves. In: Preprint CS94 -143, Department of Computer Science, Cornegie Mellon University, pp. 1–10 (1994).
22.
Hess F., Shparlinski I.E.: On the linear complexity and multidimensional distribution of congruential generators over elliptic curves. Des. Codes Cryptogr. 35(1), 111–117 (2005).MathSciNetCrossRefMATH
23.
Huang M.Q.: Analysis and cryptologic evaluation of primitive sequences over an integer residue ring. Doctoral Dissertation of Graduate School of USTC, Academia Sinica (1988).
24.
Josh A., Virginia V.W.: A refined laser method and faster matrix multiplication. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 522–539. Society for Industrial and Applied Mathematics, USA (2021).
25.
26.
Kannan R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 193–206. Association for Computing Machinery, New York, NY, USA (1983).
27.
28.
Knuth D.E.: Seminumerical algorithms. In: The Art of Computer Programming, vol. 2. Addison-Wesley, Canada (1981).
29.
30.
Kuzmin A.S., Nechaev A.A.: Linear recurring sequences over galois ring. Russ. Math. Surv. 48, 171–172 (1993).CrossRef
31.
Kuzmin A.S., Nechaev A.A.: Reconstruction of a linear recurrence of maximal period over a galois ring from its highest coordinate sequence. Discret. Math. Appl. 21(2), 145–178 (2011).MathSciNetCrossRefMATH
32.
Kuzmin A.S., Marchalko G.B., Nechaev A.A.: Reconstruction of a linear recurrence over a primary residue ring. Mem. Discret. Math. 12, 155–194 (2009).
33.
L’Ecuyer P., Touzin R.: Fast combined multiple recursive generators with multipliers of the form \(a=\pm 2^q\pm 2^r\). In: Proceedings of the 32nd Conference on Winter Simulation, pp. 683–689. Society for Computer Simulation International, San Diego, CA, USA (2000).
34.
L’Ecuyer P.: Good parameters and implementations for combined multiple recursive random number generators. Oper. Res. 47(1), 159–164 (1999).CrossRefMATH
35.
Lehmer D.H.: Mathematical methods in large-scale computing units. Ann. Comput. Lab. Harvard Univ. 26, 141–146 (1951).MathSciNetMATH
36.
37.
38.
39.
40.
Nguyen P.Q.: Hermite’s constant and lattice algorithms. In: Nguyen P.Q., Vallée B. (eds.) The LLL Algorithm, pp. 19–69. Springer, Berlin, Heidelberg (2010).CrossRef
41.
Nguyen P.Q., Stehlé D.: LLL on the average. In: Hess F., Pauli S., Pohst M. (eds.) Algorithmic Number Theory, pp. 238–256. Springer, Berlin, Heidelberg (2006).CrossRef
42.
Plumstead J.B.: Inferring a sequence generated by a linear congruence. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pp. 153–159. IEEE, Chicago, IL, USA (1982).
43.
44.
Schnorr C.P., Euchner M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(2), 181–199 (1994).MathSciNetCrossRefMATH
45.
46.
Stern J.: Secret linear congruential generators are not cryptographically secure. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pp. 421–426. IEEE, Los Angeles (1987).
47.
Sugiyama Y., Kasahara M., Hirasawa S., Namekawa T.: A method for solving key equation for decoding goppa codes. Inf. Control 27(1), 87–99 (1975).MathSciNetCrossRefMATH
48.
Sun H.Y., Zhu X.Y., Zheng Q.X.: Predicting truncated multiple recursive generators with unknown parameters. Des. Codes Cryptogr. 88, 1083–1102 (2020).MathSciNetCrossRefMATH
49.
Von zur Gathen J., Gerhard J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013).
50.
51.
William C.B.: Matrices over Commutative Rings. Marcel Dekker, New York (1993).MATH
52.
Yang J.B.: Reconstructing Truncated Sequences Derived from Primitive Sequences over Inter Residue Rings. PLA Information Engineering University, Zhengzhou (2017).
53.
Zhou J.J., Qi W.F.: On some properties of linear recurring sequences over \(\mathbb{Z} /(m)\). Chin. Q. J. Math. 5(1–2), 166–171 (1990).
54.
Zhu X.Y.: Some Results on Injective Mappings of Primitive Sequences Modulo Prime Powers. PLA Information Engineering University, Zhengzhou (2004).
55.
Metadata
Title
An improved method for predicting truncated multiple recursive generators with unknown parameters
Authors
Han-Bing Yu
Qun-Xiong Zheng
Yi-Jian Liu
Jing-Guo Bi
Yu-Fei Duan
Jing-Wen Xue
You Wu
Yue Cao
Rong Cheng
Lin Wang
Bai-Shun Sun
Publication date
10-01-2023
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 5/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-022-01175-4

Other articles of this Issue 5/2023

Designs, Codes and Cryptography 5/2023 Go to the issue

OriginalPaper

On some batch code properties of the simplex code

OriginalPaper

The decomposition of an NFSR into the cascade connection of two smaller NFSRs revisited

OriginalPaper

A geometric description of the Figueroa plane

OriginalPaper

Minimum distance and parameter ranges of locally recoverable codes with availability from fiber products of curves

OriginalPaper

Grassl–Rötteler cyclic and consta-cyclic MDS codes are generalised Reed–Solomon codes

OriginalPaper

Symplectic 4-dimensional semifields of order and

Premium Partner

    Image Credits