Equidistant filters based on skew ML-sequences over fields

M. A. Goltvanitsa

Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 2, pp. 71-86

Résumé

Let $p$ be a prime number, $R = \mathrm{GF}(q)$ be a field of $q = p^r$ elements and $S = \mathrm{GF}(q^n)$ be an extension of $R$. Let $\breve{S}$ be the ring of all linear transformations of the space $_RS$. A linear recurring sequence $v$ of order $m$ over the module $_{\breve{S}}S$ is said to be a skew linear recurring sequence (skew LRS) of order $m$ over $S$. The period $T(v)$ of such sequence satisfies the inequality $T(v) \leqslant\tau = q^{mn}-1$. If $T(v) = \tau$ we call $v$ a skew LRS of maximal period (skew MP LRS). Here we investigate periodic properties and rank (linear complexity) of the sequence $y(i) = v(i)v(i + k)\cdot\ldots\cdot v(i + k(s-1))$, $k, s \in \mathbb{N}_0$, $i\geqslant 0$, where $v$ is a skew MP LRS. Based on the obtained results we propose new methods for filtering generators construction based on skew MP LRS.

Bibliographie

[1] Lidl R., Niederreiter H., Finite Fields, Cambridge Univ. Press, 1983, 755 pp. | MR | Zbl

[2] Kurakin V. L., Mikhalev A. V., Nechaev A. A., Tsypyschev V. N., “Linear and polylinear recurring sequences over Abelian groups and modules”, J. Math. Sci., 102:6 (2000), 4598–4626 | MR | Zbl

[3] Goltvanitsa M. A., Nechaev A. A., Zaitsev S. N., “Skew linear recurring sequences of maximal period over Galois rings”, J. Math. Sci., 187:2 (2012), 115–128 | DOI | MR | Zbl

[4] Goltvanitsa M. A., Nechaev A. A., Zaitsev S. N., “Skew LRS of maximal period over Galois rings”, Matem. Voprosy Kriptografii, 4:2 (2013), 59–72 | DOI | MR

[5] Goltvanitsa M. A., “A construction of skew LRS of maximal period over finite fields based on the defining tuples of factors”, Matem. Voprosy Kriptografii, 5:2 (2014), 37–46 | DOI | MR

[6] Goltvanitsa M. A., “Digit sequences of skew linear recurrences of maximal period over Galois rings”, Matem. Voprosy Kriptografii, 6:2 (2015), 189–197 | MR

[7] Goltvanitsa M. A., “The first digit sequence of skew linear recurrence of maximal period over Galois ring”, Matem. Voprosy Kriptografii, 7:3 (2016), 5–18 | DOI | MR

[8] Goltvanitsa M. A., “On a class of skew linear recurrences of maximal period over Galois rings”, Systemy vysokoi dostupnosti, 11:3 (2015), 28–49 (in Russian) | MR

[9] Tsaban B., Vishne U., “Efficient linear feedback shift registers with maximal period”, Finite Fields and Their Appl., 8:2 (2002), 256–267 | DOI | MR | Zbl

[10] Zeng G., He K. C., Han W., “A trinomial type of $\sigma$-LFSR oriented toward software implementation”, Sci. in China, Ser. F — Inf. Sci., 50:3 (2007), 359–372 | MR | Zbl

[11] Alferov A. P., Zubov A. U., Kuzmin A. S., Cheremushkin A. V., Foundations of Cryptography, Gelios ARV, 2002, 480 pp. (in Russian)

[12] Menezes A. J., Vanstone S. A., Van Oorschot P. C., Handbook of Applied Cryptography, CRC Press, 1996, 780 pp. | MR

[13] Rueppel R. A., Analysis and Design of Stream Ciphers, Springer-Verlag, Heidelberg etc., 1986, xii+244 pp. | MR | Zbl

[14] Bernasconi C., Gunter G., “Analysis of a nonlinear feedforward logic for binary sequence generators”, Lect. Notes Comput. Sci., 219, 1986, 161–166 | DOI | Zbl

[15] Bogonatov R. V., “Nechaev's hypothesis on linear recurrences multiplication”, Chebyshevskii sbornik, 6:1 (2005), 48–55 (in Russian) | MR | Zbl

[16] Kurakin V. L., “Polynomial transformations of linear recurrent sequences over the ring $p^2$”, Discrete Mathem. and Appl., 9:2 (1999), 185–210 | MR | Zbl

[17] Kolokotronis N., Liminiotis K., Kaloupsidis N., “Lower bounds on sequence complexity via generalised Vandermonde determinants”, Lect. Notes Comput. Sci., 4086, 2006, 271–284 | DOI | MR | Zbl

[18] Lam C., Gong G., “A lower bound for the linear span of filtering sequences”, State of Art of Stream Ciphers (SASC), 2004, 220–233

[19] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, v. 1, 2, Gelios ARV, 2003, 336+415 pp. (in Russian)