A Boolean function can be represented in several different forms. These different
representation have advantages and disadvantages of their own. The Algebraic Normal
Form, truth table, and Walsh spectrum representations are widely studied in
literature. In 1999, Claude Carlet and Phillippe Guillot introduced the Numerical
Normal Form. NumericalNormal Form(NNF) of a Boolean function is similar to Algebraic
Normal Form, with integer coefficients instead of coefficients from the two
element field. Using NNF representation, just like the Walsh spectrum, characterization
of several cryptographically important functions, such as resilient and bent
functions, is possible. In 2002, Carlet had shown several divisibility results concerning
resilient and correlation-immune functions using NNF. With these divisibility
results, Carlet is able to give bounds concerning nonlinearity of resilient and correlation
immune functions.
In this thesis, following Carlet and Guillot, we introduce the Numerical Normal
Form and derive the pairwise relations between the mentioned representations.
Characterization of Boolean, resilient and bent functions using NNF is also given.
We then review the divisibility results of Carlet, which will be linked to some results
on the nonlinearity of resilient and correlation immune functions.
We show the Mö / bius inversion properties of NNF of a Boolean function, using
Gian-Carlo Rota&rsquo / s work as a guide. Finally, using a lot of the mentioned results, we prove a necessary condition on theWalsh spectrum of Boolean functions with given
degree.
Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/2/12605549/index.pdf |
Date | 01 September 2004 |
Creators | Gologlu, Faruk |
Contributors | Yucel, Melek D. |
Publisher | METU |
Source Sets | Middle East Technical Univ. |
Language | English |
Detected Language | English |
Type | M.S. Thesis |
Format | text/pdf |
Rights | To liberate the content for public access |
Page generated in 0.0014 seconds