Advanced

On Boolean Functions in Symmetric-Key Ciphers

Pasalic, Enes LU (2003)
Abstract
This thesis discusses new results on the design and the existence of cryptographically strong Boolean functions used in the design of stream and block ciphers. By interlinking theoretical results and computer search some open problems have been solved, that is, we have shown the existence of previously unknown classes of functions. Furthermore, several general construction methods are exhibited and in particular a new method that extends a theoretical framework for recursive construction of cryptographically strong resilient functions is proposed. The functions obtained through this method are either optimized or suboptimized depending on the properties of input function. An important theoretical contribution discussed in the thesis is a... (More)
This thesis discusses new results on the design and the existence of cryptographically strong Boolean functions used in the design of stream and block ciphers. By interlinking theoretical results and computer search some open problems have been solved, that is, we have shown the existence of previously unknown classes of functions. Furthermore, several general construction methods are exhibited and in particular a new method that extends a theoretical framework for recursive construction of cryptographically strong resilient functions is proposed. The functions obtained through this method are either optimized or suboptimized depending on the properties of input function. An important theoretical contribution discussed in the thesis is a general result regarding the degree optimization of 1-resilient functions. A construction of suboptimized functions is further discussed in a generalized manner, and several results in this direction are provided. The possibilities of using integer programming and a sophisticated computer search in finding Boolean functions with good cryptographic properties are also discussed. Some alternative construction methods based on the tools borrowed from projective geometry are proposed. For instance, the possibility of using certain objects in projective space, known as conics, in construction of Boolean functions beyond the bent concatenation bound is examined. Autocorrelation properties of Boolean functions, important in the design of block ciphers, are also investigated. A new upper bound on nonlinearity and a new divisibility result on the function's derivatives for a certain class of Boolean functions are established. Finally, two new constructions of highly nonlinear resilient vector output Boolean functions are proposed. This class of function is suitable in the design of stream ciphers which do not operate on a bit level. Actually, the nonlinearity achieved through these construction is the best known for almost all input instances. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Prof Carlet, Claude, Frankrike
organization
publishing date
type
Thesis
publication status
published
subject
keywords
autocorrelation properties, correlation attacks, nonlinearity, resiliency, Boolean function, Stream ciphers, block ciphers, Informatics, systems theory, Informatik, systemteori
pages
181 pages
publisher
Department of Information Technology, Lund Univeristy
defense location
E:1406, E-huset, LTH
defense date
2003-02-28 10:15
ISBN
91-7167-027-0
language
English
LU publication?
yes
id
8442bf52-d425-45c5-9cc5-ea8e3d09608d (old id 21032)
date added to LUP
2007-05-28 14:14:49
date last changed
2016-09-19 08:45:08
@phdthesis{8442bf52-d425-45c5-9cc5-ea8e3d09608d,
  abstract     = {This thesis discusses new results on the design and the existence of cryptographically strong Boolean functions used in the design of stream and block ciphers. By interlinking theoretical results and computer search some open problems have been solved, that is, we have shown the existence of previously unknown classes of functions. Furthermore, several general construction methods are exhibited and in particular a new method that extends a theoretical framework for recursive construction of cryptographically strong resilient functions is proposed. The functions obtained through this method are either optimized or suboptimized depending on the properties of input function. An important theoretical contribution discussed in the thesis is a general result regarding the degree optimization of 1-resilient functions. A construction of suboptimized functions is further discussed in a generalized manner, and several results in this direction are provided. The possibilities of using integer programming and a sophisticated computer search in finding Boolean functions with good cryptographic properties are also discussed. Some alternative construction methods based on the tools borrowed from projective geometry are proposed. For instance, the possibility of using certain objects in projective space, known as conics, in construction of Boolean functions beyond the bent concatenation bound is examined. Autocorrelation properties of Boolean functions, important in the design of block ciphers, are also investigated. A new upper bound on nonlinearity and a new divisibility result on the function's derivatives for a certain class of Boolean functions are established. Finally, two new constructions of highly nonlinear resilient vector output Boolean functions are proposed. This class of function is suitable in the design of stream ciphers which do not operate on a bit level. Actually, the nonlinearity achieved through these construction is the best known for almost all input instances.},
  author       = {Pasalic, Enes},
  isbn         = {91-7167-027-0},
  keyword      = {autocorrelation properties,correlation attacks,nonlinearity,resiliency,Boolean function,Stream ciphers,block ciphers,Informatics,systems theory,Informatik,systemteori},
  language     = {eng},
  pages        = {181},
  publisher    = {Department of Information Technology, Lund Univeristy},
  school       = {Lund University},
  title        = {On Boolean Functions in Symmetric-Key Ciphers},
  year         = {2003},
}