Some classes of resilient functions over Galois rings and their linear characteristics

O. V. Kamlovskii ; K. N. Pankov

Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 18-22.

Résumé

Let $R=\text{GR}(q^l,p^l)=\{r_1,\ldots,r_{q^l}\}$ be a Galois ring. Let $A_n(R)$ be a set of all affine functions $g(\vec x)=a_0+a_1x_1+\ldots+a_nx_n=a_0+\langle \vec a,\vec x \rangle$, where $\vec x=(x_1,\ldots,x_n)$, $a_0\in R$, $\vec a=(a_1,\ldots,a_n)\in R^n$. We present some classes of resilient function $f:R^n\to R$ with the specified value of linear characteristic $C(f)$, where $C(f)=\max_{a\in R\setminus \{0\}}\max_{g\in A_n(R)}\left|\sum\limits_{x_1,\ldots,x_n\in R}{\chi(af(\vec x)-g(\vec x))} \right|$ and $\chi$ is the canonical additive character of the ring $R$. In the paper, we describe the function $f$ using a branching construction of the given functions $f_1,\ldots,f_{r_{q^l}}$ in $n-1$ variables. We prove that in the case when the functions $f_1,\ldots,f_{r_{q^l}}$ are $k$-resilient, the resulting function $f$ is also $k$-resilient. Moreover, $C(f)\le C(f_{r_1})+\ldots+C(f_{r_{q^l}})$. We also describe the function $f(\vec x,\vec y)=\langle \phi(\vec x),\vec y\rangle+h(\vec x)$, where $n=2k$, $\phi:R^k\to R^{k}$, $h:R^k\to R$, $\vec x$, $\vec y\in R^k$. It is known that in the case $\phi(R^k)\subset (R^*)^k$ ($R^*$ is the group of units in the ring $R$) the function $f$ is $(k-1)$-resilient. We prove that in the case $|\phi^{-1}(\vec c)|\le t$ for all $\vec c\in R^k$ the enequality $C(f)\le q^{k(2l-1)}$ is true.

Détail

Keywords: discrete functions, resilient functions, Galois rings, linear characteristic of functions.

Bibliographie

[1] Pankov K. N., “Otsenki moschnosti klassov otobrazhenii, primenyaemykh v protokolakh kvantovogo raspredeleniya klyuchei”, Naukoemkie tekhnologii v kosmicheskikh issledovaniyakh Zemli, 2022, no. 4, 4–18

[2] Camion P., Carlet C., Charpin P., and Sendrier N., “On correlation-immune functions”, LNCS, 576, 1992, 86–100 | MR | Zbl

[3] Dobbertin H., “Construction of bent functions and balanced boolean functions with high nonlinearity”, LNCS, 1008, 1995, 61–74 | Zbl

[4] Xiao G-Z. and Massey J. L., “A spectral characterization on correlation-immune combining functions”, IEEE Trans. Inform. Theory, 1988, no. 3, 569–571 | DOI | MR | Zbl

[5] Kamlovskii O. V., Pankov K. N., “Klassy sbalansirovannykh funktsii nad konechnymi polyami, obladayuschikh malym znacheniem lineinoi kharakteristiki”, Problemy peredachi informatsii, 2022, no. 4, 103–117 | MR

[6] Carlet C., “More correlation-immune and resilient functions over Galois fields and Galois rings”, LNCS, 1233, 1997, 422–433 | MR

[7] Camion P. and Canteaut A., “Correlation-immune and resilient function over finite alphabets and their applications in cryptography”, Des. Codes Cryptogr., 16 (1999), 121–149 | DOI | MR | Zbl

[8] Bugrov A. D., “Kusochno-affinnye podstanovki konechnykh polei”, Prikladnaya diskretnaya matematika, 2015, no. 4(30), 5–23

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

[10] Kuzmin A. S., Markov V. T., Nechaev A. A. i dr., “Bent-funktsii i giperbent-funktsii nad polem iz $2^l$ elementov”, Problemy peredachi informatsii, 2008, no. 1, 15–37 | Zbl

[11] Golomb S. W. and Gong G., Signal Design for Good Correlation, Cambridge University Press, Cambridge, 2005 | MR | Zbl

[12] Nechaev A. A., “Kod Kerdoka v tsiklicheskoi forme”, Diskretnaya matematika, 1989, no. 4, 123–139 | Zbl

[13] Nechaev A. A., “Tsiklovye tipy lineinykh podstanovok nad konechnymi kommutativnymi koltsami”, Matematicheskii sbornik, 1993, no. 3, 21–56 | Zbl

[14] Lidl R., Niderraiter G., Konechnye polya, Mir, M., 1988

[15] Kamlovskii O. V., “Chastotnye kharakteristiki lineinykh rekurrentnykh posledovatelnostei nad koltsami Galua”, Matematicheskii sbornik, 2009, no. 4, 31–52 | DOI | MR | Zbl

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

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

[18] McFarland R. L., “A family of noncyclic difference sets”, J. Combin. Theory. Ser. A, 15 (1973), 1–10 | DOI | MR | Zbl

[19] Tokareva N. N., “Obobscheniya bent-funktsii. Obzor rabot”, Diskretnyi analiz i issledovanie operatsii, 2010, no. 1, 34–64 | Zbl