Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Designs, Codes and Cryptography
Erschienen in: Designs, Codes and Cryptography 5/2023

10.01.2023

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

verfasst von: 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

Erschienen in: Designs, Codes and Cryptography | Ausgabe 5/2023

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel The differential spectrum and boomerang spectrum of a class of locally-APN functions
Nächster Artikel A general family of Plotkin-optimal two-weight codes over
Fußnoten
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.
 
Literatur
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.
Lenstra A.K., Lenstra H.W., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982).MathSciNetCrossRefMATH
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.
Metadaten
Titel
An improved method for predicting truncated multiple recursive generators with unknown parameters
verfasst von
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
Publikationsdatum
10.01.2023
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 5/2023
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-022-01175-4

Weitere Artikel der Ausgabe 5/2023

Designs, Codes and Cryptography 5/2023 Zur Ausgabe

OriginalPaper

Some restrictions on the weight enumerators of near-extremal ternary self-dual codes and quaternary Hermitian self-dual codes

OriginalPaper

Cyclic codes of length 5p with MDS symbol-pair

OriginalPaper

Rank weight hierarchy of some classes of polynomial codes

OriginalPaper

A geometric description of the Figueroa plane

OriginalPaper

Quasi optimal anticodes: structure and invariants

OriginalPaper

New cryptanalysis of LowMC with algebraic techniques

Premium Partner

    Bildnachweise