Abstract
In this paper, binary sequences generated by nonlinearly filtering maximal length sequences are studied. Specifically, the parameter linear complexity of the filtered sequences has been considered and analyzed. In fact, a method of computing all the nonlinear filters that generate sequences with a cryptographically large linear complexity has been developed. The procedure is based on the concept of equivalence classes of nonlinear filters and on the addition of filters from different classes. Three distinct representations of nonlinear filters have been systematically addressed. The method completes the class of nonlinear filters with guaranteed linear complexity found in the cryptographic literature.
Research partially supported by CDTI (Spain) under Project Cenit- HESPERIA as well as by Ministry of Science and Innovation and European FEDER Fund under Project TIN2011-25452/TSI.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Nagaraj, N.: One-Time Pad as a nonlinear dynamical system. Commun Nonlinear Sci. Numer Simulat. 17, 4029–4036 (2012)
eSTREAM, the ECRYPT Stream Cipher Project,The eSTREAM Portfolio (2012), http://www.ecrypt.eu.org/documents/D.SYM.10-v1.pdf
Robshaw, M., Billet, O. (eds.): New Stream Cipher Designs. LNCS, vol. 4986. Springer, Heidelberg (2008)
Menezes, A.J., et al.: Handbook of Applied Cryptography. CRC Press, New York (1997)
Paar, C., Pelzl, J.: Understanding Cryptography. Springer, Heidelberg (2010)
Rueppel, R.A.: Analysis and Design of Stream Ciphers. Springer, New York (1986)
Tan, S.K., Guan, S.U.: Evolving cellular automata to generate nonlinear sequences with desirable properties. Applied Soft Computing 7, 1131–1134 (2007)
Golomb, S.: Shift-Register Sequences, revised edn. Aegean Park Press, Laguna Hills (1982)
Fúster-Sabater, A., Caballero-Gil, P., Delgado-Mohatar, O.: Deterministic Computation of Pseudorandomness in Sequences of Cryptographic Application. In: Allen, G., Nabrzyski, J., Seidel, E., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds.) ICCS 2009, Part I. LNCS, vol. 5544, pp. 621–630. Springer, Heidelberg (2009)
Fúster-Sabater, A., Caballero-Gil, P.: Chaotic modelling of the generalized self-shrinking generator. Appl. Soft Comput. 11, 1876–1880 (2011)
A. Marsaglia, Test of DIEHARD (1998), http://stat.fsu.edu/pub/diehard/
Massey, J.L.: Shift-Register Synthesis and BCH Decoding. IEEE Trans. Information Theory 15(1), 122–127 (1969)
Caballero-Gil, P., Fúster-Sabater, A.: A wide family of nonlinear filter functions with large linear span. Inform. Sci. 164, 197–207 (2004)
Limniotis, K., Kolokotronis, N., Kalouptsidis, N.: On the Linear Complexity of Sequences Obtained by State Space Generators. IEEE Trans. Inform. Theory 54, 1786–1793 (2008)
Kolokotronis, N., Limniotis, K., Kalouptsidis, N.: Lower Bounds on Sequence Complexity Via Generalised Vandermonde Determinants. In: Gong, G., Helleseth, T., Song, H.-Y., Yang, K. (eds.) SETA 2006. LNCS, vol. 4086, pp. 271–284. Springer, Heidelberg (2006)
Lee, K., O’Sullivan, M.E.: List decoding of Hermitian codes using Gröbner bases. Journal of Symbolic Computation 44(12), 1662–1675 (2009)
Respondek, J.S.: On the confluent Vandermonde matrix calculation algorithm. Applied Mathematics Letters 24(2), 103–106 (2011)
Respondek, J.S.: Numerical recipes for the high efficient inverse of the confluent Vandermonde matrices. Applied Mathematics and Computation 218(5), 2044–2054 (2011)
Lidl, R., Niederreiter, H.: Finite Fields. In: Enciclopedia of Mathematics and Its Applications, 2nd edn., vol. 20. Cambridge University Press, Cambridge (1997)
Ronjom, S., Helleseth, T.: A New Attack on the Filter Generator. IEEE Trans. Information Theory 53(5), 1752–1758 (2007)
Rønjom, S., Cid, C.: Nonlinear Equivalence of Stream Ciphers. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 40–54. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fúster-Sabater, A. (2013). Analysis of the Linear Complexity in Pseudorandom Sequence Generators. In: Murgante, B., et al. Computational Science and Its Applications – ICCSA 2013. ICCSA 2013. Lecture Notes in Computer Science, vol 7975. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39640-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-39640-3_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39639-7
Online ISBN: 978-3-642-39640-3
eBook Packages: Computer ScienceComputer Science (R0)