Computing cryptographic properties of Boolean functions from the algebraic normal orm representation

Download

index.pdf

Date

2013

Author

Çalık, Çağdaş

Metadata

Show full item record

Item Usage Stats

289
views

123
downloads

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 coefficients 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 efficient 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.

Subject Keywords

Coding theory, Algebra, Boolean, Binary system (Mathematics)., Integer programming., Cryptography.

URI

http://etd.lib.metu.edu.tr/upload/12615762/index.pdf
https://hdl.handle.net/11511/22563

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

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...
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 ...
Using Criticalities as a Heuristic for Answer Set Programming SABUNCU, ORKUNT; Alpaslan, Ferda Nur; AKMAN, VAROL (2004-01-08) Answer Set Programming is a new paradigm based on logic programming. The main component of answer set programming is a system that finds the answer sets of logic programs. During the computation of an answer set, systems are faced with choice points where they have to select a literal and assign it a truth value. Generally, systems utilize some heuristics to choose new literals at the choice points. The heuristic used is one of the key factors for the performance of the system. A new heuristic for answer s...
On nonlinearity and hamming weight preserving bijective mappings acting on boolean functions Sertkaya, İsa; Doğanaksoy, Ali; Department of Cryptography (2014) 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 a...
A visual interactive approach for scenario-based stochastic multi-objective problems and an application Balibek, E.; Köksalan, Mustafa Murat (2012-12-01) In many practical applications of stochastic programming, discretization of continuous random variables in the form of a scenario tree is required. In this paper, we deal with the randomness in scenario generation and present a visual interactive method for scenario-based stochastic multi-objective problems. The method relies on multi-variate statistical analysis of solutions obtained from a multi-objective stochastic problem to construct joint confidence regions for the objective function values. The decis...

Citation Formats

Ç. Çalık, “Computing cryptographic properties of Boolean functions from the algebraic normal orm representation,” Ph.D. - Doctoral Program, Middle East Technical University, 2013.