nach oben

Designs, Codes and Cryptography

Erschienen in:

19.05.2023

An asymptotic lower bound on the number of bent functions

verfasst von: V. N. Potapov, A. A. Taranenko, Yu. V. Tarannikov

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2024

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A Boolean function f on n variables is said to be a bent function if the absolute value of all its Walsh coefficients is \(2^{n/2}\). Our main result is a new asymptotic lower bound on the number of Boolean bent functions. It is based on a modification of the Maiorana–McFarland family of bent functions and recent progress in the estimation of the number of transversals in latin squares and hypercubes. By-products of our proofs are the asymptotics of the logarithm of the numbers of partitions of the Boolean hypercube into 2-dimensional affine and linear subspaces.

Vorheriger Artikel Densities of codes of various linearity degrees in translation-invariant metric spaces

Nächster Artikel Modified Patterson–Wiedemann construction

Agievich S.V.: On the representation of bent functions by bent rectangles. In: Probabilistic Methods in Discrete Mathematics, Proceedings of the Fifth International Petrozavodsk Conference, pp. 121–135, Utrecht, Boston (2002)

Agievich S.: Bent rectangles. In: Proceedings of the NATO advanced study institute on Boolean functions in cryptology and information security, NATO Science for Peace and Security Series D: Information and Communication Security, vol. 18, pp. 3–22, Amsterdam (2008).

Agievich S.V.: On the continuation to bent functions and upper bounds on their number. Prikl. Diskr. Mat. Suppl. 13, 18–21 (2020).

Baksova I.P., Tarannikov Y.V.: On a construction of bent functions. Surv. Appl. Ind. Math. 27(1), 64–66 (2020).

Baksova I.P., Tarannikov Y.V.: The bounds on the number of partitions of the space \( {F}_2^m\) into \(k\)-dimensional affine subspaces. Mosc. Univ. Math. Bull. 77, 131–135 (2022).CrossRef

Canfield E.R., Gao Z., Greenhill C., McKay B.D., Robinson R.W.: Asymptotic enumeration of correlation-immune Boolean functions. Cryptogr. Commun. 2(1), 111–126 (2010).MathSciNetCrossRef

Canteaut A., Charpin P.: Decomposing bent functions. IEEE Trans. Inf. Theory 49(8), 2004–2019 (2003).MathSciNetCrossRef

Carlet C.: Two new classes of bent functions. In: Helleseth T. (ed.) Advances in Cryptology–.EUROCRYPT’93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol. 765. Springer, Berlin (1994).

Carlet C., Klapper A.: Upper bounds on the number of resilient functions and of bent functions. In: Proceedings of the 23rd Symposium on Information Theory in the Benelux, Louvain-La-Neuve, Belgium (2002).

10.

Carlet C.: On the confusion and diffusion properties of Maiorana–McFarland’s and extended Maiorana-McFarland’s functions. In: Special Issue “Complexity Issues in Coding and Cryptography”, dedicated to Prof. H. Niederreiter on the occasion of his 60th birthday, pp. 182–204, J. of Complexity 20, (2004).

11.

Carlet C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2020).CrossRef

12.

Carlet C., Mesnager S.: Four decades of research on bent functions. Des. Codes Cryptogr. 78(1), 5–50 (2016).MathSciNetCrossRef

13.

Çeşmelioğlu A., Meidl W.: A construction of bent functions from plateaued functions. Des. Codes Cryptogr. 66(1–3), 231–242 (2013).MathSciNetCrossRef

14.

Çeşmelioğlu A., Meidl W., Pott A.: Generalized Maiorana–McFarland class and normality of \(p\)-ary bent functions. Finite Fields Appl. 24, 105–117 (2013).MathSciNetCrossRef

15.

Eberhard S.: More on additive triples of bijections. arxiv:1704.02407.

16.

Hodžić S., Pasalic E., Wei Y., Zhang F.: Designing plateaued Boolean functions in spectral domain and their classification. IEEE Trans. Inf. Theory 65(9), 5865–5879 (2019).MathSciNetCrossRef

17.

Khalyavin A.V., Lobanov M.S., Tarannikov Y.V.: On plateaued Boolean functions with the same spectrum support. Sib. Electron. Mat. Izv. 13, 1346–1368 (2016).MathSciNet

18.

Langevin P., Leander G.: Counting all bent functions in dimension eight 99270589265934370305785861242880. Des. Codes Cryptogr. 59(1–3), 193–205 (2011).MathSciNetCrossRef

19.

Luria Z.: New bounds on the number of \(n\)-queens configurations. arxiv:1705.05225.

20.

McFarland R.L.: A family of difference sets in non-cyclic groups. J. Comb. Theory Ser. A 15, 1–10 (1973).MathSciNetCrossRef

21.

Mesnager S.: Bent Functions. Fundamentals and Results. Springer, Cham (2016).CrossRef

22.

Potapov V.N.: A lower bound on the number of Boolean functions with median correlation immunity. In: Proceedings of XVI International Symposium “Problems of Redundancy in Information and Control Systems”, pp. 45–46. IEEE, Moscow, Russia (2019).

23.

Potapov V.N.: An Upper Bound on the Number of Bent Functions. In Proceedings of XVII International Symposium “Problems of Redundancy in Information and Control Systems”, pp. 95–96. IEEE, Moscow, Russia (2021).

24.

Taranenko A.A.: On the numbers of 1-factors and 1-factorizations of hypergraphs. Discrete Math. 340(4), 753–762 (2017).MathSciNetCrossRef

25.

Taranenko A.A.: Transversals, plexes, and multiplexes in iterated quasigroups. Electron. J. Comb. 25(4), 4.30 (2018).MathSciNetCrossRef

26.

Tarannikov Y.V.: On the values of the affine rank of the support of a spectrum of a plateaued function. Diskret. Mat. 18(3), 120–137 (2006).MathSciNet

27.

Tokareva N.: On the number of bent functions from iterative constructions: lower bounds and hypothesis. Adv. Math. Commun. 5(4), 609–621 (2011).MathSciNetCrossRef

28.

Tokareva N.: Bent Functions. Elsevier/Academic Press, Amsterdam (2015).CrossRef

Titel: An asymptotic lower bound on the number of bent functions
verfasst von: V. N. Potapov
A. A. Taranenko
Yu. V. Tarannikov
Publikationsdatum: 19.05.2023
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2024
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01239-z

Springer Professional

An asymptotic lower bound on the number of bent functions

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2024

Densities of codes of various linearity degrees in translation-invariant metric spaces

Constructing irreducible polynomials recursively with a reverse composition method

Quantum impossible differential attacks: applications to AES and SKINNY

New quantum codes from self-dual codes over

On subfield subcodes obtained from restricted evaluation codes

Introducing nega-Forrelation: quantum algorithms in analyzing nega-Hadamard and nega-crosscorrelation spectra

Premium Partner