General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

Diskr. Mat., 2006, Volume 18, Issue 1, Pages 9–29 (Mi dm29)  

This article is cited in 9 scientific papers (total in 9 papers)

Approximation of Boolean functions by monomial functions

A. S. Kuz'min, V. T. Markov, A. A. Nechaev, A. B. Shishkov

Abstract: Every Boolean function of $n$ variables is identified with a function $F\colon Q\to P$, where $Q=\mathit{GF}(2^n)$, $P=\mathit{GF}(2)$. A. Youssef and G. Gong showed that for $n=2\lambda$ there exist functions $F$ which have equally bad approximations not only by linear functions (that is, by functions $\operatorname{tr}(\mu x)$, where $\mu\in Q^*$ and $\operatorname{tr}\colon Q\to P$ is the trace function), but also by proper monomial functions (functions $\operatorname{tr}(\mu x^\delta)$, where $(\delta, 2^n-1)=1$). Such functions $F$ were called hyper-bent functions (HB functions, HBF), and for any $n=2\lambda$ a non-empty class of HBF having the property $F(0)=0$ was constructed. This class consists of the functions $F(x)=G(x^{2^\lambda-1})$ such that the equation $F(x)=1$ has exactly $(2^\lambda-1)2^{\lambda-1}$ solutions in $Q$. In the present paper, we give some essential restrictions on the parameters of an arbitrary HBF showing that the class of HBF is far less than that of bent functions. In particular, we show that any HBF is a bent function having the degree of nonlinearity $\lambda$, and for some $n$ (for instance, if $\lambda>2$ and $2^\lambda-1$ is prime, or $\lambda\in \{4,9,25,27\}$) the class of HBF is exhausted by the functions $F(x)=G(x^{2^\lambda-1})$ described by A. Youssef and G. Gong. For $n=4$, in addition to 10 HBF listed above there exist 18 more HBF with property $F(0)=0$. The question of whether there exist other hyper-bent functions for $n>4$ remains open.
This research was supported by the Russian Foundation for Basic Research, grants 05–01–01048, 05–01–01018, and the program of the President of the Russian Federation for support of the leading scientific schools, grants 1910.2003.1, 2358.2003.9.


Full text: PDF file (2155 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2006, 16:1, 7–28

Bibliographic databases:

UDC: 519.7
Received: 25.01.2006

Citation: A. S. Kuz'min, V. T. Markov, A. A. Nechaev, A. B. Shishkov, “Approximation of Boolean functions by monomial functions”, Diskr. Mat., 18:1 (2006), 9–29; Discrete Math. Appl., 16:1 (2006), 7–28

Citation in format AMSBIB
\by A.~S.~Kuz'min, V.~T.~Markov, A.~A.~Nechaev, A.~B.~Shishkov
\paper Approximation of Boolean functions by monomial functions
\jour Diskr. Mat.
\yr 2006
\vol 18
\issue 1
\pages 9--29
\jour Discrete Math. Appl.
\yr 2006
\vol 16
\issue 1
\pages 7--28

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. J. Appl. Industr. Math., 2:4 (2008), 566–584  mathnet  crossref  zmath
    2. N. N. Tokareva, “On Quadratic Approximations in Block Ciphers”, Problems Inform. Transmission, 44:3 (2008), 266–286  mathnet  crossref  mathscinet  zmath  isi
    3. Charpin P., Gong G., “Hyperbent functions, Kloosterman sums, and Dickson polynomials”, IEEE Trans. Inform. Theory, 54:9 (2008), 4230–4238  crossref  mathscinet  zmath  isi  elib  scopus
    4. A. S. Kuz'min, V. T. Markov, A. A. Nechaev, V. A. Shishkin, A. B. Shishkov, “Bent and Hyper-bent Functions over a Field of $2^l$ Elements”, Problems Inform. Transmission, 44:1 (2008), 12–33  mathnet  crossref  mathscinet  zmath  isi
    5. A. V. Ivanov, “Blizost k klassu monomialnykh approksimatsii privedennogo predstavleniya bulevoi funktsii v zavisimosti ot vybora bazisa, v kotorom ono zadano”, PDM, 2009, prilozhenie № 1, 7–9  mathnet
    6. N. N. Tokareva, “Generalizations of bent functions”, J. Appl. Industr. Math., 5:1 (2011), 110–129  mathnet  crossref  mathscinet  zmath
    7. A. V. Ivanov, V. N. Romanov, “Postroenie klassov bulevykh funktsii s zadannymi kriptograficheskimi svoistvami na osnove koordinatnykh funktsii stepennykh preobrazovanii konechnykh polei”, PDM, 2010, prilozhenie № 3, 10–11  mathnet
    8. A. V. Ivanov, “Nezamknutost klassa giper-bent-funktsii otnositelno deistviya polnoi lineinoi gruppy”, Matem. vopr. kriptogr., 3:2 (2012), 5–26  mathnet  crossref
    9. A. S. Kuzmin, V. I. Nozdrunov, “Vzaimosvyaz koeffitsientov polinoma nad polem i vesa bulevoi funktsii”, PDM, 2014, no. 4(26), 28–46  mathnet
  • Дискретная математика
    Number of views:
    This page:917
    Full text:373
    First page:3

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020