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 cryptographyREFERENCES:
 Berlekamp, E. R. (1968). Algebraic coding theory. McGraw-Hill Book Co., New YorkToronto, Ont.-London.
 Buchanan, W. J., Li, S., & Asif, R. (2017). Lightweight cryptography methods. Journal of Cyber Security Technology, 1(3-4), 187-201.
 Edemskiy, V., & Minin, A. (2016). About the linear complexity of the almost perfect sequences. International Journal of Communications, 1, 223-226.
 ISO/IEC 29192-3:2012. International standard for lightweight cryptographic methods, ISO/IEC, 2012.
 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.
 Massey, J. L. (1969). Shift-register synthesis and BCH decoding. IEEE Trans. Information Theory, IT-15, 122–127.
 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.
 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.
 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.
 Meier, W., Staffelbach, O.: The self-shrinking generator. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 205– 214. Springer, Heidelberg (1995).
 Randrianarisoa, T. (2018). Coding Theory using Linear Complexity of Finite Sequences. arXiv preprint arXiv:1802.10034.
 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
 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.
 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
 Venkateswarlu, A. (2007). Studies on error linear complexity measures for multisequences (Doctoral dissertation).
 Wang, Q., Jiang, Y., & Lin, D. (2015). Linear complexity of binary generalized cyclotomic sequences over GF (q). Journal of Complexity, 31(5), 731-740.
 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.