Abstract
A system related to the shrinking generator that is made up of two feedback shift registers in which one (FSR \( \mathbb{A} \))) controls the clocking of the other (FSR \( \mathbb{B} \)) is introduced. It is established that if FSR \( \mathbb{A} \)) generates an m-sequence of period (2m − 1) and FSR \( \mathbb{B} \) generates a de Bruijn sequence of period 2η, then the output sequence of the system has period P = 2m+ν−1, linear complexity L bounded from below by 2m+η−2, good statistical properties, and it is secure against correlation attacks. All these properties make it a suitable crypto-generator for stream cipher applications.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
D. Gollmann, and W. Chambers, “Clock-Controlled Shift Register: A Review” IEEE J. Sel. Ar. Comm. vol. 7, No. 4, May 1989, pp. 525–533.
S. W. Golomb, “Shift Register Sequences”, Aegean Park Press, 1982.
D. Coppersmith, H. Krawczyk, and Y. Mansour, “The Shrinking Generator”, Proceedings of Crypto 93, Springer-Verlag, 1994, pp 22–39.
R. Lidl, and H. Niederreiter, “Introduction to Finite Fields and Their Applications”, UK: Cambridge University Press, 1986.
A. Kanso, “Clock-Controlled Generators”, PhD thesis, University of London 1999, pp. 161.
J. Golic, and M. Mihaljevic, “A Generalized Correlation Attack on a Class of Stream Ciphers Based on the Levenstein Distance”, Journal of Cryptology, 3, 1991, pp. 201–212.
J. Golic, “Towards Fast Correlation Attacks on Irregularly Clocked Shift Registers”, Lecture Notes in Computer Science 921 (EuroCrypt 95), 1995, pp. 248–262.
W. Meir, and O. Staffelbach, “Fast Correlation Attacks on Certain Stream Ciphers”, Journal of Cryptology, 1, 1989, pp. 159–176.
T. Siegenthaler, “Correlation-Immunity of Non-linear Combining Functions for Cryptographic Applications”, IEEE Trans On Information Theory, 30, 1984, pp.776–780.
J. Golic, “On the Security of Shift Register Based Keystream Generators”, R. Anderson, Editor, Fast Software Encryption, Cambridge Security Workshop (LNCS 809), Springer-Verlag, 1994, pp. 90–100.
T. Johansson, “Reduced Complexity Correlation Attacks on Two Clock-Controlled Generators”, Advances of Cryptology (AsiaCrypt 98), Lecture Notes in Computer Science, vol. 1514, 1998, pp. 342–356.
M. Mihaljevic, “An Approach to the Initial State Reconstruction of a Clock-Controlled Shift Register Based on a Novel Distance Measure”, Advances in Cryptology (AusCrypt 92), Lecture Notes in Computer Science, vol. 178, 1993, pp. 349–356
J. Golic, and L.O. Connor, “Embedding Probabilistic Correlation Attacks on Clock-Controlled Shift Registers”, Advances in Cryptology (EuroCrypt 94), Lecture Notes in Computer Science, vol. 950, 1995, pp. 230–243.
L. Simpson, J. Golic, and E. Dawson, “A Probabilistic Correlation Attack on the Shrinking Generator”, ACISP 1998, pp. 147–158.
T. Johansson, F. Jonsson, “Improved Fast Correlation Attacks on Certain Stream Ciphers via Convolutional Codes”, Advances in Cryptography (EuroCrypt 99), Lecture Notes in Computer Science, vol. 1592, Springer-Verlag, 1999, pp. 347–362.
T. Johansson, F. Jonsson, “Fast Correlation Attacks Through Reconstruction of Linear Polynomials”, Advances in Cryptology (Crypto 2000), Lecture Notes in Computer Science, vol. 1880, Springer-Verlag, 2000, pp. 300–315.
W. Chambers, and S. Jennings, “Linear Equivalence of Certain BRM Shift Register Sequences”, Electronics Letters, vol. 20, November 1984, pp.1018–1019.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kanso, A. (2003). Clock-Controlled Shrinking Generator of Feedback Shift Registers. In: Safavi-Naini, R., Seberry, J. (eds) Information Security and Privacy. ACISP 2003. Lecture Notes in Computer Science, vol 2727. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45067-X_38
Download citation
DOI: https://doi.org/10.1007/3-540-45067-X_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40515-3
Online ISBN: 978-3-540-45067-2
eBook Packages: Springer Book Archive