La cryptologie est une des disciplines des mathématiques, elle est composée de deux sous-ensembles: la cryptographie et la cryptanalyse. Tandis que la cryptographie s'intéresse aux algorithmes permettant de modifier une information afin de la rendre inintelligible sans la connaissance d'un secret, la seconde s'intéresse aux méthodes mathématiques permettant de recouvrer l'information originale à partir de la seule connaissance de l'élément chiffré.La cryptographie se subdivise elle-même en deux sous-ensembles: la cryptographie symétrique et la cryptographie asymétrique. La première utilise une clef identique pour les opérations de chiffrement et de déchiffrement, tandis que la deuxième utilise une clef pour le chiffrement et une autre clef, différente de la précédente, pour le déchiffrement. Enfin, la cryptographie symétrique travaille soit sur des blocs d'information soit sur des flux continus d'information. Ce sont les algorithmes de chiffrement par blocs qui nous intéressent ici.L'objectif de la cryptanalyse est de retrouver l'information initiale sans connaissance de la clef de chiffrement et ceci dans un temps plus court que l'attaque par force brute. Il existe de nombreuses méthodes de cryptanalyse comme la cryptanalyse fréquentielle, la cryptanalyse différentielle, la cryptanalyse intégrale, la cryptanalyse linéaire...Beaucoup de ces méthodes sont maintenues en échec par les algorithmes de chiffrement modernes. En effet, dans un jeu de la lance et du bouclier, les cryptographes développent des algorithmes de chiffrement de plus en plus efficaces pour protéger l'information chiffrée d'une attaque par cryptanalyse. C'est le cas notamment de l'Advanced Encryption Standard (AES). Cet algorithme de chiffrement par blocs a été conçu par Joan Daemen et Vincent Rijmen et transformé en standard par le National Institute of Standards and Technology (NIST) en 2001. Afin de contrer les méthodes de cryptanalyse usuelles les concepteurs de l'AES lui ont donné une forte structure algébrique.Ce choix élimine brillamment toute possibilité d'attaque statistique, cependant, de récents travaux tendent à montrer, que ce qui est censé faire la robustesse de l'AES, pourrait se révéler être son point faible. En effet, selon ces études, cryptanalyser l'AES se ``résume'' à résoudre un système d'équations quadratiques symbolisant la structure du chiffrement de l'AES. Malheureusement, la taille du système d'équations obtenu et le manque d'algorithmes de résolution efficaces font qu'il est impossible, à l'heure actuelle, de résoudre de tels systèmes dans un temps raisonnable.L'enjeu de cette thèse est, à partir de la structure algébrique de l'AES, de décrire son algorithme de chiffrement et de déchiffrement sous la forme d'un nouveau système d'équations booléennes. Puis, en s'appuyant sur une représentation spécifique de ces équations, d'en réaliser une analyse combinatoire afin d'y détecter d'éventuels biais statistiques. / Cryptology is one of the mathematical fields, it is composed of two subsets: cryptography and cryptanalysis. While cryptography focuses on algorithms to modify an information by making it unintelligible without knowledge of a secret, the second focuses on mathematical methods to recover the original information from the only knowledge of the encrypted element.Cryptography itself is subdivided into two subsets: symmetric cryptography and asymmetric cryptography. The first uses the same key for encryption and decryption operations, while the second uses one key for encryption and another key, different from the previous one, for decryption. Finally, symmetric cryptography is working either on blocks of information either on continuous flow of information. These are algorithms block cipher that interests us here.The aim of cryptanalysis is to recover the original information without knowing the encryption key and this, into a shorter time than the brute-force attack. There are many methods of cryptanalysis as frequency cryptanalysis, differential cryptanalysis, integral cryptanalysis, linear cryptanalysis...Many of these methods are defeated by modern encryption algorithms. Indeed, in a game of spear and shield, cryptographers develop encryption algorithms more efficient to protect the encrypted information from an attack by cryptanalysis. This is the case of the Advanced Encryption Standard (AES). This block cipher algorithm was designed by Joan Daemen and Vincent Rijmen and transformed into standard by the National Institute of Standards and Technology (NIST) in 2001. To counter the usual methods of cryptanalysis of AES designers have given it a strong algebraic structure.This choice eliminates brilliantly any possibility of statistical attack, however, recent work suggests that what is supposed to be the strength of the AES, could prove to be his weak point. According to these studies, the AES cryptanalysis comes down to ``solve'' a quadratic equations symbolizing the structure of the AES encryption. Unfortunately, the size of the system of equations obtained and the lack of efficient resolution algorithms make it impossible, at this time, to solve such systems in a reasonable time.The challenge of this thesis is, from the algebraic structure of the AES, to describe its encryption and decryption processes in the form of a new Boolean equations system. Then, based on a specific representation of these equations, to achieve a combinatorial analysis to detect potential statistical biases.

Title: A construction of minimum DNF representations of 2-interval functions Author: Jakub Dubovský Department: Dep. of Theoretical Computer Science and Mathematical Logic Supervisor: doc.RNDr.Ondřej Čepek, Ph.D. Abstract: The thesis is devoted to interval boolean functions. It is focused on construction of their representation by disjunctive normal forms with minimum number of terms. Summary of known results in this field for 1-interval functions is presented. It shows that method used to prove those results cannot be in general used for two or more interval functions. It tries to extend those results to 2-interval functions. An optimization algorithm for special subclass of them is constructed. Exact error estimation for approximation algorithm is proven. A command line software for experimentation with interval function is part of the thesis. Keywords: boolean function, interval function, representation construction, ap- proximation 1

In this thesis, the geometric margin is used for the first time as the robustness indicator of an uncoupled cellular neural network implementing a given Boolean function. First, robust template design for uncoupled cellular neural networks implementing linearly separable Boolean functions by support vector machines is proposed. A fast sequential minimal optimization algorithm is presented to find maximal margin classifiers, which in turn determine the robust templates. Some general properties of robust templates are investigated. An improved CFC algorithm implementing an arbitrarily given Boolean function is proposed. Two illustrative examples are provided to demonstrate the validity of the proposed method.

We introduce a steepest-descent-like search algorithm for the design of Boolean functions, yielding multiple desirable cryptographic properties in their Walsh and autocorrelation spectra together. The algorithm finds some Boolean functions on 9, 10, 11, 13 variables with very good cryptographic properties unattained in the literature. More specifically, we have discovered 9-variable rotation symmetric Boolean functions (RSBFs) having nonlinearity of 241, which exceeds the bent concatenation bound and has remained as an open question in the literature for almost three decades. We have then shown that there is no RSBF having nonlinearity greater than 241, and that there are 8x189 many RSBFs having nonlinearity of 241, such that, among them there are only two that are different up to the affine equivalence. We also propose a generalization to RSBFs and dihedral symmetric Boolean functions (DSBFs), which improves the nonlinearity result of 9-variable Boolean functions to 242. Further, we classify all possible permutations (362, 880) on the input variables of 9-variable Boolean functions and find that there are only 30 classes, which are different with respect to the linear equivalence of invariant Boolean functions under some permutations. Some of these classes and their subsets yield new 9-variable Boolean functions having the nonlinearity of 242 with different autocorrelation spectra from those of the Boolean functions found in generalized RSBF and DSBF classes. Moreover, we have attained 13-variable balanced Boolean functions having nonlinearity of 4036 which is greater than the bent concatenation bound of 4032, and improves the recent result of 4034.

In this thesis, we work on the upper bound for nonlinearity of t-resilient Boolean functions given by Sarkar and Maitra, which is based on divisibility properties of spectral weights of resilient functions and study construction methods that achieve the upper bound. One of the construction methods, introduced by Maity and Johansson, starts with a bent function and complements some values of its truth table corresponding to a previously chosen set of inputs, S, which satisfies three criteria. In this thesis, we show that a fourth criterion is needed for t-resiliency of the resulting function, and prove that three criteria of Maity and Johansson do not guarantee resiliency. We also work on other constructions, one by Sarkar and Maitra, which uses a Maiorana-McFarland like technique to satisfy the upper bound and the other by Tarannikov, which satisfies the nonlinearity bound using a technique with low computational complexity. However, these methods have tendency to maximize the order of resiliency for a given number of variables, therefore one cannot construct functions for all possible resiliency values given the number of variables, using this method. We further go into details and compute the auto-correlation functions of the constructed Boolean functions to find the absolute indicator and sum-of-squared-errors for each of them. We also provide a comparison of Boolean functions constructed by other techniques given in the literature, together with the ones studied in this thesis.

Algoritmos exatos para fatoração estão limitados a funções Booleanas read-once, onde cada variável aparece uma vez na equação final. No entanto, estes algoritmos apresentam duas restrições principais: (1) eles não consideram funções Booleanas incompletamente especificadas, e (2) eles não são adequados para as funções binate. Para superar o primeiro inconveniente, é proposto um algoritmo que encontra equações read-once para funções Booleanas incompletamente especificadas, sempre que possível, é proposto. Com respeito à segunda limitação, é apresentada uma transformação de domínio que divide variáveis binate existentes em duas variáveis unate independentes. Tal transformação de domínio conduz a funções Booleanas incompletamente especificadas, que podem ser eficientemente fatoradas mediante a aplicação do algoritmo proposto. A combinação das duas contribuições dá resultados ótimos para uma nova classe de funções Booleanas chamada read-polarity-once, onde cada polaridade (positiva ou negativa) de uma variável aparece no máximo uma vez na forma fatorada da expressão Booleana. Resultados experimentais sobre circuitos ISCAS'85 mostrou que funções read-polarity-once são significativamente mais frequentes em circuitos reais quando comparado com a classe de funções read-once, a qual muitos trabalhos já foram dedicados na literatura. / Efficient exact factoring algorithms are limited to read-once functions, in which each variable appears once in the final Boolean equation. However, those algorithms present two main constraints: (1) they do not consider incompletely specified Boolean functions; and (2) they are not suitable for binate functions. To overcome the first drawback, it is proposed an algorithm that finds read-once formulas for incompletely specified Boolean functions, whenever possible. With respect to the second limitation, a domain transformation that splits existing binate variables into two independent unate variables is presented. Such domain transformation leads to incompletely specified Boolean functions, which can be efficiently factored by applying the proposed algorithm. The combination of both contributions gives optimal results for a novel broader class of Boolean functions named as read-polarity-once functions, where each polarity (positive or negative) of a variable appears at most once in the factored form. Experimental results over ISCAS'85 benchmark circuits have shown that read-polarityonce functions are significantly more frequent than read-once functions, for which many works have already been devoted in the literature.

Algoritmos exatos para fatoração estão limitados a funções Booleanas read-once, onde cada variável aparece uma vez na equação final. No entanto, estes algoritmos apresentam duas restrições principais: (1) eles não consideram funções Booleanas incompletamente especificadas, e (2) eles não são adequados para as funções binate. Para superar o primeiro inconveniente, é proposto um algoritmo que encontra equações read-once para funções Booleanas incompletamente especificadas, sempre que possível, é proposto. Com respeito à segunda limitação, é apresentada uma transformação de domínio que divide variáveis binate existentes em duas variáveis unate independentes. Tal transformação de domínio conduz a funções Booleanas incompletamente especificadas, que podem ser eficientemente fatoradas mediante a aplicação do algoritmo proposto. A combinação das duas contribuições dá resultados ótimos para uma nova classe de funções Booleanas chamada read-polarity-once, onde cada polaridade (positiva ou negativa) de uma variável aparece no máximo uma vez na forma fatorada da expressão Booleana. Resultados experimentais sobre circuitos ISCAS'85 mostrou que funções read-polarity-once são significativamente mais frequentes em circuitos reais quando comparado com a classe de funções read-once, a qual muitos trabalhos já foram dedicados na literatura. / Efficient exact factoring algorithms are limited to read-once functions, in which each variable appears once in the final Boolean equation. However, those algorithms present two main constraints: (1) they do not consider incompletely specified Boolean functions; and (2) they are not suitable for binate functions. To overcome the first drawback, it is proposed an algorithm that finds read-once formulas for incompletely specified Boolean functions, whenever possible. With respect to the second limitation, a domain transformation that splits existing binate variables into two independent unate variables is presented. Such domain transformation leads to incompletely specified Boolean functions, which can be efficiently factored by applying the proposed algorithm. The combination of both contributions gives optimal results for a novel broader class of Boolean functions named as read-polarity-once functions, where each polarity (positive or negative) of a variable appears at most once in the factored form. Experimental results over ISCAS'85 benchmark circuits have shown that read-polarityonce functions are significantly more frequent than read-once functions, for which many works have already been devoted in the literature.

Algoritmos exatos para fatoração estão limitados a funções Booleanas read-once, onde cada variável aparece uma vez na equação final. No entanto, estes algoritmos apresentam duas restrições principais: (1) eles não consideram funções Booleanas incompletamente especificadas, e (2) eles não são adequados para as funções binate. Para superar o primeiro inconveniente, é proposto um algoritmo que encontra equações read-once para funções Booleanas incompletamente especificadas, sempre que possível, é proposto. Com respeito à segunda limitação, é apresentada uma transformação de domínio que divide variáveis binate existentes em duas variáveis unate independentes. Tal transformação de domínio conduz a funções Booleanas incompletamente especificadas, que podem ser eficientemente fatoradas mediante a aplicação do algoritmo proposto. A combinação das duas contribuições dá resultados ótimos para uma nova classe de funções Booleanas chamada read-polarity-once, onde cada polaridade (positiva ou negativa) de uma variável aparece no máximo uma vez na forma fatorada da expressão Booleana. Resultados experimentais sobre circuitos ISCAS'85 mostrou que funções read-polarity-once são significativamente mais frequentes em circuitos reais quando comparado com a classe de funções read-once, a qual muitos trabalhos já foram dedicados na literatura. / Efficient exact factoring algorithms are limited to read-once functions, in which each variable appears once in the final Boolean equation. However, those algorithms present two main constraints: (1) they do not consider incompletely specified Boolean functions; and (2) they are not suitable for binate functions. To overcome the first drawback, it is proposed an algorithm that finds read-once formulas for incompletely specified Boolean functions, whenever possible. With respect to the second limitation, a domain transformation that splits existing binate variables into two independent unate variables is presented. Such domain transformation leads to incompletely specified Boolean functions, which can be efficiently factored by applying the proposed algorithm. The combination of both contributions gives optimal results for a novel broader class of Boolean functions named as read-polarity-once functions, where each polarity (positive or negative) of a variable appears at most once in the factored form. Experimental results over ISCAS'85 benchmark circuits have shown that read-polarityonce functions are significantly more frequent than read-once functions, for which many works have already been devoted in the literature.

The aim of the research presented in this thesis is to investigate the use of various optimisation heuristics in the fields of automated cryptanalysis and automated cryptographic function generation. These techniques were found to provide a successful method of automated cryptanalysis of a variety of the classical ciphers. Also, they were found to enhance existing fast correlation attacks on certain stream ciphers. A previously proposed attack of the knapsack cipher is shown to be flawed due to the absence of a suitable solution evaluation mechanism. Finally, a new approach for finding highly nonlinear Boolean functions is introduced.

The growing interest in the Internet of Things (IoT) has led to predictions claiming that by 2020 we can expect to be surrounded by 50 billion Internet connected devices. With more entry points to a network, adversaries can potentially use IoT devices as a stepping stone for attacking other devices connected to the network or the network itself. Information security relies on cryptographic primitives that, in turn, depend on secret keys. Furthermore, the issue of Intellectual property (IP) theft in the field of Integrated circuit (IC) design can be tackled with the help of unique device identifiers. Physical unclonable functions (PUFs) provide a tamper-resilient solution for secure key storage and fingerprinting hardware. PUFs use intrinsic manufacturing differences of ICs to assign unique identities to hardware. Arbiter PUFs utilise the differences in delays of identically designed paths, giving rise to an unpredictable response unique to a given IC. This thesis explores the statistical properties of Boolean functions induced by arbiter PUFs. In particular, this empirical study looks into the distribution of induced functions. The data gathered shows that only 3% of all possible 4-variable functions can be induced by a single 4 stage arbiter PUF. Furthermore, some individual functions are more than 5 times more likely than others. Hence, the distribution is non-uniform. We also evaluate alternate PUF designs, improving the coverage vastly, resulting in one particular implementation inducing all 65,536 4-variable functions. We hypothesise the need for n XORed PUFs to induce all 22n possible n-variable Boolean functions.