Advanced

On propagation characteristics of resilient functions

Charpin, P and Pasalic, Enes LU (2003) 9th Annual International Workshop, SAC 2002 In Lecture Notes in Computer Science (Selected Areas in Cryptography. Revised Papers) 2595. p.175-195
Abstract
In this paper we derive several important results towards a better understanding of propagation characteristics of resilient Boolean functions. We first introduce a new upper bound on nonlinearity of a given resilient function depending on the propagation criterion. We later show that a large class of resilient functions admit a linear structure; more generally, we exhibit some divisibility properties concerning the Walsh-spectrum of the derivatives of any resilient function. We prove that, fixing the order of resiliency and the degree of propagation criterion, a high algebraic degree is a necessary condition for construction of functions with good autocorrelation properties. We conclude by a study of the main constructions of resilient... (More)
In this paper we derive several important results towards a better understanding of propagation characteristics of resilient Boolean functions. We first introduce a new upper bound on nonlinearity of a given resilient function depending on the propagation criterion. We later show that a large class of resilient functions admit a linear structure; more generally, we exhibit some divisibility properties concerning the Walsh-spectrum of the derivatives of any resilient function. We prove that, fixing the order of resiliency and the degree of propagation criterion, a high algebraic degree is a necessary condition for construction of functions with good autocorrelation properties. We conclude by a study of the main constructions of resilient functions. We notably show how to avoid linear structures when a linear concatenation is used and when the recursive construction introduced in [11] is chosen. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Boolean functions, linear space, resiliency, nonlinearity, propagation characteristics
in
Lecture Notes in Computer Science (Selected Areas in Cryptography. Revised Papers)
volume
2595
pages
175 - 195
publisher
Springer
conference name
9th Annual International Workshop, SAC 2002
external identifiers
  • wos:000182919400013
  • scopus:35248894976
ISSN
1611-3349
0302-9743
DOI
10.1007/3-540-36492-7_13
language
English
LU publication?
yes
id
5c4eeb9c-328a-462f-89ff-0068202aa9f9 (old id 309966)
date added to LUP
2007-08-28 08:48:53
date last changed
2018-01-07 05:31:18
@inproceedings{5c4eeb9c-328a-462f-89ff-0068202aa9f9,
  abstract     = {In this paper we derive several important results towards a better understanding of propagation characteristics of resilient Boolean functions. We first introduce a new upper bound on nonlinearity of a given resilient function depending on the propagation criterion. We later show that a large class of resilient functions admit a linear structure; more generally, we exhibit some divisibility properties concerning the Walsh-spectrum of the derivatives of any resilient function. We prove that, fixing the order of resiliency and the degree of propagation criterion, a high algebraic degree is a necessary condition for construction of functions with good autocorrelation properties. We conclude by a study of the main constructions of resilient functions. We notably show how to avoid linear structures when a linear concatenation is used and when the recursive construction introduced in [11] is chosen.},
  author       = {Charpin, P and Pasalic, Enes},
  booktitle    = {Lecture Notes in Computer Science (Selected Areas in Cryptography. Revised Papers)},
  issn         = {1611-3349},
  keyword      = {Boolean functions,linear space,resiliency,nonlinearity,propagation characteristics},
  language     = {eng},
  pages        = {175--195},
  publisher    = {Springer},
  title        = {On propagation characteristics of resilient functions},
  url          = {http://dx.doi.org/10.1007/3-540-36492-7_13},
  volume       = {2595},
  year         = {2003},
}