CryptoDB
Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity
Authors: |
- Sihem Mesnager
|
Download: |
- URL: http://eprint.iacr.org/2007/117
- Search ePrint
- Search Google
|
Abstract: |
The recent algebraic attacks have received a lot of attention in
cryptographic literature. The algebraic immunity of a Boolean
function quantifies its resistance to the standard algebraic attacks
of the pseudo-random generators using it as a nonlinear filtering or
combining function. Very few results have been found concerning its
relation with the other cryptographic parameters or with the $r$-th
order nonlinearity. As recalled by Carlet at Crypto'06, many papers
have illustrated the importance of the $r$th-order nonlinearity
profile (which includes the first-order nonlinearity). The role of
this parameter relatively to the currently known attacks has been
also shown for block ciphers. Recently, two lower bounds involving
the algebraic immunity on the $r$th-order nonlinearity have been
shown by Carlet et \emph{al}. None of them improves upon the other
one in all situations. In this paper, we prove a new lower bound on
the $r$th-order nonlinearity profile of Boolean functions, given
their algebraic immunity, that improves significantly upon one of
these lower bounds for all orders and upon the other one for low
orders. |
BibTeX
@misc{eprint-2007-13399,
title={Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity},
booktitle={IACR Eprint archive},
keywords={foundations / stream cipher, block cipher, algebraic attack, Boolean function, algebraic immunity, algebraic degree, higher order nonlinearity, annihilator},
url={http://eprint.iacr.org/2007/117},
note={ hachai@math.jussieu.fr 13728 received 30 Mar 2007, last revised 3 Aug 2007},
author={Sihem Mesnager},
year=2007
}