Abstract: Perfect nonlinear functions from a finite group $G$ to another one $H$ are those functions $f: G \rightarrow H$ such that for all nonzero $\alpha \in G$, the derivative $d_{\alpha}f: x \mapsto f(\alpha x) f(x)^{-1}$ is balanced. In the case where both $G$ and $H$ are Abelian groups, $f: G \rightarrow H$ is perfect nonlinear if and only if $f$ is bent i.e for all nonprincipal character $\chi$ of $H$, the (discrete) Fourier transform of $\chi \circ f$ has a constant magnitude equals to $|G|$. In this paper, using the theory of linear representations, we exhibit similar bentness-like characterizations in the cases where $G$ and/or $H$ are (finite) non Abelian groups. Thus we extend the concept of bent functions to the framework of non Abelian groups.

Abstract: The two operations, deletion and contraction of an edge, on multigraphs directly lead to the Tutte polynomial which satisfies a universal problem. As observed by Brylawski in terms of order relations, these operations may be interpreted as a particular instance of a general theory which involves universal invariants like the Tutte polynomial, and a universal group, called the Tutte-Grothendieck group. In this contribution, Brylawski's theory is extended in two ways: first of all, the order relation is replaced by a string rewriting system, and secondly, commutativity by partial commutations (that permits a kind of interpolation between non commutativity and full commutativity). This allows us to clarify the relations between the semigroup subject to rewriting and the Tutte-Grothendieck group: the later is actually the Grothendieck group completion of the former, up to the free adjunction of a unit (this was even not mention by Brylawski), and normal forms may be seen as universal invariants. Moreover we prove that such universal constructions are also possible in case of a non convergent rewriting system, outside the scope of Brylawski's work.

Résumé : Le dual topologique de l'espace des séries en un nombre quelconque, éventuellement infini, de variables non commutatives avec un corps topologique séparé de coefficients, pour la topologie produit, n'est autre que l'espace des polynômes. Il en résulte de façon immédiate que les endomorphismes continus sur les séries sont exactement les matrices infinies mais finies en ligne. Les matrices triangulaires infinies, puisque formant une algèbre de Fréchet, disposent quant à elles d'un calcul intégral et différentiel, que nous développons dans un cadre assez général, et qui permet d'établir une correspondance exponentielle-logarithme de type Lie. Nous déployons ces outils sur l'algèbre de Weyl (à deux générateurs) réalisée fidèlement comme une algèbre d'opérateurs agissant continûment sur l'espace des séries formelles (en une variable). Puis nous démontrons que chaque endomorphisme d'un espace vectoriel de dimension infinie dénombrable peut s'obtenir explicitement sous la forme de la somme d'une famille sommable en des opérateurs plus élémentaires, les opérateurs d'échelle (généralisation de l'algèbre de Weyl), précisant de la sorte le théorème de densité de Jacobson. Par dualité (topologique) un résultat similaire concernant les opérateurs continus sur un espace de combinaisons linéaires infinies tombent presque gratuitement. Par ailleurs nous développons la notion d'algèbre (contractée) large d'un monoïde à zéro (obtenue par complétion de l'algèbre contractée) qui nous permet de calculer de nouvelles formules d'inversion de Möbius ainsi que des séries de Hilbert.
Abstract: The topological dual of the space of formal series with any number, even infinite, of noncommutative variables over an Hausdorff topological field, under the product topology, is the space of polynomials. It implies that continuous endomorphisms on series are exactly the infinite but row-finite matrices. Because their totality is a Fréchet algebra, a basic integral and differential calculus can be defined for intinite triangular matrices; such a calculus is futhermore developped in a general way and leads to an exponential-logarithm Lie-like correspondence. These analytic tools are then successfully applied on the first Weyl algebra faithfully represented as an algebra of continuous operators on the space of formal power series (in one variable). Afterwards we prove that every endomorphism of an infinite (countable) dimensional vector space may be explicitly obtained as the sum of a summable family of elementary operators, called ladder operators (generalizing the Weyl algebra) in a way similar to Jacobson's density theorem. By (topological) duality we obtain the same result for continuous operators on a space of infinite linear combinations. Besides we introduce the total (contracted) algebra of a monoid with a zero (as a completion of the usual contracted algebra) which is used to compute new Moebius inversion formulae along with some Hilbert series.

Abstract: The purpose of this paper is to present extended definitions and characterizations of the classical notions of APN and maximum nonlinear Boolean functions to deal with the case of mappings from a finite group K to another one N with the possibility that one or both groups are non-Abelian.

Abstract: Even in spaces of formal power series is required a topology in order to legitimate some operations, in particular to compute infinite summations. Many topologies can be exploited for different purposes. Combinatorists and algebraists may think to usual order topologies, or the product topology induced by a discrete coefficient field, or some inverse limit topologies. Analysists will take into account the valued field structure of real or complex numbers. As the main result of this paper we prove that the topological dual spaces of formal power series, relative to the class of product topologies with respect to Hausdorff field topologies on the coefficient field, are all the same, namely the space of polynomials. As a consequence, this kind of rigidity forces linear maps, continuous for any (and then for all) of those topologies, to be defined by very particular infinite matrices similar to row-finite matrices.  

Abstract: The purpose of this chapter is to give an account on modern cryptography, both symmetric and asymmetric, following the evolution of mathematical techniques to construct secure bijective functions. After a brief introduction concerning some general notions on cryptography, the block ciphers DES, IDEA and AES are presented. In a second part are presented the relations between prime numbers and public-key encryption, followed by a rigorous description of RSA cryptosystem. 

Abstract: Starting with the Heisenberg-Weyl algebra, fundamental to quantum physics, we first show how the ordering of the non-commuting operators intrinsic to that algebra gives rise to generalizations of the classical Stirling Numbers of Combinatorics. These may be expressed in terms of infinite, but row-finite, matrices, which may also be considered as endomorphisms of $\mathbb{C}[[x]]$. This leads us to consider endomorphisms in more general spaces, and these in turn may be expressed in terms of generalizations of the ladder-operators familiar in physics.

Abstract: The Möbius inversion formula, introduced during the 19th century in number theory, was generalized to a wide class of monoids called locally finite such as the free partially commutative, plactic and hypoplactic monoids for instance. In this contribution are developed and used some topological and algebraic notions for monoids with zero, similar to ordinary objects such as the (total) algebra of a monoid, the augmentation ideal or the star operation on proper series. The main concern is to extend the study of the Möbius function to some monoids with zero, i.e., with an absorbing element, in particular the so-called Rees quotients of locally finite monoids. Some relations between the Möbius functions of a monoid and its Rees quotient are also provided.

Abstract: The concern of this paper is a famous combinatorial formula known under the name "exponential formula". It occurs quite naturally in many contexts (physics, mathematics, computer science). Roughly speaking, it expresses that the exponential generating function of a whole structure is equal to the exponential of those of connected substructures. Keeping this descriptive statement as a guideline, we develop a general framework to handle many different situations in which the exponential formula can be applied.

Abstract: A partial monoid $P$ is a set with a partial multiplication $\times$ (and total identity $1_P$) which satisfies some associativity axiom. The partial monoid $P$ may be embedded in a free monoid $P^*$ and the product $\star$ is simulated by a string rewriting system on $P^*$ that consists in evaluating the concatenation of two letters as a product in $P$, when it is defined, and a letter $1_P$ as the empty word $\epsilon$. In this paper we study the profound relations between confluence for such a system and associativity of the multiplication. Moreover we develop a reduction strategy to ensure confluence and which allows us to define a multiplication on normal forms associative up to a given congruence of $P^*$. Finally we show that this operation is associative if, and only if, the rewriting system under consideration is confluent.

Abstract: The Riordan group is the semi-direct product of a multiplicative group of invertible series and a group, under substitution, of non units. The Riordan near algebra, as introduced in this paper, is the Cartesian product of the algebra of formal power series and its principal ideal of non units, equipped with a product that extends the multiplication of the Riordan group. The later is naturally embedded as a subgroup of units into the former. In this paper, we prove the existence of a formal calculus on the Riordan algebra. This formal calculus plays a role similar to those of holomorphic calculi in the Banach or Fréchet algebras setting, but without the constraint of a radius of convergence. Using this calculus, we define "en passant" a notion of generalized powers in the Riordan group.

Abstract: Due to implementation constraints the XOR operation is widely used in order to combine plaintext and key bit-strings in secret-key block ciphers. This choice directly induces the classical version of the differential attack by the use of XOR-kind differences. While very natural, there are many alternatives to the XOR. Each of them inducing a new form for its corresponding differential attack (using the appropriate notion of difference) and therefore block-ciphers need to use S-boxes that are resistant against these nonstandard differential cryptanalysis. In this contribution we study the functions that offer the best resistance against a differential attack based on a finite field multiplication. We also show that in some particular cases, there are robust permutations which offers the best resistant against both multiplication and exponentiation base differential attacks. We call them doubly perfect nonlinear permutations.

Résumé : L'objectif de ce chapitre est de présenter les principes généraux de la cryptographie, à la fois symétrique et asymétrique, en mettant l'accent sur l'évolution des techniques mathématiques de conception des bijections cryptographiquement sûres. Les procédés de chiffrement par blocs DES, IDEA et AES sont par la suite exposés. Enfin les relations entre les nombres premiers et la cryptographie à clef publique, en particulier dans le procédé de chiffrement RSA, sont développées. 

Abstract: The objective of this contribution is to introduce an analogue to the classical secretkey block ciphers, such as DES, IDEA or AES, in the nondenumerable setting, namely where cleartexts, plaintexts and keys are real numbers. The nonlinear part of traditional secretkey block ciphers, the S-boxes, is designed to provide confusion, i.e., to resist to several kind of cryptanalysis such as algebraic, differential or linear attacks. By analogy we construct S-boxes in the uncountable setting which provide the best resistance to a classical or modified version of the differential attack. Since our S-boxes are real-valued functions defined on the real-line, we also need to prevent possible new attacks based on real analysis (such as continuity and derivability), which are ignored since impossible in the finite case: we must hide the topological structure. So we introduce a new kind of discontinuous boxes for this purpose.

Abstract: Bent or perfect nonlinear Boolean functions represent the best resistance against the so-called linear and differential cryptanalysis. But this kind of cryptographic relevant functions only exists when the number of input bits m is an even integer and is larger than the double of the number of output bits n. Unfortunately the non-existence cases, the odd dimension (m is an odd integer) or the plane dimension ( m = n ), are not illegitimate from a cryptographic point of view and even commonly considered. New notions of bentness and perfect nonlinearity are then needed in those impossible cases for the traditional theory. In this paper, by replacing the usual XOR by another kind of bit-strings combination, we explicitly construct new “bent” Boolean functions in traditionally impossible cases.

Abstract: We introduce the notion of a bent function on a finite nonabelian group which is a natural generalization of the well-known notion of bentness on a finite abelian group due to Logachev, Salnikov and Yashchenko. Using the theory of linear representations and noncommutative harmonic analysis of finite groups we obtain several properties of such functions similar to the corresponding properties of traditional Abelian bent functions.

Abstract: The concept of bent functions, originally introduced by Dillon and Rothaus, is very relevant in cryptography because this kind of functions represents the maximal resistance against the so-called linear cryptanalysis. In 1997, Logachev, Salnikov and Yashchenko described a fundamental notion of bentness for functions defined on a finite Abelian group G with values in the unit circle of the complex field. in this paper, by replacing this unit circle by the unit hypersphere S_H(0_H,1) of an arbitrary finite-dimensional Hermitian space H, we develop a generalization of the concept of bentness for S_H(0_H,1)-valued functions defined on G, called multidimensional bent functions.

Résumé : Les notions de fonctions parfaitement non linéaires et courbes sont particulièrement pertinentes en cryptographie puisqu'elles formalisent les résistances maximales face aux très efficaces attaques différentielle et linéaire. Cette thèse est ainsi consacrée à l'étude de ces objets cryptographiques. Nous interprétons ces notions de manière très naturelle essentiellement en substituant les translations figurant dans la définition de la non linéarité parfaite par une action de groupe quelconque. Les propriétés de ces actions telle que la fidélité ou la régularité permettent de décliner en plusieurs variantes ce nouveau concept. Nous développons de surcroît sa caractérisation duale à l'aide de la transformée de Fourier ce qui aboutit à la notion appropriée de fonction courbe. En particulier dans le cas d'une action de groupe non abélien, nous faisons usage de la théorie des représentations linéaires afin d'établir une version duale matricielle. Nous généralisons par ailleurs selon le même principe ces objets combinatoires appelés ensembles à différences qui caractérisent la non linéarité parfaite des fonctions à valeurs dans le corps fini à deux éléments. Cela nous permet d'exhiber des constructions de fonctions satisfaisant nos critères généralisés, en particulier dans ces cas où les fonctions courbes au sens classique n'existent pas.
Abstract: Notions of perfect nonlinearity and bent functions are particularly relevant in cryptography because they formalize maximal resistances against the very efficient differential and linear attacks. This thesis is then dedicated to the study of these cryptographic objects. We naturally interpret these notions in a more abstract and theoretical framework essentially by the substitution of the translations which occur in the definition of perfect nonlinearity by any group action. The properties of these actions as fidelity and regularity allow to decline this new concept into several alternatives. We develop as well its dual characterization using the Fourier transform that leads to an adapted notion of bentness. In particular in the case of a non Abelian group action, we use the linear representations theory to establish a dual matrix version. Furthermore, following the same principle, we generalize those combinatorics objects called difference sets which characterize perfect nonlinearity of functions with values in the finite field with two elements. This allows us to exhibit some constructions of functions which satisfy our generalized criteria, in particular in those cases where bent functions in the usual sense do not exist.