WSEAS Transactions on Computers

Print ISSN: 1109-2750
E-ISSN: 2224-2872

Volume 17, 2018

Notice: As of 2014 and for the forthcoming years, the publication frequency/periodicity of WSEAS Journals is adapted to the 'continuously updated' model. What this means is that instead of being separated into issues, new papers will be added on a continuous basis, allowing a more regular flow and shorter publication times. The papers will appear in reverse order, therefore the most recent one will be on top.

A Study on Linear Complexity of p-ary Pseudo Random Sequences Generated by pGSSG

AUTHORS: Antoniya Tasheva, Zhaneta Savova-Tasheva, Boyan Petrov

Download as PDF

ABSTRACT: Nowadays, when fast-growing areas, such as IoT, automotive systems, sensor networks, healthcare, distributed control systems, cyber-physical systems, and the smart grid, are widely used there is a need of specific device design with a better balance between security, performance, and resource requirements for resource-constrained environments. Because low linear complexity is undesirable for cryptographic applications, there is a necessity for lightweight cryptographic stream ciphers development with high linear complexity. Due to this reason a linear complexity of p-ary Generalized Self-Shrinking Generator (pGSSG), which has very simple design and is suitable for lightweight stream cipher, is investigated in this paper. Mathematically was shown that the extended Euclidean algorithm can be applied to find the linear complexity of p-ary pseudorandom sequences. The conducted tests show that the pGSSG linear complexity is close to its theoretical upper bound.

KEYWORDS: - Linear complexity, pseudo random sequences, pGSSG, extended Euclidean algorithm, pLFSR, lightweight cryptography


[1] Berlekamp, E. R. (1968). Algebraic coding theory. McGraw-Hill Book Co., New YorkToronto, Ont.-London.

[2] Buchanan, W. J., Li, S., & Asif, R. (2017). Lightweight cryptography methods. Journal of Cyber Security Technology, 1(3-4), 187-201.

[3] Edemskiy, V., & Minin, A. (2016). About the linear complexity of the almost perfect sequences. International Journal of Communications, 1, 223-226.

[4] ISO/IEC 29192-3:2012. International standard for lightweight cryptographic methods, ISO/IEC, 2012.

[5] Manifavas, C., Hatzivasilis, G., Fysarakis, K., & Papaefstathiou, Y. (2016). A survey of lightweight stream ciphers for embedded systems. Security and Communication Networks, 9(10), 1226-1246.

[6] Massey, J. L. (1969). Shift-register synthesis and BCH decoding. IEEE Trans. Information Theory, IT-15, 122–127.

[7] Massey, James L., and Shirlei Serconek. „Linear complexity of periodic sequences: a general theory.“ In Advances in cryptology— CRYPTO’96, pp. 358-371. Springer Berlin Heidelberg, 1996.

[8] McKay, K. A., Bassham, L., Turan, M. S., & Mouha, N. (2017). NISTIR 8114 report on lightweight cryptography. National Institute of Standards and Technology (NIST), Gaithersburg.

[9] Meidl, W., Winterhof, A. (2013). Linear complexity of sequences and multisequences, Handbook of finite fields. Chapter 10.4, pp. 318-330. Chapman and Hall/CRC.

[10] Meier, W., Staffelbach, O.: The self-shrinking generator. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 205– 214. Springer, Heidelberg (1995).

[11] Randrianarisoa, T. (2018). Coding Theory using Linear Complexity of Finite Sequences. arXiv preprint arXiv:1802.10034.

[12] Rueppel R.A. (1986) Linear Complexity and Random Sequences. In: Pichler F. (eds) Advances in Cryptology — EUROCRYPT’ 85. EUROCRYPT 1985. Lecture Notes in Computer Science, vol 219. Springer, Berlin, Heidelberg

[13] Tasheva, A., Tasheva, Zh., Milev, A., Generalization of the Self-Shrinking Generator in the Galois Field GF(pn ), Advances in Artificial Intelligence, vol. 2011, Article ID 464971, 10 pages, 2011.

[14] Tasheva, A., Savova-Tasheva, Zh., Petrov, B., Stoykov, K., Determining the Feedback Multipliers in a p-ary Linear Feedback Shift Registers, WSEAS Transactions on Systems and Control, Volume 13, 2018, Art. #45, pp. 420-424

[15] Venkateswarlu, A. (2007). Studies on error linear complexity measures for multisequences (Doctoral dissertation).

[16] Wang, Q., Jiang, Y., & Lin, D. (2015). Linear complexity of binary generalized cyclotomic sequences over GF (q). Journal of Complexity, 31(5), 731-740.

[17] Winterhof, A., Linear complexity and related complexity measures, in Selected Topics in Information and Coding Theory, vol. 7. Hackensack, NJ, USA: World Scientific, 2010, pp. 3–40.

WSEAS Transactions on Computers, ISSN / E-ISSN: 1109-2750 / 2224-2872, Volume 17, 2018, Art. #24, pp. 197-201

Copyright © 2018 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0

Bulletin Board


The editorial board is accepting papers.

WSEAS Main Site