Properties of classes of Boolean functions constructed from several linear recurrences over a residue ring $\mathbb{Z}_{2^n}$

A. D. Bugrov ; O. V. Kamlovskii

Matematičeskie voprosy kriptografii, Tome 15 (2024) no. 4, pp. 9-22

Résumé

The paper defines a class of Boolean functions constructed from higher bit sequences of several linear recurrences over the ring $\mathbb{Z}_{2^n}.$ To build the higher bit sequences various coordinate sets are used. It is shown that this class consists of functions that are significantly far from the class of all linear functions.

Bibliographie

[1] Glukhov M.M., Elizarov V.P., Nechaev A.A., Algebra, Uchebnik, v. 2, Gelios ARV, M., 2003, 416 pp.

[2] Lidl R., Niderraiter G., Konechnye polya, v. 1, 2, Mir, M., 1988, 822 pp.

[3] Nechaev A.A., “Tsiklovye tipy lineinykh podstanovok nad konechnymi kommutativnymi koltsami”, Mat. sb., 184:3 (1993), 21–56 | Zbl

[4] Kuzmin A.S., Nechaev A.A., “Lineinye rekurrentnye posledovatelnosti nad koltsami Galua”, Algebra i logika, 34:2 (1995), 169–189 | MR | Zbl

[5] Kamlovskii O.V., “Metod trigonometricheskikh summ dlya issledovaniya chastot $r$-gramm v starshikh koordinatnykh posledovatelnostyakh lineinykh rekurrent nad koltsom $\mathbb{Z}_{2^n}$”, Matematicheskie voprosy kriptografii, 1:4 (2010), 33–62 | DOI | Zbl

[6] Bylkov D.N., Kamlovskii O.V., “Parametry bulevykh funktsii, postroennykh s ispolzovaniem starshikh koordinatnykh posledovatelnostei lineinykh rekurrent”, Matematicheskie voprosy kriptografii, 3:4 (2012), 25–53 | DOI | Zbl

[7] Bylkov D.N., “Ob odnom klasse bulevykh funktsii, postroennykh s ispolzovaniem starshikh razryadnykh posledovatelnostei lineinykh rekurrent”, Prikladnaya diskretnaya matematika. Prilozhenie, 2014, no. 7, 59–60

[8] Kamlovskii O.V., “Nelineinost odnogo klassa bulevykh funktsii, postroennykh s ispolzovaniem dvoichnykh razryadnykh posledovatelnostei lineinykh rekurrent nad koltsom $\mathbb{Z}_{2^n}$”, Matematicheskie voprosy kriptografii, 7:3 (2016), 29–46 | DOI | MR | Zbl

[9] Bugrov A.D., Kamlovskii O.V., “Parametry odnogo klassa funktsii, zadannykh na konechnom pole”, Matematicheskie voprosy kriptografii, 9:4 (2018), 31–52 | DOI | MR | Zbl

[10] Gruba A.A., “Bulevy funktsii, postoennye s ispolzovaniem razryadnykh posledovatelnostei lineinykh rekurrent”, Diskretnaya matematika, 35:1 (2023), 54–61 | DOI

[11] Kamlovskii O.V., Kuzmin A.S., “Otsenki chastot poyavleniya elementov v lineinykh rekurrentnykh posledovatelnostyakh nad koltsami Galua”, Fundam. i prikl. matematika, 6:4 (2000), 1083–1094 | MR | Zbl

[12] Ambrosimov A.S., “Svoistva bent-funktsii $q$-znachnoi logiki nad konechnymi polyami”, Diskretnaya matematika, 6:3 (1994), 50–60 | MR | Zbl

[13] Solodovnikov V.I., “Bent-funktsii iz konechnoi abelevoi gruppy v konechnuyu abelevu gruppu”, Diskretnaya matematika, 14:1 (2002), 99–113 | DOI | Zbl

[14] Logachev O.A., Salnikov A.A., Smyshlyaev S.V., Yaschenko V.V., Bulevy funktsii v teorii kodirovaniya i kriptologii, MTsNMO, M., 2012, 584 pp.

[15] Shparlinski I.E., Winterhof A., “On the nonlinearity of linear recurrence sequences”, Appl. Math. Letters, 19:4 (2006), 340–344 | DOI | MR | Zbl

[16] Bylkov D.N., “Klass uslozhnenii lineinykh rekurrent nad koltsom Galua, ne privodyaschii k potere informatsii”, Problemy peredachi informatsii, 46:3 (2010), 51–59 | MR | Zbl