Chromos, Boolean functions and avalanche characteristics.

摘要

This thesis is concerned with three big problems spread out in the three chapters.;The first chapter begins with a brief discussion of the famous Kronecker's Theorem from Diophantine Approximations. Then we study a close problem to which Kronecker's Theorem can be applied, namely the problem of the reflecting ray solved by Konig and Szucs: a perfectly mobile particle moves inside a fixed unit cube ;A related problem is the problem studied by I. J. Schoenberg: find the largest n-dimensional open cube with the property that a cubical shell contains the entire path of some particle motion, which moves like a billiard ball. In order to study this problem, Schoenberg defined a class of combinatorial objects called n-chromos on which we shall devote the most part of this chapter. We construct explicitly four classes of n-chromos and attack some conjectures proposed by Th. Dienst. We close the first chapter by exhibiting the state of art regarding the interesting and rather difficult view-obstruction problems.;Chapter 2 presents a brief but rather comprehensive review of Boolean functions and avalanche characteristics. We define the concept of Strict Avalanche Criterion (SAC) introduced by Webster and Tavares at Crypto' 85: a function satisfies the SAC if complementing a single bit results in changing the output bit with probability exactly one half. The SAC property is used to construct good S-boxes in DES-like block cipher algorithms. We prove some conjectures proposed by Cusick in an Information Processing Letters (1996) published paper, concerning the number and construction of SAC functions.;In the last chapter we study the notion of perfect nonlinearity as introduced by Meier and Staffelbach at Eurocrypt' 89 in a cryptographic context. It turns out that this concept is equivalent to the bent property discovered by Rothaus in 1965. Bent functions have practical applications in spread spectrum communications, in cryptography and in coding theory. We define a few known classes of bent functions belonging to Maiorana-McFarland (MM class) and Dillon. We also study the extended MM class (under affine transformations). We use these constructions to define explicitly a large class of Boolean balanced functions of high nonlinearity.