Divisibility properties on boolean functions using the numerical normal form

Download

index.pdf

Date

2004

Author

Göloğlu, Faruk

Metadata

Show full item record

Item Usage Stats

124
views

71
downloads

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̕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.

Subject Keywords

Algebra.

URI

http://etd.lib.metu.edu.tr/upload/2/12605549/index.pdf
https://hdl.handle.net/11511/14605

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Integrable KdV systems: Recursion operators of degree four Gurses, M; Karasu, Atalay (1999-01-25) The recursion operator and bi-Hamiltonian formulation of the Drinfeld-Sokolov system are given. (C) 1999 Elsevier Science B.V.
Minimal non-FC-groups and coprime automorphisms of quasi-simple groups Ersoy, Kıvanç; Kuzucuoğlu, Mahmut; Department of Mathematics (2004) A group G is called an FC-group if the conjugacy class of every element is finite. G is called a minimal non-FC-group if G is not an FC-group, but every proper subgroup of G is an FC-group. The first part of this thesis is on minimal non-FC-groups and their finitary permutational representations. Belyaev proved in 1998 that, every perfect locally finite minimal non-FC-group has non-trivial finitary permutational representation. In Chapter 3, we write the proof of Belyaev in detail. Recall that a group G is ...
Galois structure of modular forms of even weight Gurel, E. (Elsevier BV, 2009-10-01) We calculate the equivariant Euler characteristics of powers of the canonical sheaf on certain modular curves over Z which have a tame action of a finite abelian group. As a consequence, we obtain information on the Galois module structure of modular forms of even weight having Fourier coefficients in certain ideals of rings of cyclotomic algebraic integers. (c) 2009 Elsevier Inc. All rights reserved.
Kummer extensions of function fields with many rational places Gülmez Temur, Burcu; Özbudak, Ferruh; Department of Mathematics (2005) In this thesis, we give two simple and effective methods for constructing Kummer extensions of algebraic function fields over finite fields with many rational places. Some explicit examples are obtained after a practical search. We also study fibre products of Kummer extensions over a finite field and determine the exact number of rational places. We obtain explicit examples with many rational places by a practical search. We have a record (i.e the lower bound is improved) and a new entry for the table of v...
Value sets of Lattes maps over finite fields Küçüksakallı, Ömer (Elsevier BV, 2014-10-01) We give an alternative computation of the value sets of Dickson polynomials over finite fields by using a singular cubic curve. Our method is not only simpler but also it can be generalized to the non-singular elliptic case. We determine the value sets of Lattes maps over finite fields which are rational functions induced by isogenies of elliptic curves with complex multiplication.

Citation Formats

F. Göloğlu, “Divisibility properties on boolean functions using the numerical normal form,” M.S. - Master of Science, Middle East Technical University, 2004.