Gröbner bases are special sets of polynomials, which are useful to solve problems in many fields such as computer vision, geometric modeling, geometric theorem proving, optimization, control theory, statistics, communications, biology, robotics, coding theory, and cryptography. The major disadvantage of algorithms to compute Gröbner bases is that computations can use a lot of computer power. One of the reasons is the amount of useless critical pairs that the algorithm has to compute. Hence, a lot of effort has been put into developing new criteria to detect such pairs in advance. This thesis is devoted to describe efficient algorithms for the computation of Gröbner bases, with particular emphasis to those based on polynomial signatures. The idea of associating each polynomial with a signature on which the criteria and reduction steps depend, has become extremely popular in part due to its good performance. Our main result combines the criteria from Gao-Volny-Wang's algorithm with the knowledge of Hilbert Series. A parallel implementation of the algorithm is also investigated to improve the computational efficiency. Our algorithm is implemented in CoCoALib, a C++ free library for computations in commutative algebra.

We present some upper bounds on the size of nonlinear codes and their restriction to systematic codes and linear codes. These bounds, which are an improvement of a bound by Zinoviev, Litsyn and Laihonen, are independent of other classical known theoretical bounds. Among these, we mention the Griesmer bound for linear codes, of which we provide a partial generalization for the systematic case. Our experiments show that in some cases (the majority of cases for some q) our bounds provide the best value, compared to all other closed-formula upper-bounds. We also present an algebraic method for computing the minimum weight of any nonlinear code. We show that for some particular code, using a non-standard representation of the code, our method is faster than brute force. An application of this method allows to compute the nonlinearity of a Boolean function, improving existing algebraic methods and reaching the same complexity of algorithms based on the fast Fourier transform.

Internet is evolving in both its structure and usage patterns; this work addresses two trends: i) the increasing popularity and the related generated traffic of media streaming applications and ii) the emerging of network portions following different philosophies from the rest of the internet and being characterized by a mesh topology, such as Community Networks. This thesis presents a modeling for decentralized live streaming for mesh networks based on graph theory, considering the different inter-dependent network abstractions involved. It proposes optimization strategies based on popular centrality metrics, such as betweenness and PageRank. Results on real-world datasets validate the theoretical work and the derived optimizing strategies are implemented in open-source streaming platforms.

Polyominoes are two-dimensional objects obtained by joining edge by edge squares of same size. Originally, polyominoes appeared in mathematical recreations, but it turned out that they have applications in various fields, for example, theoretical physics and bio-informatics. Among the most popular topics in combinatorics related to polyominoes one finds enumerating polyominoes of given size, including the asymptotic growth of the numbers of polyominoes, tiling problems, and reconstruction of polyominoes. Recently Qureshi introduced a binomial ideal induced by the geometry of a given polyomino, called polyomino ideal, and its related algebra. From that moment different authors studied algebraic properties and invariants related to this ideal, such as primality, Gröbner bases, Gorensteinnes and Castelnuovo-Mumford regularity. In this thesis, we provide an overview on the results that we obtained about polyomino ideals and its related algebra. In the first part of the thesis, we discuss questions about the primality and the Gröbner bases of the polyomino ideal. In the second part of the thesis, we talk over the Castelnuovo-Mumford regularity, Hilbert series, and Gorensteinnes of the polyomino ideal and its coordinate ring.

Torsion pairs were introduced by Dickson in 1966 as a generalization of the concept of torsion abelian group to arbitrary abelian categories. Using torsion pairs, we can divide complex abelian categories in smaller parts which are easier to understand. In this thesis we discuss torsion pairs in the category of modules over a finite-dimensional algebra, in particular we explore the relation between torsion pairs in the category of all modules and torsion pairs in the category of finite-dimensional modules. In the second chapter of the thesis, we present the analogue of a classical theorem of Auslander in the context of τ-tilting theory: for a finite-dimensional algebra the number of torsion pairs in the category of finite-dimensional modules is finite if and only if every brick over such algebra is finite- dimensional. In the third chapter, we revisit the Ingalls-Thomas correspondences between torsion pairs and wide subcategories in the context of large torsion pairs. We provide a nice description of the resulting wide subcategories and show that all such subcategories are coreflective. In the final chapter, we describe mutation of cosilting modules in terms of an operation on the Ziegler spectrum of the algebra.

In the first part of this thesis we report results about some “linear” trapdoors that can be embedded in a block cipher. In particular we are interested in any block cipher which has invertible S-boxes and that acts as a permutation on the message space, once the key is chosen. The message space is a vector space and we can endow it with alternative operations (hidden sums) for which the structure of vector space is preserved. Each of this operation is related to a different copy of the affine group. So, our block cipher could be affine with respect to one of these hidden sums. We show conditions on the S-box able to prevent a type of trapdoors based on hidden sums, in particular we introduce the notion of Anti-Crooked function. Moreover we shows some properties of the translation groups related to these hidden sums, characterizing those that are generated by affine permutations. In that case we prove that hidden sum trapdoors are practical and we can perform a global reconstruction attack. We also analyze the role of the mixing layer obtaining results suggesting the possibility to have undetectable hidden sum trapdoors using MDS mixing layers. In the second part we take into account the index coding with side information (ICSI) problem. Firstly we investigate the optimal length of a linear index code, that is equal to the min-rank of the hypergraph related to the instance of the ICSI problem. In particular we extend the the so-called Sandwich Property from graphs to hypergraphs and also we give an upper bound on the min-rank of an hypergraph taking advantage of incidence structures such as 2-designs and projective planes. Then we consider the more general case when the side information are coded, the index coding with coded side information (ICCSI) problem. We extend some results on the error correction index codes to the ICCSI problem case and a syndrome decoding algorithm is also given.

This thesis deals with the classical problem of prime numbers represented by polynomials. It consists of three parts. In the first part I collected many results about the problem. Some of them are quite recent and this part can be considered as a survey of the state of the art of the subject. In the second part I present two results due to P. Pleasants about the cubic polynomials with integer coefficients in several variables. The aim of this part is to simplify the works of Pleasants and modernize the notation employed. In such a way these important theorems are now in a more readable form. In the third part I present some original results related with some algebraic invariants which are the key-tools in the works of Pleasants. The hidden diophantine nature of these invariants makes them very difficult to study. Anyway some results are proved. These results make the results of Pleasants somewhat more effective.

In this thesis, I show that the representation of prime integers by reduced binary quadratic forms of given discriminant can be obtained in polynomial complexity using Schoof's algorithm for counting the number of points of elliptic curves over finite fields. It is a remarkable fact that, although an algorithm of Gauss' solved the representation problem long time ago, a solution in polynomial complexity is very recent and almost unnoticed in the literature. Further, I present a viable alternative to Gauss' algorithm, which constitutes the main original contribution of my thesis. This alternative way of computing in polynomial time an explicit solution of the representation problem is particularly suitable whenever the number of not equivalent reduced forms is small. Lastly, I report that, in the efforts of improving Schoof's algorithm, a marginal incompleteness in its original formulation was identified. This weakness was eliminated by a slight modification of the algorithm suggested by Schoof himself.

Secure multi-party computation (MPC) is a field of cryptography that aims to provide methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike of traditional cryptography where adversary is outside the system of participants, the main task (and challenge) of MPC is to protect participants from internal adversaries, who participate in protocol and can therefore send corrupted. The results presented in this thesis are three-fold. First, we study MPC from a theoretical standpoint, designing a new heuristic and a new proof system useful for proving the security of threshold signatures, a particular kind of MPC protocol. Next, we present new MPC primitives: a novel secret sharing scheme, a threshold version of Schnorr signature, a post quantum secure group action based threshold signature and finally a post quantum oblivious transfer. Lastly, we designed a coercion resistant e-voting protocol, that allows voters to freely votes without being afraid of external adversaries trying to pressure them to vote in a particular way.

Most isogeny-based cryptosystems ultimately rely, for their security, on l- IsoPath, i.e. the problem of finding a secret l-smooth isogeny between two elliptic curves. As cryptographic applications usually employ weaker variants of l-IsoPath for practical reasons, it is natural to ask whether these variants are equally hard from a computational perspective. For example, what happens if the endomorphism ring of one of the curves is known? Does the existence of suitable pairings affect the hardness of l-IsoPath? What happens if some non-trivial endomorphisms of the domain and codomain curves are known? These kinds of questions lead to different problems, some of which are considered throughout this thesis. To prevent anyone from knowing the endomorphism ring of a supersingular elliptic curve, we would need a method to hash in the supersingular isogeny graph, i.e. the graph whose vertices are supersingular elliptic curves (up to isomorphism) and whose edges are isogenies of fixed degree. We give examples of cryptographic protocols that could benefit from this and survey some known methods. Since none of them is at the same time efficient and cryptographically secure, we also point out a few alternative approaches. Later on, we leverage the classic Deuring correspondence between supersingular elliptic curves and quaternion orders to study a weaker version of l-IsoPath, inspired by the study of CM theory from the previous part. We then focus on the construction of pairings of elliptic curves, showing that, in the general case, finding distinct pairings compatible with a secret isogeny is no easier than retrieving the isogeny itself. In the presence of an orientation, on the other hand, we show that the existence of suitable self-pairings, together with a recent attack on the isogeny-based key-exchange SIDH, does lead to efficiently solving l- IsoPath for some class-group-action-based protocols. In particular, we completely characterize the cases in which these selfpairings exist. Finally, we introduce a different graph of elliptic curves, which has not been considered before in isogeny-based cryptography and which does not arise, in fact, from isogenies: the Hessian graph. We give a (still partial) account of its remarkable regularity and discuss potential cryptographic applications.