Boolean functions play an important role in the design and analysis of symmetric-key cryptosystems,
as well as having applications in other fields such as coding theory. Boolean functions
acting on large number of inputs introduces the problem of computing the cryptographic
properties. Traditional methods of computing these properties involve transformations which
require computation and memory resources exponential in the number of input variables. When
the number of inputs is large, Boolean functions are usually defined by the algebraic normal
form (ANF) representation. In this thesis, methods for computing the weight and nonlinearity
of Boolean functions from the ANF representation are investigated. The relation between the
ANF coecients and the weight of a Boolean function was introduced by Carlet and Guillot.
This expression allows the weight to be computed in $mathcal{O}(2^p)$ operations for a Boolean function
containing p monomials in its ANF. In this work, a more ecient algorithm for computing the
weight is proposed, which eliminates the unnecessary calculations in the weight expression. By
generalizing the weight expression, a formulation of the distances to the set of linear functions
is obtained. Using this formulation, the problem of computing the nonlinearity of a Boolean
function from its ANF is reduced to an associated binary integer programming problem. This
approach allows the computation of nonlinearity for Boolean functions with high number of
input variables and consisting of small number of monomials in a reasonable time.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12615759/index.pdf |
| Date | 01 February 2013 |
| Creators | Calik, Cagdas |
| Contributors | Doganaksoy, Ali |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | Ph.D. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.0016 seconds