{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:42:35Z","timestamp":1760110955409,"version":"build-2065373602"},"reference-count":74,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"publisher","award":["311646"],"award-info":[{"award-number":["311646"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Since the introduction of the Kolmogorov complexity of binary sequences in the 1960s, there have been significant advancements on the topic of complexity measures for randomness assessment, which are of fundamental importance in theoretical computer science and of practical interest in cryptography. This survey reviews notable research from the past four decades on the linear, quadratic and maximum-order complexities of pseudo-random sequences, and their relations with Lempel\u2013Ziv complexity, expansion complexity, 2-adic complexity and correlation measures.<\/jats:p>","DOI":"10.3390\/cryptography8020025","type":"journal-article","created":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T10:41:03Z","timestamp":1718275263000},"page":"25","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Survey on Complexity Measures for Pseudo-Random Sequences"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3792-769X","authenticated-orcid":false,"given":"Chunlei","family":"Li","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, 5020 Bergen, Norway"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,13]]},"reference":[{"key":"ref_1","unstructured":"Ristenpart, T., and Yilek, S. (March, January 28). When good randomness goes bad: Virtual machine reset vulnerabilities and hedging deployed cryptography. Proceedings of the Network and Distributed System Security (NDSS) Symposium, San Diego, CA, USA."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ishai, Y., and Rijmen, V. (2019). An analysis of NIST SP 800-90A. Advances in Cryptology\u2014EUROCRYPT 2019, Springer International Publishing.","DOI":"10.1007\/978-3-030-17653-2"},{"key":"ref_3","unstructured":"Bernstein, D.J., Lange, T., and Niederhagen, R. (2015). Dual EC: A standardized back door. Cryptol. ePrint Arch., 767. Available online: https:\/\/eprint.iacr.org\/2015\/767."},{"key":"ref_4","unstructured":"Tang, Q., and Teague, V. (2024). On the possibility of a backdoor in the Micali-Schnorr generator. Public-Key Cryptography\u2014PKC 2024, Springer Nature."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Barker, E., and Kelsey, J. (2015). Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST (National Institute of Standards and Technology). Special Publication.","DOI":"10.6028\/NIST.SP.800-90Ar1"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Gavrilova, M., Gervasi, O., Kumar, V., Tan, C.J.K., Taniar, D., Lagan\u00e1, A., Mun, Y., and Choo, H. (2006). Application of LFSRsfor parallel sequence generation in cryptologic algorithms. Computational Science and Its Applications\u2014ICCSA 2006, Springer.","DOI":"10.1007\/11751540"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kuznetsov, A.A., Potii, O.V., Poluyanenko, N.A., Gorbenko, Y.I., and Kryvinska, N. (2022). Areas of Application for Nonlinear Shift Registers in PRS Generators. Stream Ciphers in Modern Real-Time IT Systems: Analysis, Design and Comparative Studies, Springer International Publishing.","DOI":"10.1007\/978-3-030-79770-6"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/BF01203155","article-title":"Grundlagen der Wahrscheinlichkeitsrechnung","volume":"5","author":"Mises","year":"1919","journal-title":"Math. Z."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1090\/S0002-9904-1940-07154-X","article-title":"On the concept of a random sequence","volume":"46","author":"Church","year":"1940","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_10","unstructured":"Golomb, S.W. (2017). Shift Register Sequences: Secure and Limited-Access Code Generators, Efficiency Code Generators, Prescribed Property Generators, Mathematical Models, World Scientific Publishing Company. [3rd Revised ed.]."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/S0304-3975(98)00075-9","article-title":"On tables of random numbers","volume":"207","author":"Kolmogorov","year":"1998","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","article-title":"The definition of random sequences","volume":"9","year":"1966","journal-title":"Inf. Control"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","article-title":"Process complexity and effective random tests","volume":"7","author":"Schnorr","year":"1973","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_14","unstructured":"Knuth, D.E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley. [3rd ed.]."},{"key":"ref_15","unstructured":"Berlekamp, E.R. (1968). Algebraic Coding Theory, World Scientific Publishing Company."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1109\/TIT.1969.1054260","article-title":"Shift-register synthesis and BCH decoding","volume":"15","author":"Massey","year":"1969","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Pichler, F. (1986). Linear complexity and random sequences. Advances in Cryptology\u2014EUROCRYPT\u201985, Springer.","DOI":"10.1007\/3-540-39805-8"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Niederreiter, H. (1988). The probabilistic theory of linear complexity. Advances in Cryptology\u2014 EUROCRYPT\u201988, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-45961-8_17"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Niederreiter, H. (2003). Linear complexity and related complexity measures for sequences. Progress in Cryptology\u2014INDOCRYPT 2003, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-540-24582-7_1"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bassham, L.E., Rukhin, A.L., Soto, J., Nechvatal, J.R., Smid, M.E., Leigh, S.D., Levenson, M., Vangel, M., Heckert, N.A., and Banks, D.L. (2010). A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, NIST.","DOI":"10.6028\/NIST.SP.800-22r1a"},{"key":"ref_21","unstructured":"Jansen, C.J.A. (1989). Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods. [Ph.D. Thesis, Delft University of Technology]."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s001459900024","article-title":"Feedback shift registers, 2-adic span, and combiners with memory","volume":"10","author":"Klapper","year":"1997","journal-title":"J. Cryptol."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1109\/18.53741","article-title":"On the quadratic spans of DeBruijn sequences","volume":"36","author":"Chan","year":"1990","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1112\/S146115701200109X","article-title":"On the use of expansion series for stream ciphers","volume":"15","author":"Diem","year":"2012","journal-title":"LMS J. Comput. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1006\/jcom.2001.0621","article-title":"Linear complexity, k-error linear complexity, and the discrete Fourier transform","volume":"18","author":"Meidl","year":"2002","journal-title":"J. Complex."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Garcia, A., and Stichtenoth, H. (2006). Pseudorandom Sequences. Topics in Geometry, Coding Theory and Cryptography, Springer.","DOI":"10.1007\/1-4020-5334-4"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1147\/rd.203.0204","article-title":"Analysis of the Berlekamp-Massey linear feedback shift-register synthesis algorithm","volume":"20","author":"Gustavson","year":"1976","journal-title":"IBM J. Res. Dev."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1109\/TIT.1987.1057299","article-title":"On the equivalence between Berlekamp\u2019s and Euclid\u2019s algorithms","volume":"33","author":"Dornstetter","year":"1987","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1109\/18.761282","article-title":"Sequences with almost perfect linear complexity profiles and curves over finite fields","volume":"45","author":"Xing","year":"1999","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0304-3975(99)00067-5","article-title":"An algorithm for shifted continued fraction expansions in parallel linear time","volume":"226","author":"Niederreiter","year":"1999","journal-title":"Theor. Comput. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Niederreiter, H. (1999). Some computable complexity measures for binary sequences. SEquences and Their Applications (SETA), Springer.","DOI":"10.1007\/978-1-4471-0551-0_5"},{"key":"ref_32","unstructured":"Jungnickel, D. (1993). Finite Fields: Structure and Arithmetics, B.I. Wissenschaftsverlag."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Koblitz, N. (1996). Linear complexity of periodic sequences: A general theory. Advances in Cryptology\u2014CRYPTO\u201996, Springer.","DOI":"10.1007\/3-540-68697-5"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Massey, J.L., and Serconek, S. (1994). A Fourier transform approach to the linear complexity of nonlinearly filtered sequences. Advances in Cryptology\u2014CRYPTO\u201994, Springer.","DOI":"10.1007\/3-540-48658-5_31"},{"key":"ref_35","unstructured":"Blahut, R.E. (1983). Theory and Practice of Error Control Codes, Addison-Wesley Publishing Company."},{"key":"ref_36","unstructured":"Selmer, E.S. (1966). Linear Recurrence Relations over Finite Fields, Department of Informatics, University of Bergen."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1276","DOI":"10.1109\/18.669398","article-title":"On the linear complexity of Legendre sequences","volume":"44","author":"Ding","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2807","DOI":"10.1109\/18.959261","article-title":"Lower bounds on the linear complexity of the discrete logarithm in finite fields","volume":"47","author":"Meidl","year":"2001","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_39","unstructured":"Helleseth, T., Kim, S.H., and No, J.S. (July, January 30). Linear complexity over GF(p) and trace representation of Lempel-Cohn-Eastman sequences. Proceedings of the IEEE International Symposium on Information Theory, Lausanne, Switzerland."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Shparlinski, I. (2003). Cryptographic Applications of Analytic Number Theory, Birkh\u00e4user.","DOI":"10.1007\/978-3-0348-8037-4"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Rueppel, R.A. (1986). Analysis and Design of Stream Ciphers, Springer.","DOI":"10.1007\/978-3-642-82865-2"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"2817","DOI":"10.1109\/TIT.2002.804050","article-title":"On the expected value of the linear complexity and the k-error linear complexity of periodic sequences","volume":"48","author":"Meidl","year":"2002","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Chan, A.H., and Games, R.A. (1990). On the quadratic spans of periodic sequences. Advances in Cryptology \u2014 CRYPTO\u201989, Springer. Lecture Notes in Computer Science, Proceedings.","DOI":"10.1007\/0-387-34805-0_9"},{"key":"ref_44","unstructured":"Youssef, A., and Gong, G. (2000, January 28\u201331). On the quadratic span of binary sequences. Proceedings of the 20th Biennial Symposium on Communications, Kingston, ON, Canada."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1840","DOI":"10.1109\/TIT.2005.846428","article-title":"On the quadratic span of binary sequences","volume":"51","author":"Rizomiliotis","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Jansen, C., and Boekee, D. (1990). The shortest feedback shift register that can generate a given sequence. Advances in Cryptology\u2014CRYPTO\u201989, Springer. Lecture Notes in Computer Science, Proceedings.","DOI":"10.1007\/0-387-34805-0_10"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Jansen, C. (1991). The maximum order complexity of sequence ensembles. Advances in Cryptology\u2014EUROCRYPT \u201991, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-46416-6_13"},{"key":"ref_48","first-page":"12","article-title":"Linear size finite automata for the set of all subwords of a word\u2014An outline of results","volume":"21","author":"Blumer","year":"1983","journal-title":"Bull. EATCS"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1109\/TIT.2005.844090","article-title":"Results on the nonlinear span of binary sequences","volume":"51","author":"Rizomiliotis","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"4293","DOI":"10.1109\/TIT.2007.907442","article-title":"On the nonlinear complexity and Lempel\u2013Ziv complexity of finite length sequences","volume":"53","author":"Limniotis","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1023\/A:1008295603824","article-title":"An approximate distribution for the maximum order complexity","volume":"10","author":"Erdmann","year":"1997","journal-title":"Des. Codes Cryptogr."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"7646","DOI":"10.1109\/TIT.2017.2736545","article-title":"Construction of sequences with high nonlinear complexity from function fields","volume":"63","author":"Luo","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"8116","DOI":"10.1109\/TIT.2023.3316252","article-title":"Binary sequences with length n and nonlinear complexity not less than n\/2","volume":"69","author":"Liang","year":"2023","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"4257","DOI":"10.1109\/TIT.2006.880054","article-title":"Constructing periodic binary sequences with maximum nonlinear span","volume":"52","author":"Rizomiliotis","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"6188","DOI":"10.1109\/TIT.2017.2714681","article-title":"Investigations on periodic sequences with maximum nonlinear complexity","volume":"63","author":"Sun","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Yuan, Q., Li, C., Zeng, X., Helleseth, T., and He, D. (2024). Further investigations on nonlinear complexity of periodic binary sequences. IEEE Trans. Inf. Theory, 1.","DOI":"10.1109\/TIT.2024.3394538"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","article-title":"On the complexity of finite sequences","volume":"22","author":"Lempel","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/s12095-016-0189-2","article-title":"Expansion complexity and linear complexity of sequences over finite fields","volume":"9","author":"Merai","year":"2017","journal-title":"Cryptogr. Commun."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"I\u015f\u0131k, L., and Winterhof, A. (2017). Maximum-order complexity and correlation measures. Cryptography, 1.","DOI":"10.3390\/cryptography1010007"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"101977","DOI":"10.1016\/j.ffa.2021.101977","article-title":"Correlation measure, linear complexity and maximum order complexity for families of binary sequences","volume":"78","author":"Chen","year":"2022","journal-title":"Finite Fields Their Appl."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1109\/TIT.2002.807308","article-title":"Periodic sequences with large k-error linear complexity","volume":"49","author":"Niederreiter","year":"2003","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0097-3165(82)90038-3","article-title":"On the complexities of DeBruijn sequences","volume":"33","author":"Chan","year":"1982","journal-title":"J. Comb. Theory A"},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1016\/0097-3165(83)90060-2","article-title":"There are no DeBruijn sequences of span n with complexity 2n-1+n+1","volume":"34","author":"Games","year":"1983","journal-title":"J. Comb. Theory A"},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"1166","DOI":"10.1109\/18.57220","article-title":"Linear spans of modified DeBruijn sequences","volume":"36","author":"Mayhew","year":"1990","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"1549","DOI":"10.1016\/j.dam.2006.11.019","article-title":"Minimal polynomials of the modified DeBruijn sequences","volume":"156","author":"Kyureghyan","year":"2008","journal-title":"Discret. Appl. Math."},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"101583","DOI":"10.1016\/j.ffa.2019.101583","article-title":"New results on the minimal polynomials of modified DeBruijn sequences","volume":"60","author":"Dong","year":"2019","journal-title":"Finite Fields Their Appl."},{"key":"ref_67","doi-asserted-by":"crossref","first-page":"101735","DOI":"10.1016\/j.ffa.2020.101735","article-title":"The minimal polynomials of modified DeBruijn sequences revisited","volume":"68","author":"Wang","year":"2020","journal-title":"Finite Fields Their Appl."},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01389353","article-title":"The lower bound of the quadratic spans of DeBruijn sequences","volume":"3","author":"Khachatrian","year":"1993","journal-title":"Des. Codes Cryptogr."},{"key":"ref_69","doi-asserted-by":"crossref","unstructured":"Klapper, A., and Goresky, M. (1995). Cryptanalysis based on 2-adic rational approximation. Advances in Cryptology\u2014CRYPTO\u201995, Springer.","DOI":"10.1007\/3-540-44750-4_21"},{"key":"ref_70","doi-asserted-by":"crossref","unstructured":"Chen, Z., Chen, Z., Obrovsky, J., and Winterhof, A. (2023). Maximum-order complexity and 2-adic complexity. arXiv.","DOI":"10.1109\/TIT.2024.3405946"},{"key":"ref_71","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_73","doi-asserted-by":"crossref","first-page":"7550","DOI":"10.1109\/TIT.2021.3112824","article-title":"The expansion complexity of ultimately periodic sequences over finite fields","volume":"67","author":"Sun","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_74","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10998-006-0008-1","article-title":"Linear complexity profile of binary sequences with small correlation measure","volume":"52","author":"Winterhof","year":"2006","journal-title":"Period. Math. Hung."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/8\/2\/25\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:58:16Z","timestamp":1760108296000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/8\/2\/25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,13]]},"references-count":74,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["cryptography8020025"],"URL":"https:\/\/doi.org\/10.3390\/cryptography8020025","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2024,6,13]]}}}