Highly Nonlinear Resilient Functions without Linear Structures

Jian LIU  Lusheng CHEN  Xuan GUANG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.6   pp.1405-1417
Publication Date: 2014/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1405
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Boolean function,  resiliency,  linear structure,  nonlinearity,  

Full Text: PDF>>
Buy this Article

In this paper, we provide several methods to construct nonlinear resilient functions with multiple good cryptographic properties, including high nonlinearity, high algebraic degree, and non-existence of linear structures. Firstly, we present an improvement on a known construction of resilient S-boxes such that the nonlinearity and the algebraic degree will become higher in some cases. Then a construction of highly nonlinear t-resilient Boolean functions without linear structures is given, whose algebraic degree achieves n-t-1, which is optimal for n-variable t-resilient Boolean functions. Furthermore, we construct a class of resilient S-boxes without linear structures, which possesses the highest nonlinearity and algebraic degree among all currently known constructions.