{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T14:23:11Z","timestamp":1784211791885,"version":"3.55.0"},"reference-count":52,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T00:00:00Z","timestamp":1728432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,12,3]]},"abstract":"<jats:p>  We introduce a novel composition method that combines linear feedback registers into larger nonlinear structures and generalizes earlier methods such as cascade connections. We prove a Chaining Period Theorem which provides the cycle structure of these register constructions. We then use this Chaining Period Theorem and a new construction we call a Product Register (PR) to introduce a flexible and scalable register family with desirable properties, which we term Composite Mersenne Product Registers (CMPRs). We provide an algorithm to estimate the linear complexity of a chosen CMPR and investigate the statistical properties and security of a CMPR-based pseudorandom generator. Finally, we propose a family of CMPR-based stream ciphers and provide comparisons with the TRIVIUM stream cipher in terms of hardware area and security. <\/jats:p>","DOI":"10.62056\/a3tx11zn4","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:00:52Z","timestamp":1736787652000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":3,"title":["Scalable Nonlinear Sequence Generation using Composite Mersenne Product Registers"],"prefix":"10.62056","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-2075-1965","authenticated-orcid":false,"given":"David","family":"Gordon","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9565-4757","authenticated-orcid":false,"given":"Arman","family":"Allahverdi","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9285-7712","authenticated-orcid":false,"given":"Simon","family":"Abrelat","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anna","family":"Hemingway","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2695-5788","authenticated-orcid":false,"given":"Adil","family":"Farooq","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Isabella","family":"Smith","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nitya","family":"Arora","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5285-7860","authenticated-orcid":false,"given":"Allen","family":"Chang","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-6380-1089","authenticated-orcid":false,"given":"Yongyu","family":"Qiang","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9731-6563","authenticated-orcid":false,"given":"Vincent","family":"Mooney","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01zkghx44","id-type":"ROR","asserted-by":"publisher"}],"name":"Georgia Institute of Technology","place":["Atlanta, Georgia, 30332, United States of America"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,1,13]]},"reference":[{"key":"ref1:Matsui","isbn-type":"print","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/3-540-48285-7_33","article-title":"Linear Cryptanalysis Method for DES Cipher","author":"Mitsuru Matsui","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540482857"},{"key":"ref2:Rueppel86","series-title":"Communications and Control Engineering","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-82865-2","volume-title":"Analysis and Design of Stream Ciphers","author":"Rainer A Rueppel","year":"1986"},{"key":"ref3:DubrovaCompositions","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/s10623-014-9947-3","article-title":"Generation of full cycles by a composition of NLFSRs","volume":"73","author":"Elena Dubrova","year":"2014","journal-title":"Designs, Codes, and Cryptography"},{"key":"ref4:Lei","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-53368-6_1","article-title":"More Balanced Polynomials: Cube Attacks on 810- and\n  825-Round Trivium with Practical Complexities","author":"He Lei","year":"2024","journal-title":"Selected Areas in Cryptography \u2013 SAC 2023"},{"key":"ref5:handbookofappliedcrypto","isbn-type":"print","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1201\/9780429466335","volume-title":"Handbook of Applied Cryptography","author":"Alfred J. Menezes","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/9780429466335"},{"key":"ref6:10.1007\/3-540-39799-X_41","isbn-type":"print","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/3-540-39799-X_41","article-title":"On the Design of S-Boxes","author":"A. F. Webster","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540397991"},{"key":"ref7:rotman1995an","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4176-8","volume-title":"An Introduction to the Theory of Groups","author":"Joseph Rotman","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/0387942858"},{"key":"ref8:Canteaut2005","isbn-type":"print","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/0-387-23483-7_165","volume-title":"Encyclopedia of Cryptography and Security","author":"Anne Canteaut","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387234830"},{"key":"ref9:niederreiter94","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172769","volume-title":"Introduction to Finite Fields and their Applications","author":"Rudolf Lidl","year":"1994"},{"key":"ref10:Trivium08","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-540-68351-3_18","article-title":"Trivium","author":"Christophe De Canni\u00e8re","year":"2008"},{"key":"ref11:streamciphers","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032688","volume-title":"Understanding Cryptography: A Textbook for Students and\n  Practitioners","author":"Christof Paar","year":"1997"},{"key":"ref12:intelfpga","volume-title":"DE10-Standard","author":"Inc. Terasic","year":"2017"},{"key":"ref13:xlGrobnerComparison","isbn-type":"print","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/978-3-540-30539-2_24","article-title":"Comparison Between XL and Gr\u00f6bner Basis Algorithms","author":"Gw\u00e9nol\u00e9 Ars","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540305392"},{"key":"ref14:XLOriginal","isbn-type":"print","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-45539-6_27","article-title":"Efficient Algorithms for Solving Overdefined Systems of\n  Multivariate Polynomial Equations","author":"Nicolas Courtois","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540455394"},{"key":"ref15:fastAlg","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-540-45146-4_11","article-title":"Fast Algebraic Attacks on Stream Ciphers with Linear\n  Feedback","volume":"2729","author":"Nicolas T. Courtois","year":"2003"},{"key":"ref16:quartusprime","volume-title":"Intel\u00ae Quartus\u00ae Prime Lite Edition Design Software\n  Version 20.1.1 for Windows","author":"Intel Corporation","year":"2019"},{"key":"ref17:Canteaut","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/0-387-23483-7_70","article-title":"Combination Generator","author":"Anne Canteaut","year":"2011"},{"key":"ref18:linalg","isbn-type":"print","volume-title":"Linear Algebra with Applications","author":"Steven Leon","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/2009023730"},{"key":"ref19:dubrova_fib_to_gal","doi-asserted-by":"publisher","first-page":"5263","DOI":"10.1109\/TIT.2009.2030467","article-title":"A Transformation From the Fibonacci to the Galois NLFSRs","volume":"55","author":"Elena Dubrova","year":"2009","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref20:Key1976","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1109\/tit.1976.1055626","article-title":"An Analysis of the Structure and Complexity of Nonlinear\n  Binary Sequence Generators","volume":"22","author":"E. Key","year":"1976","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref21:pugh2019systematic","volume-title":"Systematic Testing of Lightweight Cryptographic\n  Implementations","author":"Sydney Pugh","year":"2019"},{"key":"ref22:Quark2012","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00145-012-9125-6","article-title":"Quark: A Lightweight Hash","volume":"26","author":"Jean-Philippe Aumasson","year":"2012","journal-title":"Journal of Cryptology"},{"key":"ref23:synopsysdv","volume-title":"Design Vision User Guide","author":"Inc. Synopsys","year":"2003"},{"key":"ref24:abramovici1994","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1109\/9780470544389","volume-title":"Digital Systems Testing and Testable Design","author":"Miron Abramovici","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0780310624"},{"key":"ref25:mykkeltveit1979","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/S0019-9958(79)90708-3","article-title":"On the Cycle Structure of Some Nonlinear Shift Register\n  Sequences","volume":"43","author":"Johannes Mykkeltveit","year":"1979","journal-title":"Information and Control","ISSN":"https:\/\/id.crossref.org\/issn\/0019-9958","issn-type":"electronic"},{"key":"ref26:aboutXL","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/3-540-36563-X_10","article-title":"About the XL algorithm over GF(2)","volume":"2612","author":"N. Courtois","year":"2003"},{"key":"ref27:Feistel73","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1038\/scientificamerican0573-15","article-title":"Cryptography and Computer Privacy","volume":"228","author":"Horst Feistel","year":"1973","journal-title":"Scientific American"},{"key":"ref28:CourtoisAlgebraic","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/3-540-39200-9_21","article-title":"Algebraic Attacks on Stream Ciphers with Linear Feedback","author":"Nicolas T. Courtois","year":"2003"},{"key":"ref29:Trivium06","series-title":"ISC'06","isbn-type":"print","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/11836810_13","article-title":"Trivium: A Stream Cipher Construction Inspired by Block\n  Cipher Design Principles","author":"Christophe De Canni\u00e8re","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/3540383417"},{"key":"ref30:innovus","volume-title":"Innovus Implementation System","author":"Inc. Cadence Design Systems","year":"2015"},{"key":"ref31:virtuoso","volume-title":"Virtuoso Layout Suite","author":"Inc. Cadence Design Systems","year":"1991"},{"key":"ref32:chang_et_al_2020","doi-asserted-by":"publisher","first-page":"3766","DOI":"10.1109\/TIT.2019.2956741","article-title":"Cycle Structures of a Class of Cascaded FSRs","volume":"66","author":"Zuling Chang","year":"2020","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref33:BerlekampMassey","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/tit.1969.1054260","article-title":"Shift-register Synthesis and BCH Decoding","volume":"15","author":"J. Massey","year":"1969","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref34:golomb1982shift","isbn-type":"print","volume-title":"Shift Register Sequences","author":"Solomon Golomb","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/9780894120480"},{"key":"ref35:MandalGong2016","doi-asserted-by":"publisher","first-page":"2725","DOI":"10.1109\/TC.2015.2506557","article-title":"Feedback Reconstruction and Implementations of Pseudorandom\n  Number Generators from Composited De Bruijn Sequences","volume":"65","author":"Kalikinkar Mandal","year":"2016","journal-title":"IEEE Transactions on Computers"},{"key":"ref36:singleCycleTFuncs","isbn-type":"print","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/11863854_34","article-title":"The Algebraic Normal Form, Linear Complexity and k-Error\n  Linear Complexity of Single-Cycle T-Function","author":"Wenying Zhang","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540445241"},{"key":"ref37:Grove1997","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04101-3","volume-title":"Groups and Characters","author":"Larry C. Grove","year":"2010"},{"key":"ref38:KS04","isbn-type":"print","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-540-24654-1_18","article-title":"Cryptographic Applications of T-Functions","author":"Alexander Klimov","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540246541"},{"key":"ref39:debruijn","first-page":"758","article-title":"A Combinatorial Problem","volume":"49","author":"N.G. de Bruijn","year":"1946","journal-title":"Proceedings of the Section of Sciences of the Koninklijke\n  Nederlandse Akademie van Wetenschappen te Amsterdam"},{"key":"ref40:MersenneTwister","isbn-type":"print","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/978-3-540-74496-2_36","article-title":"SIMD-Oriented Fast Mersenne Twister: a 128-bit Pseudorandom\n  Number Generator","author":"Mutsuo Saito","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540744962"},{"key":"ref41:1675242","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1109\/TC.1979.1675242","article-title":"Structured Design of Substitution-Permutation Encryption\n  Networks","volume":"C-28","author":"John B. Kam","year":"1979","journal-title":"IEEE Transactions on Computers"},{"key":"ref42:cyclonev","volume-title":"Cyclone\u00ae V FPGA and SoC FPGA","author":"Intel Corporation","year":"2013"},{"key":"ref43:impFastAlg","isbn-type":"print","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-540-25937-4_5","article-title":"Improving Fast Algebraic Attacks","author":"Frederik Armknecht","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540259374"},{"key":"ref44:cubetesters","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-03317-9_1","volume-title":"Lecture Notes in Computer Science","author":"Jean-Philippe Aumasson","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642033179"},{"key":"ref45:cubeattacksurvey","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-023-00602-w","article-title":"Fourteen Years of Cube Attacks","author":"Marco Cianfriglia","year":"2023","journal-title":"Applicable Algebra in Engineering, Communication, and\n  Computing"},{"key":"ref46:Shannon:1945:MTC","volume-title":"A Mathematical Theory of Cryptography","author":"Claude Shannon","year":"1945"},{"key":"ref47:freepdk45","volume-title":"FreePDK45(TM)","author":"North Carolina State University","year":"2011"},{"key":"ref48:dubrovanlfsrs","volume-title":"A List of Maximum Period NLFSRs","author":"Elena Dubrova","year":"2012"},{"key":"ref49:greendimond","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1049\/piee.1970.0134","article-title":"Nonlinear Product-Feedback Shift Registers","volume":"117","author":"D.H. Green","year":"1970","journal-title":"Proceedings of the Institution of Electrical Engineers","ISSN":"https:\/\/id.crossref.org\/issn\/0020-3270","issn-type":"electronic"},{"key":"ref50:F4","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","article-title":"A New Efficient Algorithm for Computing Gr\u00f6bner Bases\n  (F4)","volume":"139","author":"JC. Faug\u00e8re","year":"1999","journal-title":"Journal of Pure and Applied Algebra"},{"key":"ref51:NISTSuite","doi-asserted-by":"crossref","first-page":"171","DOI":"10.6028\/NIST.SP.800-22r1a","volume-title":"A Statistical Test Suite for Random and Pseudorandom Number\n  Generators for Cryptographic Applications","volume":"800","author":"Lawrence E. Bassham","year":"2010"},{"key":"ref52:Cube","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-01001-9_16","article-title":"Cube Attacks on Tweakable Black Box Polynomials","author":"Itai Dinur","year":"2009"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:11:42Z","timestamp":1736788302000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/4\/19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,13]]},"references-count":52,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,1,13]]}},"URL":"https:\/\/doi.org\/10.62056\/a3tx11zn4","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,13]]},"assertion":[{"value":"2024-10-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-4-32"}}