Algebraic methods for cryptographic key exhange

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 ...