Title: Homomorphic encryption and coding theory Author: Veronika Půlpánová Department: Department of algebra Supervisor: RNDr. Michal Hojsík, Ph.D., Department of algebra Abstract: The current mainstream in fully homomorphic encryption is the appro- ach that uses the theory of lattices. The thesis explores alternative approaches to homomorphic encryption. First we present a code-based homomorphic encrypti- on scheme by Armknecht et. al. and study its properties. Then we describe the family of cryptosystems commonly known as Polly Cracker and identify its pro- blematic aspects. The main contribution of this thesis is the design of a new fully homomorphic symmetric encryption scheme based on Polly Cracker. It proposes a new approach to overcoming the complexity of the simple Polly Cracker - based cryptosystems. It uses Gröbner bases to generate zero-dimensional ideals of po- lynomial rings over finite fields whose factor rings are then used as the rings of ciphertexts. Gröbner bases equip these rings with a multiplicative structure that is easily algorithmized, thus providing an environment for a fully homomorphic cryptosystem. Keywords: Fully homomorphic encryption, Polly Cracker, coding theory, zero- dimensional ideals

Title: Applications of Gröbner bases in cryptography Author: Aleš Fuchs Department: Department of Algebra Supervisor: Mgr. Jan Št'ovíček Ph.D., Department of Algebra Abstract: In the present paper we study admissible orders and techniques of multivariate polynomial division in the setting of polynomial rings over finite fields. The Gröbner bases of some ideal play a key role here, as they allow to solve the ideal membership problem thanks to their properties. We also explore features of so called reduced Gröbner bases, which are unique for a particular ideal and in some way also minimal. Further we will discuss the main facts about Gröbner bases also in the setting of free algebras over finite fields, where the variables are non-commuting. Contrary to the first case, Gröbner bases can be infinite here, even for some finitely generated two- sided ideals. In the last chapter we introduce an asymmetric cryptosystem Polly Cracker, based on the ideal membership problem in both commutative and noncommutative theory. We analyze some known cryptanalytic methods applied to these systems and in several cases also precautions dealing with them. Finally we summarize these precautions and introduce a blueprint of Polly Cracker reliable construction. Keywords: noncommutative Gröbner bases, Polly Cracker, security,...

We develop a public key cryptosystem whose security is based on the intractability of the ideal membership problem for a noncommutative algebra over a finite field. We show that this system, which is the noncommutative analogue of the Polly Cracker cryptosystem, is more secure than the commutative version. This is due to the fact that there are a number of ideals of noncommutative algebras (over finite fields) that have infinite reduced Groebner bases, and can be used to generate a public key. We present classes of such ideals and prove that they do not have a finite Groebner basis under any admissible order. We also examine various techniques to realize finite Groebner bases, in order to determine whether these ideals can be used effectively in the design of a public key cryptosystem. We then show how some of these classes of ideals, which have infinite reduced Groebner bases, can be used to design a public key cryptosystem. We also study various techniques of encryption. Finally, we study techniques of cryptanalysis that may be used to attack the cryptosystems that we present. We show how poorly constructed public keys can in fact, reveal the private key, and discuss techniques to design public keys that adequately conceal the private key. We also show how linear algebra can be used in ciphertext attacks and present a technique to overcome such attacks. This is different from the commutative version of the Polly Cracker cryptosystem, which is believed to be susceptible to "intelligent" linear algebra attacks. / Ph. D.