Pseudo-random sequences with long period, low correlation, high linear complexity, and uniform distribution of bit patterns are widely used in the field of information security and cryptography. This paper proposes an approach for generating a pseudo-random multi-value sequence (including a binary sequence) by utilizing a primitive polynomial, trace function, and k-th power residue symbol over the sub extension field. All our previous sequences are defined over the prime field, whereas, proposed sequence in this paper is defined over the sub extension field. Thus, it’s a new and innovative perception to consider the sub extension field during the sequence generation procedure. By considering the sub extension field, two notable outcomes are: proposed sequence holds higher linear complexity and more uniform distribution of bit patterns compared to our previous work which defined over the prime field. Additionally, other important properties of the proposed multi-value sequence such as period, autocorrelation, and cross-correlation are theoretically shown along with some experimental results.
References
[1]
Goresky, M. and Klapper, A. (2012) Algebraic Shift Register Sequences. Cambridge University Press, Cambridge.
[2]
Hamza, R. (2017) A Novel Pseudo Random Sequence Generator for Image-Cryptographic Applications. Journal of Information Security and Applications, 35, 119-127.
https://doi.org/10.1016/j.jisa.2017.06.005
[3]
Golomb, S.W. (1967) Shift Register Sequences. Holden-Day, San Francisco, CA.
[4]
Menezes, A.J., Van Oorschot, P.C. and Vanstone, S.A. (1996) Handbook of Applied Cryptography. CRC Press, Boca Raton, FL.
[5]
Salhab, O., Jweihan, N., Jodeh, M.A., Taha, M.A. and Farajallah, M. (2018) Survey paper: Pseudo Random Number Generators and Security Tests. Journal of Theoretical and Applied Information Technology, 96, 1951-1970.
[6]
Kinga, A., Aline, F. and Christain, E. (2012) Generation and Testing of Random Numbers for Cryptographic Applications. Proceedings of Romanian Academy, 13, 368-377.
[7]
Parvees, M.Y.M., Samath, J.A. and Bose, B.P. (2019) Cryptographically Secure Diffusion Sequences—An Attempt to Prove Sequences Are Random. In: Peter, J., Alavi, A. and Javadi, B., Ed., Advances in Big Data and Cloud Computing, Springer, Singapore, 433-442. https://doi.org/10.1007/978-981-13-1882-5_37
[8]
Matsumoto, M. and Nishimura, T. (1998) Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator. ACM Transactions on Modeling and Computer Simulation, 8, 3-30.
https://doi.org/10.1145/272991.272995
[9]
Blum, L., Blum, M. and Shub, M. (1986) A Simple Unpredictable Pseudorandom Number Generator. SIAM Journal on Computing, 15, 364-383.
https://doi.org/10.1137/0215025
[10]
Zierler, N. (1958) Legendre Sequence. MIT Lincoln Publications, Lexington, MA.
[11]
Zierler, N. (1959) Linear Recurring Sequences. Journal of the Society for Industrial and Applied Mathematics, 7, 31-48. https://doi.org/10.1137/0107003
[12]
Sidelnikov, V.M. (1971) On Mutual Correlation of Sequences. Soviet Mathematics-Doklady, 12, 197-201.
[13]
Nogami, Y., Tada, K. and Uehara, S. (2014) Geometric Sequence Binarized with Legendre Symbol over Odd Characteristic Field and Its Properties. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A, 2336-2342. https://doi.org/10.1587/transfun.E97.A.2336
[14]
Nogami, Y., Uehara, S., Tsuchiya, K., Begum, N., Ino, H. and Morelos-Zaragoza, R.H. (2016) A Multi-Value Sequence Generated by Power Residue Symbol and Trace Function over Odd Characteristic Field. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E99-A, 2226-2237.
https://doi.org/10.1587/transfun.E99.A.2226
[15]
Arshad, A.M., Nogami, Y., Ino, H. and Uehara, S. (2016) Auto and Cross Correlation of Well Balanced Sequence Over Odd Characteristic Field. 2016 Fourth International Conference on Computing and Networking, Hiroshima, Japan, 22-25 November 2016, 604-609. https://doi.org/10.1109/CANDAR.2016.0109
[16]
Arshad, A.M., Nogami, Y., Ogawa, C., Ino, H., Uehara, S., Morelos-Zaragoza, R. and Tsuchiya, K. (2016) A New Approach for Generating Well Balanced Pseudo-random Signed Binary Sequence Over Odd Characteristic Field. 2016 International Symposium on Information Theory and Its Applications, Monterey, CA, 30 October-2 November 2016, 777-780.
[17]
Arshad, A.M., Miyazaki, T., Nogami, Y., Uehara, S. and Morelos-Zaragoza, R. (2017) Multi-Value Sequence Generated by Trace Function and Power Residue Symbol Over Proper Sub Extension Field. IEEE International Conference on Consumer Electronics-Taiwan, Taipei, Taiwan, 12-14 June 2017, 249-250.
https://doi.org/10.1109/ICCE-China.2017.7991089
[18]
Lidl, R. and Niederreiter, H. (1984) Finite Fields, Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge.
[19]
Berlekamp, E.R. (1984) Algebraic Coding Theory. Aegean Park Press, Walnut Creek, CA.
[20]
Helleseth, T. and Kumar, P.V. (1998) Sequences with low correlation. In: Handbook of Coding Theory, North-Holland, Amsterdam.
[21]
Hertel, D. (2005) Cross-Correlation Properties of Perfect Binary Sequence. In: Helleseth, T., Sarwate, D., Song, H.Y. and Yang, K., Eds., Sequences and Their Applications: SETA 2004. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg.
https://doi.org/10.1007/11423461_14
[22]
Kumar, P.J. and Moreno, O. (1991) Prime-Phase Sequences with Periodic Correlation Properties Better Than Binary Sequences. IEEE Transactions on Information Theory, 37, 603-616. https://doi.org/10.1109/18.79916
[23]
Alecu, A. and Salagean, A. (2007) Modified Berlekamp-Massey Algorithm for Approximating the k-Error Linear Complexity of Binary Sequences. In: Galbraith, S.D., Ed., Cryptography and Coding. Cryptography and Coding 2007. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 220-232.
https://doi.org/10.1007/978-3-540-77272-9_14
