Scalable Nonlinear Sequence Generation using Composite Mersenne Product Registers

David Gordon; Arman Allahverdi; Simon Abrelat; Anna Hemingway; Adil Farooq; Isabella Smith; Nitya Arora; Allen Ian Chang; Yongyu Qiang; Vincent John Mooney III

doi:10.62056/a3tx11zn4

Scalable Nonlinear Sequence Generation using Composite Mersenne Product Registers

Authors

David Gordon, Arman Allahverdi, Simon Abrelat, Anna Hemingway, Adil Farooq, Isabella Smith, Nitya Arora, Allen Ian Chang, Yongyu Qiang, Vincent John Mooney III

David Gordon

Georgia Institute of Technology, Atlanta, United States of America
dgordon48 at gatech dot edu

Arman Allahverdi

Georgia Institute of Technology, Atlanta, United States of America
aallahverdi3 at gatech dot edu

Simon Abrelat

Georgia Institute of Technology, Atlanta, United States of America
simon dot abrelat at gatech dot edu

Anna Hemingway

Georgia Institute of Technology, Atlanta, United States of America
ahemingway6 at gatech dot edu

Adil Farooq

Georgia Institute of Technology, Atlanta, United States of America
afarooq32 at gatech dot edu

Isabella Smith

Georgia Institute of Technology, Atlanta, United States of America
ismith80 at gatech dot edu

Nitya Arora

Georgia Institute of Technology, Atlanta, United States of America
narora70 at gatech dot edu

Allen Ian Chang

Georgia Institute of Technology, Atlanta, United States of America
allen dot chang at gatech dot edu

Yongyu Qiang

Georgia Institute of Technology, Atlanta, United States of America
yqiang7 at gatech dot edu

Vincent John Mooney III

Georgia Institute of Technology, Atlanta, United States of America
mooney at gatech dot edu

Keywords: LFSR Cascade Connection Cycle Structure CMPR Nonlinear Sequence Generation Stream Cipher

Abstract

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.

References

[Abr94]

Miron Abramovici. Digital Systems Testing and Testable Design. IEEE Wiley-Interscience, New York, NY 1994.

Google Scholar ePrint

[ADMS09]

Jean-Philippe Aumasson, Itai Dinur, Willi Meier, and Adi Shamir. Cube Testers and Key Recovery Attacks On Reduced-Round MD6 and Trivium, pages 1–22. Springer, Cham 2009. DOI: 10.1007/978-3-642-03317-9_1

Google Scholar ePrint

[AFI⁺04]

Gwénolé Ars, Jean-Charles Faugère, Hideki Imai, Mitsuru Kawazoe, and Makoto Sugita. Comparison Between XL and Gröbner Basis Algorithms. In Pil Joong Lee, editor, Advances in Cryptology - ASIACRYPT 2004, pages 338–353, Berlin, Heidelberg. 2004. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-30539-2_24

Google Scholar ePrint

[AHMN12]

Jean-Philippe Aumasson, Luca Henzen, Willi Meier, and María Naya-Plasencia. Quark: A Lightweight Hash. Journal of Cryptology, 26(2):313–339, May 2012. DOI: 10.1007/s00145-012-9125-6

Google Scholar ePrint

[Arm04]

Frederik Armknecht. Improving Fast Algebraic Attacks. In Bimal Roy and Willi Meier, editors, Fast Software Encryption, pages 65–82, Berlin, Heidelberg. 2004. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-25937-4_5

Google Scholar ePrint

[BRS⁺10]

Lawrence E. Bassham, Andrew L. Rukhin, Juan Soto, James R. Nechvatal, Miles E. Smid, Elaine B. Barker, Stefan D. Leigh, Mark Levenson, Mark Vangel, David L. Banks, Nathanael Alan Heckert, James F. Dray, and San Vo. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. Technical report number 22, National Institute of Standards and Techonology. April 2010.

Google Scholar ePrint

[Cad15]

Inc. Cadence Design Systems. Innovus Implementation System. 2015.

Google Scholar ePrint

[Cad91]

Inc. Cadence Design Systems. Virtuoso Layout Suite. 1991.

Google Scholar ePrint

[Can05]

Anne Canteaut. Filter Generator, pages 223–224. Springer US, Boston, MA 2005. DOI: 10.1007/0-387-23483-7_165

Google Scholar ePrint

[Can11]

Anne Canteaut. Combination Generator. In Encyclopedia of Cryptography and Security (2nd ed.), pages 82–83. Springer US 2011. DOI: 10.1007/0-387-23483-7_70

Google Scholar ePrint

[CGW20]

Zuling Chang, Guang Gong, and Qiang Wang. Cycle Structures of a Class of Cascaded FSRs. IEEE Transactions on Information Theory, 66(6):3766-3774, 2020. DOI: 10.1109/TIT.2019.2956741

Google Scholar ePrint

[CKPS00]

Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In Advances in Cryptology — EUROCRYPT 2000, pages 392–407. 2000. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45539-6_27

Google Scholar ePrint

[CM03]

Nicolas T. Courtois and Willi Meier. Algebraic Attacks on Stream Ciphers with Linear Feedback. In Eli Biham, editor, Advances in Cryptology — EUROCRYPT 2003, pages 345–359, Berlin, Heidelberg. 2003. Springer Berlin Heidelberg. DOI: 10.1007/3-540-39200-9_21

Google Scholar ePrint

[COOP23]

Marco Cianfriglia, Elia Onofri, Silvia Onofri, and Marco Pedicini. Fourteen Years of Cube Attacks. Applicable Algebra in Engineering, Communication, and Computing, May 2023. DOI: 10.1007/s00200-023-00602-w

Google Scholar ePrint

[Cor13]

Intel Corporation. Cyclone® V FPGA and SoC FPGA. 2013.

Google Scholar ePrint

[Cor19]

Intel Corporation. Intel® Quartus® Prime Lite Edition Design Software Version 20.1.1 for Windows. 2019.

Google Scholar ePrint

[Cou03]

Nicolas T. Courtois. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, volume 2729, pages 176–194, Berlin, Heidelberg. 2003. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-45146-4_11

Google Scholar ePrint

[CP03]

N. Courtois and J. Patarin. About the XL algorithm over GF(2). In Topics in Cryptology — CT-RSA 2003, volume 2612, pages 141–157. 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-36563-X_10

Google Scholar ePrint

[dBru46]

N.G. de Bruijn. A Combinatorial Problem. Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, 49(7):758-764, 1946.

Google Scholar ePrint

[De 06]

Christophe De Cannière. Trivium: A Stream Cipher Construction Inspired by Block Cipher Design Principles. In Proceedings of the 9th International Conference on Information Security, pages 171–186, Berlin, Heidelberg. 2006. Springer-Verlag. DOI: 10.1007/11836810_13

Google Scholar ePrint

[DP08]

Christophe De Cannière and Bart Preneel. Trivium. In Lecture Notes in Computer Science, pages 244–266, Berlin, Heidelberg. 2008. Springer-Verlag. DOI: 10.1007/978-3-540-68351-3_18

Google Scholar ePrint

[DS09]

Itai Dinur and Adi Shamir. Cube Attacks on Tweakable Black Box Polynomials. In Antoine Joux, editor, Advances in Cryptology - EUROCRYPT 2009, pages 278–299, Berlin, Heidelberg. 2009. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-01001-9_16

Google Scholar ePrint

[Dub09]

Elena Dubrova. A Transformation From the Fibonacci to the Galois NLFSRs. IEEE Transactions on Information Theory, 55(11):5263-5271, 2009. DOI: 10.1109/TIT.2009.2030467

Google Scholar ePrint

[Dub12]

Elena Dubrova. A List of Maximum Period NLFSRs. 2012.

Google Scholar ePrint

[Dub14]

Elena Dubrova. Generation of full cycles by a composition of NLFSRs. Designs, Codes, and Cryptography, 73:469–486, March 2014. DOI: 10.1007/s10623-014-9947-3

Google Scholar ePrint

[Fau99]

JC. Faugère. A New Efficient Algorithm for Computing Gröbner Bases (F4). Journal of Pure and Applied Algebra, 139(1):61-88, 1999. DOI: https://doi.org/10.1016/S0022-4049(99)00005-5

Google Scholar ePrint

[Fei73]

Horst Feistel. Cryptography and Computer Privacy. Scientific American, 228(5):15–23, 1973.

Google Scholar ePrint

[GD70]

D.H. Green and K.R. Dimond. Nonlinear Product-Feedback Shift Registers. Proceedings of the Institution of Electrical Engineers, 117(4):681-686, 1970. DOI: https://doi.org/10.1049/piee.1970.0134

Google Scholar ePrint

[Gol82]

Solomon Golomb. Shift Register Sequences. Aegean Park Press, Laguna Hills, Calif 1982.

Google Scholar ePrint

[Gro10]

Larry C. Grove. Groups and Characters. John Wiley & Sons, Inc. 2010. DOI: 10.1007/978-3-642-04101-3

Google Scholar ePrint

[KD79]

John B. Kam and George I. Davida. Structured Design of Substitution-Permutation Encryption Networks. IEEE Transactions on Computers, C-28(10):747-753, 1979. DOI: 10.1109/TC.1979.1675242

Google Scholar ePrint

[Key76]

E. Key. An Analysis of the Structure and Complexity of Nonlinear Binary Sequence Generators. IEEE Transactions on Information Theory, 22(6):732–736, November 1976. DOI: 10.1109/tit.1976.1055626

Google Scholar ePrint

[KS04]

Alexander Klimov and Adi Shamir. Cryptographic Applications of T-Functions. In Mitsuru Matsui and Robert J. Zuccherato, editors, Selected Areas in Cryptography, pages 248–261, Berlin, Heidelberg. 2004. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-24654-1_18

Google Scholar ePrint

[Leo09]

Steven Leon. Linear Algebra with Applications, chapter 6.1. Pearson, New York 2009.

Google Scholar ePrint

[LH24]

He Lei and Wang Hu. More Balanced Polynomials: Cube Attacks on 810- and 825-Round Trivium with Practical Complexities. Selected Areas in Cryptography – SAC 2023, February 2024. DOI: 10.1007/978-3-031-53368-6_1

Google Scholar ePrint

[LN94]

Rudolf Lidl and Harald Niederreiter. Introduction to Finite Fields and their Applications. Cambridge University Press, 2 edition. 1994. DOI: 10.1017/CBO9781139172769

Google Scholar ePrint

[Mas69]

J. Massey. Shift-register Synthesis and BCH Decoding. IEEE Transactions on Information Theory, 15(1):122–127, January 1969. DOI: 10.1109/tit.1969.1054260

Google Scholar ePrint

[Mat94]

Mitsuru Matsui. Linear Cryptanalysis Method for DES Cipher. In Tor Helleseth, editor, Advances in Cryptology — EUROCRYPT '93, pages 386–397, Berlin, Heidelberg. 1994. Springer Berlin Heidelberg. DOI: 10.1007/3-540-48285-7_33

Google Scholar ePrint

[MG16]

Kalikinkar Mandal and Guang Gong. Feedback Reconstruction and Implementations of Pseudorandom Number Generators from Composited De Bruijn Sequences. IEEE Transactions on Computers, 65(9):2725-2738, 2016. DOI: 10.1109/TC.2015.2506557

Google Scholar ePrint

[MST79]

Johannes Mykkeltveit, Man-Keung Siu, and Po Tong. On the Cycle Structure of Some Nonlinear Shift Register Sequences. Information and Control, 43(2):202-215, 1979. DOI: https://doi.org/10.1016/S0019-9958(79)90708-3

Google Scholar ePrint

[MvOV97]

Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Public-Key Parameters, pages 154–160. CRC Press, Boca Raton, FL 1997. DOI: 10.1201/9780429466335

Google Scholar ePrint

[PP97]

Christof Paar and Jan Pelzl. Understanding Cryptography: A Textbook for Students and Practitioners. Springer Heidelberg Dordrecht London New York 1997. DOI: 10.1002/9781118032688

Google Scholar ePrint

[PRKK19]

Sydney Pugh, MS Raunak, D Richard Kuhn, and Raghu Kacker. Systematic Testing of Lightweight Cryptographic Implementations. Technical report, National Institute of Standards and Technology. November 2019.

Google Scholar ePrint

[Rot95]

Joseph Rotman. An Introduction to the Theory of Groups. Springer-Verlag, New York 1995.

Google Scholar ePrint

[Rue86]

Rainer A Rueppel. Analysis and Design of Stream Ciphers. Communications and Control Engineering. Springer, Berlin, Germany, 1986 edition. 1986.

Google Scholar ePrint

[Sha45]

Claude Shannon. A Mathematical Theory of Cryptography. Technical report, Bell Laboratories. September 1945.

Google Scholar ePrint

[SM08]

Mutsuo Saito and Makoto Matsumoto. SIMD-Oriented Fast Mersenne Twister: a 128-bit Pseudorandom Number Generator. In Alexander Keller, Stefan Heinrich, and Harald Niederreiter, editors, Monte Carlo and Quasi-Monte Carlo Methods 2006, pages 607–622, Berlin, Heidelberg. 2008. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-74496-2_36

Google Scholar ePrint

[Syn03]

Inc. Synopsys. Design Vision User Guide. 2003.

Google Scholar ePrint

[Ter17]

Inc. Terasic. DE10-Standard. 2017.

Google Scholar ePrint

[Uni11]

North Carolina State University. FreePDK45(TM). 2011.

Google Scholar ePrint

[WT86]

A. F. Webster and S. E. Tavares. On the Design of S-Boxes. In Hugh C. Williams, editor, Advances in Cryptology — CRYPTO '85 Proceedings, pages 523–534, Berlin, Heidelberg. 1986. Springer Berlin Heidelberg. DOI: 10.1007/3-540-39799-X_41

Google Scholar ePrint

[ZW06]

Wenying Zhang and Chuan-Kun Wu. The Algebraic Normal Form, Linear Complexity and k-Error Linear Complexity of Single-Cycle T-Function. In Guang Gong, Tor Helleseth, Hong-Yeop Song, and Kyeongcheol Yang, editors, Sequences and Their Applications – SETA 2006, pages 391–401, Berlin, Heidelberg. 2006. Springer Berlin Heidelberg. DOI: 10.1007/11863854_34

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a3tx11zn4

History

Submitted: 2024-10-09
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

David Gordon, Arman Allahverdi, Simon Abrelat, Anna Hemingway, Adil Farooq, Isabella Smith, Nitya Arora, Allen Ian Chang, Yongyu Qiang, and Vincent John Mooney III, Scalable Nonlinear Sequence Generation using Composite Mersenne Product Registers. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a3tx11zn4.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-4-19,
    author = "Gordon, David and Allahverdi, Arman and Abrelat, Simon and Hemingway, Anna and Farooq, Adil and Smith, Isabella and Arora, Nitya and Chang, Allen Ian and Qiang, Yongyu and III, Vincent John Mooney",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Scalable Nonlinear Sequence Generation using Composite Mersenne Product Registers",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/a3tx11zn4"
}

TY - JOUR
AU - Gordon, David
AU - Allahverdi, Arman
AU - Abrelat, Simon
AU - Hemingway, Anna
AU - Farooq, Adil
AU - Smith, Isabella
AU - Arora, Nitya
AU - Chang, Allen
AU - Qiang, Yongyu
AU - Mooney, Vincent
PY  - 2025
TI  - Scalable Nonlinear Sequence Generation using Composite Mersenne Product Registers
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 4
DO  - 10.62056/a3tx11zn4
UR  - https://doi.org/10.62056/a3tx11zn4
AB  - <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. </p>
ER  -

David Gordon, Arman Allahverdi, Simon Abrelat, Anna Hemingway, Adil Farooq, Isabella Smith, Nitya Arora, Allen Ian Chang, Yongyu Qiang, and Vincent John Mooney III, Scalable Nonlinear Sequence Generation using Composite Mersenne Product Registers. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a3tx11zn4.