Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports]
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2014, Volume 11, Pages 229–245 (Mi semr484)  

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

Discrete mathematics and mathematical cybernetics

Generalized proper matrices and constructing of $m$-resilient Boolean functions with maximal nonlinearity for expanded range of parameters

Y. V. Tarannikov

Mech. & Math. Department, Lomonosov Moscow State University, 119992 Moscow, Russia
Full-text PDF (585 kB) Citations (4)
References:
Abstract: Nonlinearity and resiliency are well known as some of the most important cryptographic parameters of Boolean functions, it is actual the problem of the constructing of functions that have high non-linearity and resiliency simultaneously. In 2000 three groups of authors obtained independently the upper bound $2^{n-1}-2^{m+1}$ for the nonlinearity of an $m$-resilient function of $n$ variables. It was shown that if this bound is achieved then $(n-3)/2\le m\le n-2$. Simultaneously in 2000 Tarannikov constructed functions that achieve this bound for $(2n-7)/3\le m\le n-2$. In 2001 Tarannikov constructed such functions for $0.6n-1\le m$ introducing for this aim so called proper matrices; later in 2001 Fedorova and Tarannikov constructed by means of proper matrices the functions that achieve the bound $2^{n-1}-2^{m+1}$ for $m\ge cn(1+o(1))$ where $c=1/\log_2(\sqrt{5}+1)=0.5902...$ but proved simultaneously that by means of proper matrices it is impossible to improve this result. During the period since 2001 it was not any further progress in the problem on the achievability of the bound $2^{n-1}-2^{m+1}$ in spite of this problem was well known and actual except the constructing in 2006–2007 by three groups of authors by means of a computer search concrete functions for $n=9$, $m=3$. In this paper we find the new approach that uses the generalization of the concept of proper matrices. We formulate combinatorial problems solutions of which allow to construct generalized proper matrices with parameters impossible for old proper matrices. As a result we obtain the constructions of $m$-resilient functions of $n$ variables with maximal nonlinearity for $m\ge cn(1+o(1))$ where $c=0.5789...$, and also we demonstrate how further advance in combinatorial problems follows an additional decrease of the constant $c$.
Keywords: Boolean functions, symmetric-key cryptography, nonlinearity, resiliency, maximal possible nonlinearity, bounds, plateaued functions, constructions, implementation complexity.
Received January 7, 2014, published March 24, 2014
Document Type: Article
UDC: 519.719.2
MSC: 94A60
Language: English
Citation: Y. V. Tarannikov, “Generalized proper matrices and constructing of $m$-resilient Boolean functions with maximal nonlinearity for expanded range of parameters”, Sib. Èlektron. Mat. Izv., 11 (2014), 229–245
Citation in format AMSBIB
\Bibitem{Tar14}
\by Y.~V.~Tarannikov
\paper Generalized proper matrices and constructing of $m$-resilient Boolean functions with maximal nonlinearity for expanded range of parameters
\jour Sib. \`Elektron. Mat. Izv.
\yr 2014
\vol 11
\pages 229--245
\mathnet{http://mi.mathnet.ru/semr484}
Linking options:
  • https://www.mathnet.ru/eng/semr484
  • https://www.mathnet.ru/eng/semr/v11/p229
  • This publication is cited in the following 4 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024