Multisequences with high joint nonlinear complexity. (English) Zbl 1405.94037
Summary: We introduce the new concept of joint nonlinear complexity for multisequences over finite fields and we analyze the joint nonlinear complexity of two families of explicit inversive multisequences. We also establish a probabilistic result on the behavior of the joint nonlinear complexity of random multisequences over a fixed finite field.
MSC:
| 94A55 | Shift register sequences and sequences over finite alphabets in information and communication theory |
| 65C10 | Random number generation in numerical analysis |
| 11K45 | Pseudo-random numbers; Monte Carlo methods |
References:
| [1] | Breiman L.: Probability. SIAM, Philadelphia (1992). · Zbl 0753.60001 |
| [2] | Dawson E., Simpson L.: Analysis and design issues for synchronous stream ciphers. In: Niederreiter H. (ed.) Coding Theory and Cryptology. Lecture Notes Series Institute of Mathematical Sciences at the National University of Singapore, vol. 1, pp. 49-90. World Scientific Publishing, River Edge (2002). · Zbl 1029.94024 |
| [3] | Eichenauer-Herrmann J.: Statistical independence of a new class of inversive congruential pseudorandom numbers. Math. Comput. 60, 375-384 (1993). · Zbl 0795.65002 |
| [4] | Erdmann D., Murphy S.: An approximate distribution for the maximum order complexity. Des. Codes Cryptogr. 10, 325-339 (1997). · Zbl 0876.94014 |
| [5] | Gutierrez J., Shparlinski I.E., Winterhof A.: On the linear and nonlinear complexity profile of nonlinear pseudorandom number generators. IEEE Trans. Inf. Theory 49, 60-64 (2003). · Zbl 1063.65005 |
| [6] | Hawkes P., Rose G.G.: Exploiting multiples of the connection polynomial in word-oriented stream ciphers. In: Okamoto T. (ed.) Advances in Cryptology—ASIACRYPT 2000 (Kyoto). Lecture Notes in Computer Science, vol. 1976, pp. 303-316. Springer, Berlin (2000). · Zbl 0974.94013 |
| [7] | Jansen C.J.A.: Investigations on nonlinear streamcipher systems: construction and evaluation methods. Ph.D. Thesis, TU Delft (1989). |
| [8] | Jansen C.J.A.: The maximum order complexity of sequence ensembles. In: Davies D.W. (ed.) Advances in Cryptology—EUROCRYPT ’91. Lecture Notes in Computer Science, vol. 547, pp. 153-159. Springer, Berlin (1991). · Zbl 0791.68077 |
| [9] | Jansen C.J.A., Boekee D.E.: The shortest feedback shift register that can generate a given sequence. In: Brassard G. (ed.) Advances in Cryptology—CRYPTO ’89. Lecture Notes in Computer Science, vol. 435, pp. 90-99. Springer, Berlin (1990). · Zbl 0722.94010 |
| [10] | Lidl R., Niederreiter H.: Finite Fields. Cambridge University Press, Cambridge (1997). · Zbl 0866.11069 |
| [11] | Limniotis K., Kolokotronis N., Kalouptsidis N.: Nonlinear complexity of binary sequences and connections with Lempel-Ziv compression. In: Gong G. et al. (eds.) Sequences and Their Applications—SETA 2006. Lecture Notes in Computer Science, vol. 4086, pp. 168-179. Springer, Berlin (2006). · Zbl 1152.94391 |
| [12] | Limniotis K., Kolokotronis N., Kalouptsidis N.: On the nonlinear complexity and Lempel-Ziv complexity of finite length sequences. IEEE Trans. Inf. Theory 53, 4293-4302 (2007). · Zbl 1326.94063 |
| [13] | Loève M.: Probability Theory, 3rd edn. Van Nostrand Reinhold, New York (1963). · Zbl 0108.14202 |
| [14] | Meidl W., Winterhof A.: On the linear complexity profile of explicit nonlinear pseudorandom numbers. Inf. Process. Lett. 85, 13-18 (2003). · Zbl 1042.68053 |
| [15] | Meidl W., Winterhof A.: On the linear complexity profile of some new explicit inversive pseudorandom numbers. J. Complex. 20, 350-355 (2004). · Zbl 1045.94011 |
| [16] | Meidl W., Winterhof A.: On the joint linear complexity profile of explicit inversive multisequences. J. Complex. 21, 324-336 (2005). · Zbl 1094.94023 |
| [17] | Meidl W., Winterhof A.: Linear complexity of sequences and multisequences. In: Mullen G.L., Panario D. (eds.) Handbook of Finite Fields, pp. 324-336. CRC Press, Boca Raton (2013). · Zbl 1094.94023 |
| [18] | Niederreiter H., Winterhof A.: Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators. Acta Arith. 93, 387-399 (2000). · Zbl 0969.11040 |
| [19] | Niederreiter H., Xing C.P.: Sequences with high nonlinear complexity. IEEE Trans. Inf. Theory 60, 6696-6701 (2014). · Zbl 1360.94284 |
| [20] | Xing C.P.: Multi-sequences with almost perfect linear complexity profile and function fields over finite fields. J. Complex. 16, 661-675 (2000). · Zbl 1026.94006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
