Abstract Cryptographic key exchange is an integral part of modern cryptography. Such schemes allow two parties to derive a common secret key over a public channel without a priori shared information. One of the most successful key agreement schemes is the one suggested by Diffie and Hellman in their seminal work on public key cryptography. In this thesis, we give an algebraic generalization of the Diffie-Hellman scheme called AGDH utilizing its implicit algebraic properties. The generalization is based on the problem of computing homomorphic images from an algebra to another. Appropriately, we call this problem the homomorphic image problem (HIP). We also devise an authenticated key exchange protocol that is secure in the Canetti-Krawczyk model assuming the infeasibility of the decision HIP (DHIP). For the secure instantiation of the scheme, we consider symmetric encryption schemes that are homomorphic over an algebraic operation. We derive a condition for the encryption scheme to be homomorphic key agreement capable. We show that whenever this condition is satisfied, the induced DHIP is computationally infeasible based on the security of the encryption scheme. To show that there are such schemes, we give a description of one such that the infeasibility of the DHIP follows from a weaker version of the McEliece generator matrix pseudorandomness assumption and the learning parity with noise (LPN) problem. We also study algebraic methods for generating suitable structures for the devised scheme. Since the platform structure requires a large set of homomorphisms, we consider classes of algebras for which this is the case. In particular, we concentrate on a class of algebras satisfying the left distributivity (LD) property. We formulate a non-associative generalization of the conjugacy search problem (CSP) called partial CSP (PCSP) for left conjugacy closed left quasigroups. We show that the feasibility of the HIP on LD left quasigroups depends on the PCSP. Application of this problem leads to a non-associative variant of the Anshel-Anshel-Goldfeld key agreement scheme. We also formulate different versions of the PCSP and show several relative hardness results related to them. Finally, we study more closely the PCSP for a class of conjugacy closed loops of order p2, where p is a prime. We show that the hardness of the PCSP depends on the number of generators for the conjugator and on that of conjugacy equation pairs. Based on the weakest variant of the PCSP, we devise a symmetric blind decryption scheme on these loops and show that it satisfies perfect secrecy against passive adversaries. / Tiivistelmä Kryptografiset avaintenvaihtomenetelmät ovat eräs modernin kryptografian tärkeimmistä osista. Näiden menetelmien avulla pystytään sopimaan ilman aiempaa tiedonvaihtoa yhteisestä salaisesta avaimesta käyttämällä julkista kanavaa. Diffie-Hellman -avaintenvaihto on yksi parhaiten tunnetuista ja eniten käytetyistä menetelmistä. Tässä työssä tarkastellaan kyseisen menetelmän yleistämistä perustuen sen algebrallisiin ominaisuuksiin. Johdettu yleistys perustuu vaikeuteen löytää annetun alkion homomorfinen kuva, jota työssä kutsutaan homomorfisen kuvan ongelmaksi (HIP). Lisäksi suunnitellaan autentikoitu avaintenvaihtoprotokolla, joka on turvallinen Canetti-Krawczyk -mallissa olettaen että homomorfisen kuvan ongelman päätösversio (DHIP) on laskennallisesti vaikea. Menetelmän turvallista toteuttamista varten tarkastellaan symmetrisen avaimen salausmenetelmiä, jotka ovat homomorfisia joidenkin algebrallisten operaatioiden yli. Työssä johdetaan symmetrisen avaimen salainten ominaisuus, kyvykkyys homomorfiseen avaintenvaihtoon, joka takaa että aikaansaatu DHIP on laskennallisesti vaikea. Lisäksi rakennetaan symmetrinen menetelmä, joka toteuttaa kyseisen ehdon. Menetelmän turvallisuus perustuu tavallista heikompaan oletukseen McEliece-generaattorimatriisin pseudosatunnaisuudesta sekä pariteetin oppimisongelman häiriölliseen versioon (LPN). Työssä tarkastellaan lisäksi menetelmiä soveltuvien algebrallisten rakenteiden generointiin. Koska menetelmä vaatii suuren joukon homomorfismeja, tarkastellaan rakenteita, joille tämä ehto pätee. Erityisesti keskitytään ns. vasemmalta distributiivisiin (LD) rakenteisiin. Työssä määritellään epäassosiatiivinen yleistys konjugointiongelman hakuversiolle (CSP) konjugoinnin suhteen suljettuille vasemmille kvasiryhmille. Tätä yleistystä kutsutaan osittaiseksi CSP:ksi (PCSP). Työssä osoitetaan, että vasemmalta distributiivisissa vasemmissa kvasiryhmissä homomorfisen kuvan ongelman vaikeus liittyy läheisesti PCSP:hen. Lisäksi tätä ongelmaa sovelletaan määrittämään epäassosiatiivinen variantti Anshel-Anshel-Goldfeld -avaintenvaihtomenetelmästä. Lisäksi tarkastellaan PCSP:n erilaisia versioita ja niiden suhteellista laskennallista kompleksisuutta. PCSP:tä tarkastellaan tarkemmin konjugoinnin suhteen suljetuissa luupeissa, joiden kertaluku on p2, missä p on alkuluku. Työssä osoitetaan, että PCSP:n vaikeus riippuu konjugoijan generaattoreiden sekä konjugaatioyhtälöiden lukumäärästä. Käyttämällä hyväksi näitä tuloksia ja erityisesti PCSP:n helpointa versiota, laaditaan symmetrisen avaimen salausmenetelmä, joka tukee ns. sokeaa salauksenpurkua. Lisäksi osoitetaan, että menetelmä takaa täydellisen salassapidon passiivisia hyökkäyksiä vastaan.

The topics explored in this project present and interesting picture of close connections between algebra and geometry. Given a specific system of polynomial equations we show how to construct a Groebner basis using Buchbergers Algorithm. Gröbner bases have very nice properties, e.g. they do give a unique remainder in the division algorithm. We use these bases to solve systems of polynomial quations in several variables and to determine whether a function lies in the ideal.

De Morgan monoids are algebraic structures that model certain non-classical logics. The variety DMM of all De Morgan monoids models the relevance logic Rt (so-named because it blocks the derivation of true conclusions from irrelevant premises). The so-called subvarieties and subquasivarieties of DMM model the strengthenings of Rt by new logical axioms, or new inference rules, respectively. Meta-logical problems concerning these stronger systems amount to structural problems about (classes of) De Morgan monoids, and the methods of universal algebra can be exploited to solve them. Until now, this strategy was under-developed in the case of Rt and DMM. The thesis contributes in several ways to the filling of this gap. First, a new structure theorem for irreducible De Morgan monoids is proved; it leads to representation theorems for the algebras in several interesting subvarieties of DMM. These in turn help us to analyse the lower part of the lattice of all subvarieties of DMM. This lattice has four atoms, i.e., DMM has just four minimal subvarieties. We describe in detail the second layer of this lattice, i.e., the covers of the four atoms. Within certain subvarieties of DMM, our description amounts to an explicit list of all the covers. We also prove that there are just 68 minimal quasivarieties of De Morgan monoids. Thereafter, we use these insights to identify strengthenings of Rt with certain desirable meta-logical features. In each case, we work with the algebraic counterpart of a meta-logical property. For example, we identify precisely the varieties of De Morgan monoids having the joint embedding property (any two nontrivial members both embed into some third member), and we establish convenient sufficient conditions for epimorphisms to be surjective in a subvariety of DMM. The joint embedding property means that the corresponding logic is determined by a single set of truth tables. Epimorphisms are related to 'implicit definitions'. (For instance, in a ring, the multiplicative inverse of an element is implicitly defined, because it is either uniquely determined or non-existent.) The logical meaning of epimorphism-surjectivity is, roughly speaking, that suitable implicit definitions can be made explicit in the corresponding logical syntax. / Thesis (PhD)--University of Pretoria, 2020. / DST-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS) / Mathematics and Applied Mathematics / PhD / Unrestricted

Network satisfaction problems (NSPs) for finite relation algebras are computational decision problems, studied intensively since the 1990s. The major open research challenge in this field is to understand which of these problems are solvable by polynomial-time algorithms. Since there are known examples of undecidable NSPs of finite relation algebras it is advisable to restrict the scope of such a classification attempt to well-behaved subclasses of relation algebras. The class of relation algebras with a normal representation is such a well-behaved subclass. Many well-known examples of relation algebras, such as the Point Algebra, RCC5, and Allen’s Interval Algebra admit a normal representation. The great advantage of finite relation algebras with normal representations is that their NSP is essentially the same as a constraint satisfaction problem (CSP). For a relational structure B the problem CSP(B) is the computational problem to decide whether a given finite relational structure C has a homomorphism to B. The study of CSPs has a long and rich history, culminating for the time being in the celebrated proofs of the Feder-Vardi dichotomy conjecture. Bulatov and Zhuk independently proved that for every finite structure B the problem CSP(B) is in P or NP-complete. Both proofs rely on the universal-algebraic approach, a powerful theory that connects algebraic properties of structures B with complexity results for the decision problems CSP(B). Our contributions to the field are divided into three parts. Firstly, we provide two algebraic criteria for NP-hardness of NSPs. Our second result is a complete classification of the complexity of NSPs for symmetric relation algebras with a flexible atom; these problems are in P or NP-complete. Our result is obtained via a decidable condition on the relation algebra which implies polynomial-time tractability of the NSP. As a third contribution we prove that for a large class of NSPs, non-hardness implies that the problems can even be solved by Datalog programs, unless P = NP. This result can be used to strengthen the dichotomy result for NSPs of symmetric relation algebras with a flexible atom: every such problem can be solved by a Datalog program or is NP-complete. Our proof relies equally on known results and new observations in the algebraic analysis of finite structures. The CSPs that emerge from NSPs are typically of the form CSP(B) for an infinite structure B and therefore do not fall into the scope of the dichotomy result for finite structures. In this thesis we study NSPs of finite relation algebras with normal representations by the universal algebraic methods which were developed for the study of finite and infinite-domain CSPs. We additionally make use of model theory and a Ramsey-type result of Nešetril and Rödl. Our contributions to the field are divided into three parts. Firstly, we provide two algebraic criteria for NP-hardness of NSPs. Our second result is a complete classification of the complexity of NSPs for symmetric relation algebras with a flexible atom; these problems are in P or NP-complete. Our result is obtained via a decidable condition on the relation algebra which implies polynomial-time tractability of the NSP. As a third contribution we prove that for a large class of NSPs the containment in P implies that the problems can even be solved by Datalog programs, unless P = NP. As a third contribution we prove that for a large class of NSPs, non-hardness implies that the problems can even be solved by Datalog programs, unless P = NP. This result can be used to strengthen the dichotomy result for NSPs of symmetric relation algebras with a flexible atom: every such problem can be solved by a Datalog program or is NP-complete. Our proof relies equally on known results and new observations in the algebraic analysis of finite structures.

<div>We further the research in o-minimal topology by studying in full generality definable topological spaces in o-minimal structures. These are topological spaces $(X, \tau)$, where $X$ is a definable set in an o-minimal structure and the topology $\tau$ has a basis that is (uniformly) definable. Examples include the canonical o-minimal "euclidean" topology, “definable spaces” in the sense of van den Dries [17], definable metric spaces [49], as well as generalizations of classical non-metrizable topological spaces such as the Split Interval and the Alexandrov Double Circle.</div><div><br></div><div>We develop a usable topological framework in our setting by introducing definable analogues of classical topological properties such as separability, compactness and metrizability. We characterize these notions, showing in particular that, whenever the underlying o-minimal structure expands $(\mathbb{R},<)$, definable separability and compactness are equivalent to their classical counterparts, and a similar weaker result for definable metrizability. We prove the equivalence of definable compactness and various other properties in terms of definable curves and types. We show that definable topological spaces in o-minimal expansions of ordered groups and fields have properties akin to first countability. Along the way we study o-minimal definable directed sets and types. We prove a density result for o-minimal types, and provide an elementary proof within o-minimality of a statement related to the known connection between dividing and definable types in o-minimal theories.</div><div><br></div><div>We prove classification and universality results for one-dimensional definable topological spaces, showing that these can be largely described in terms of a few canonical examples. We derive in particular that the three element basis conjecture of Gruenhage [25] holds for all infinite Hausdorff definable topological spaces in o-minimal structures expanding $(\mathbb{R},<)$, i.e. any such space has a definable copy of an interval with the euclidean, discrete or lower limit topology.</div><div><br></div><div>A definable topological space is affine if it is definably homeomorphic to a euclidean space. We prove affineness results in o-minimal expansions of ordered fields. This includes a result for Hausdorff one-dimensional definable topological spaces. We give two new proofs of an affineness theorem of Walsberg [49] for definable metric spaces. We also prove an affineness result for definable topological spaces of any dimension that are Tychonoff in a definable</div><div>sense, and derive that a large class of locally affine definable topological spaces are affine.</div>

<p>This work strengthens and extends an algorithm for computing Betti numbers of symmetric semialgebraic sets developed by Basu and Riener in, <em>Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-Algebraic Sets</em>. We first adapt a construction of Gabrielov and Vorobjov in, <em>Approximation of Definable Sets by Compact Families, and Upper Bounds on Homotopy and Homology,</em> for replacing arbitrary definable sets by compact ones to the symmetric case. The original construction provided maps from the homotopy and homology groups of the replacement set to those of the original; we show that for sets symmetric relative to the action of some finite reflection group <em>G</em>, we may construct these maps to be equivariant. This modification to the construction for compact replacement allows us to extend Basu and Riener's theorem on which submodules appear in the isotypic decomposition of each cohomology space to sets not necessarily closed and bounded. Furthermore, by utilizing this equivariant compact approximation, we may obtain a precise description of the aforementioned decomposition of each cohomology space, and not merely the final dimension of the space, from Basu and Riener's algorithm.</p> <p><br></p> <p>    Though our equivariant compact replacement holds for <em>G</em> any finite reflection group, Basu and Riener's results only consider the case of the action the of symmetric group, sometimes termed type <em>A</em>. As a first step towards generalizing Basu and Riener's work, we examine the next major class of symmetry: the action of the group of signed permutations (known as type <em>B</em>). We focus our attention on Vandermonde varieties, a key object in Basu and Riener's proofs. We show that the intersection of a type <em>B</em> Vandermonde variety with a fundamental region of type <em>B</em> symmetry is topologically regular. We also prove a result about the intersection of a type <em>B</em> Vandermonde variety with the walls of this fundamental region, leading to the elimination of factors in a different decomposition of the homology spaces.</p>

Achieving a classification of all clones of operations over a finite set is one of the goals at the heart of universal algebra. In 1921 Post provided a full description of the lattice of all clones over a two-element set. However, over the following years, it has been shown that a similar classification seems arduously reachable even if we only focus on clones over three-element sets: in 1959 Janov and Mučnik proved that there exists a continuum of clones over a k-element set for every k > 2. Subsequent research in universal algebra therefore focused on understanding particular aspects of clone lattices over finite domains. Remarkable results in this direction are the description of maximal and minimal clones. One might still hope to classify all operation clones on finite domains up to some equivalence relation so that equivalent clones share many of the properties that are of interest in universal algebra. In a recent turn of events, a weakening of the notion of clone homomorphism was introduced: a minor-preserving map from a clone C to D is a map which preserves arities and composition with projections. The minor-equivalence relation on clones over finite sets gained importance both in universal algebra and in computer science: minor-equivalent clones satisfy the same set identities of the form f(x_1,...,x_n) = g(y_1,...,y_m), also known as minor-identities. Moreover, it was proved that the complexity of the CSP of a finite structure A only depends on the set of minor-identities satisfied by the polymorphism clone of A. Throughout this dissertation we focus on the poset that arises by considering clones over a three-element set with the following order: we write C ≤_{m} D if there exist a minor-preserving map from C to D. It has been proved that ≤_{m} is a preorder; we call the poset arising from ≤_{m} the pp-constructability poset. We initiate a systematic study of the pp-constructability poset. To this end, we distinguish two cases that are qualitatively distinct: when considering clones over a finite set A, one can either set a boundary on the cardinality of A, or not. We denote by P_n the pp-constructability poset restricted to clones over a set A such that |A|=n and by P_{fin} we denote the whole pp-constructability poset, i.e., we only require A to be finite. First, we prove that P_{fin} is a semilattice and that it has no atoms. Moreover, we provide a complete description of P_2 and describe a significant part of P_3: we prove that P_3 has exactly three submaximal elements and present a full description of the ideal generated by one of these submaximal elements. As a byproduct, we prove that there are only countably many clones of self-dual operations over {0,1,2} up to minor-equivalence.

For $n\geq2$, a variety $\mathcal{V}$ is said to be congruence $n$-permutable if every algebra $\mathbf{A}\in\mathcal{V}$ satisfies $\alpha\circ^n\beta=\beta\circ^n\alpha$, for all $\alpha,\beta\in \Con(\mathbf{A})$. Furthermore, given any algebra $\mathbf{A}$ and $k\geq1$, a $k$-dimensional Hagemann relation on $\mathbf{A}$ is a reflexive compatible relation $R\subseteq A\times A$ such that $R^{-1}\not\subseteq R\circ^k R$. A famous result of J. Hagemann and A. Mitschke shows that a variety $\mathcal{V}$ is congruence $n$-permutable if and only if $\mathcal{V}$ has no member carrying an $(n-1)$-dimensional Hagemann relation: by using this criterion, we provide another Maltsev characterization of congruence $n$-permutability, equivalent to the well-known Schmidt's and Hagemann-Mitschke's (\cite{HagMit}) term-based descriptions. We further establish that the omission by varieties of certain special configurations of Hagemann relations induces the satisfaction of suitable Maltsev conditions. These omission properties may be used to characterize congruence $n$-permutable idempotent varieties for some $n\geq2$, congruence 2-permutable idempotent varieties and congruence 3-permutable locally finite idempotent varieties, yielding that the following are prime Maltsev conditions: \begin{enumerate} \item congruence $n$-permutability for some $n\geq2$ with respect to idempotent varieties; \item congruence 2-permutability with respect to idempotent varieties; \item congruence 3-permutability with respect to locally finite idempotent varieties. \end{enumerate} Finally, we focus on the analysis of a family of strong Maltsev conditions, which we denote by $\{\mathcal{D}_n:2\leq n<\omega\}$, such that any variety $\mathcal{V}$ is congruence $n$-permutable whenever $\mathcal{D}_n$ is interpretable in $\mathcal{V}$. Among various other properties, we also show that the $\mathcal{D}_n$'s with odd $n\geq3$ generate decomposable strong Maltsev filters in the lattice of interpretability types. / Thesis / Doctor of Philosophy (PhD)

In this thesis we derive novel results on the complexity of idempotent Mal'tsev condition satisfaction problems. For a Mal'tsev condition M, the idempotent M- satisfaction problem is the decision problem defined via: INPUT: A finite idempotent algebra A. QUESTION: Does A satisfy M? In particular we are able to prove that this decision problem is in the complexity class NP whenever M satisfi es one of the following conditions: 1. M is a strong Mal'tsev condition which implies the existence of a near unanimity term. 2. M is a strong Mal'tsev condition of height < 1 (see Definition 5.1.1). As a porism of these two results, we are able to derive the stronger result that the complexity of the idempotent M-satisfaction problem is in NP whenever M is a strong Mal'tsev condition which implies the existence of an edge term. On top of this we also outline a polynomial-time algorithm for the idempotent M-satisfaction problem when M is a linear strong Mal'tsev condition which implies the existence of a near unanimity term. We also examine the related search problem in which the goal is to produce operation tables of term operations of the algebra A which witness that A satisfies the Mal'tsev condition M whenever such terms exist (and otherwise correctly decide that such terms do not exist). We outline polynomial-time algorithms for this search problem for various strong Mal'tsev conditions. We close the thesis with a short list of open problems as suggested directions for further research. / Thesis / Doctor of Philosophy (PhD)

No abstract provided. / Thesis / Doctor of Philosophy (PhD) / Scope and contents: Two topics are studied in this thesis. The first topic is concerned with the relation between the categories of complexes over two algebras when there is a unitary algebra homomorphism from one to the other. The second topic deals with differential forms. A certain finiteness theorem for the module of integral differential forms is studied.