On nonlinearity and hamming weight preserving bijective mappings acting on boolean functions

Download
index.pdf
2014
Sertkaya, İsa
Show full item record
255
views
94
downloads
Boolean functions are widely studied in cryptography due to their key role and ap- plications in various cryptographic schemes. Particularly in order to make symmetric crypto-systems resistant against cryptanalytic attacks, Boolean functions are associ- ated some cryptographic design criteria. As a result of Shannon’s similarity of secrecy systems theory, cryptographic design criteria should be at least preserved under the action of basic transformations. Among these design criteria, Meier and Staffelbach analyzed behavior of the nonlinearity criteria under the action of bijective mappings defined on input values of the functions. Later, Preneel proved that nonlinearity still remains invariant under the action of affine equivalence mappings. Motivated by the previous studies, in his master thesis, the author showed the existence of new nonlin- earity preserving bijective mappings. In this thesis, we first give definition of the maximal group that can act on Boolean functions. This maximal group is the symmetric group of the vector space that cor- responds to the set comprised of the truth table of the Boolean functions. We give a representation, based on the coordinate functions’ algebraic normal form, for the ele- ments of this symmetric group and then we list its subgroups that we mainly focus on. Regarding these subgroups, our aim is to enumerate or classify these bijective map- pings with respect to preserving a cryptographic design criterion. After the necessary definitions and notions, we mainly investigate the nonlinearity preserving bijective mappings. Then we apply the procedures constructed on nonlinearity preservability to another cryptographic design criterion, namely the Hamming weight. From a the- oretical viewpoint, our basic result is that we show the existence of new families of bijective mappings that leaves nonlinearity (respectively, Hamming weight) invariant. Under the action of linear and affine bijective mappings we give the necessary and sufficient conditions to keep nonlinearity invariant. We explicitly construct an iso- morphism between the affine equivalency mappings subgroup and the automorphism group of the Sylvester Hadamard matrices and give the order of this automorphism group. Next we construct a family of non-affine nonlinearity preserving bijective map- pings explicitly. However, we also show that all of these explicitly constructed non- linearity preserving bijective mappings produce the same orbit structure as the affine equivalency mappings. On the other hand, we give the exact number of nonlinearity preserving bijective mappings for the functions with n ≤ 6 variables. Then, based on these cardinalities, we prove the existence of new non-affine nonlinearity preserving mappings, without constructing explicitly. We demonstrate some examples for these non-affine mappings. Following the results obtained for nonlinearity preserving bijective mappings, we ex- tend our study to the Hamming weight preserving bijective mappings. First we com- pletely solve the enumeration problem of Hamming weight preserving bijective mappings, and give the exact number of the Hamming weight preserving bijective map- pings for all Boolean functions. Afterwards, we study the classification problem and give partial results. Lechner proved that the Hamming weight property is preserved un- der the action of symmetric group of input vector space. We further prove that among the affine bijective mappings only these mappings preserve the Hamming weight. Finally, again based on the enumeration of the Hamming weight preserving bijective mappings we proved the existence of Hamming weight preserving non-affine bijective mappings.
Nonlinear theories., Boolean functions., Affine equivalence., Hadamard matrices., Mappings (Mathematics).
http://etd.lib.metu.edu.tr/upload/12617862/index.pdf
https://hdl.handle.net/11511/23817
Graduate School of Applied Mathematics, Thesis

Suggestions

On constructions and enumeration of bent and semi-bent functions
Koçak, Neşe; Doğanaksoy, Ali; Saygı, Zülfükar; Department of Cryptography (2015)
Bent and semi-bent functions play an important role in cryptography and coding theory. They are widely studied as parts of building blocks in symmetric key cryptosystems because they provide resistance to fast correlation attacks and linear cryptanalysis due to their high nonlinearity. Besides, they can possess other desirable cryptographic properties such as low autocorrelation, propagation criteria, resiliency and high algebraic degree. Therefore, parallel to the advances in cryptanalysis techniques, the ...
Analysis of boolean functions with respect to Walsh spectrum
Uyan, Erdener; Doğanaksoy, Ali; Department of Cryptography (2013)
Boolean functions appear in various scientific disciplines including coding theory, combinatorics, complexity theory, cryptography, graph theory, etc. In cryptography, the design and analysis of Boolean functions possessing a range of cryptographic characteristics has often been the focus of attention. A productive ground of research for most of these cryptographic characteristics is Walsh spectrum, one of the most common representations of a Boolean function. This thesis presents an analysis of Boolean fun...
Some characterizations of generalized s-plateaued functions
Çelik, Emircan; Özbudak, Ferruh; Department of Cryptography (2017)
Plateaued functions play important role in cryptography because of their various desirable cryptographic features. Due to this characteristics they have been widely studied in the literature. This studies include p-ary functions and some generalizations of the boolean functions. In this thesis, we present some of this important work and show that plateaued functions can be generalized much more general framework naturally. Characterizations of generalized plateaued functions using Walsh power moments are al...
On q-ary plateaued functions over F-q and their explicit characterizations
Mesnager, Sihem; Özbudak, Ferruh; Sinak, Ahmet; Cohen, Gerard (Elsevier BV, 2019-08-01)
Plateaued and bent functions play a significant role in cryptography, sequence theory, coding theory and combinatorics. In 1997, Coulter and Matthews redefined bent functions over any finite field F-q where q is a prime power, and established their properties. The objective of this work is to redefine the notion of plateaued functions over F-q, and to present several explicit characterizations of those functions. We first give, over F-q, the notion of q-ary plateaued functions, which relies on the concept o...
On the efficient implementation of RSA
Güner, Hatice Kübra; Cenk, Murat; Department of Cryptography (2015)
Modular exponentiation is an essential operation for many asymmetric key cryptosystems such as RSA in which encryption and decryption are based on modular exponentiation. Therefore, efficiency of the system is effected with running time of the modular exponentiation algorithm. At the same time, key sizes also influence the efficiency of the algorithm. Over the years key sizes had to be increased to provide security. To make RSA practical, one of usable choices is acceleration of the modular exponentiation a...
Citation Formats
İ. Sertkaya, “On nonlinearity and hamming weight preserving bijective mappings acting on boolean functions,” Ph.D. - Doctoral Program, Middle East Technical University, 2014.
METU IIS - Integrated Information Service open@metu.edu.tr