Search

Of the many families of cryptographic schemes proposed to be post-quantum, a relatively unexplored set of examples comes from group-based cryptography. One of the more central schemes from this area is the so-called Semidirect Product Key Exchange (SDPKE), a generalization of Diffie–Hellman Key Exchange that is plausibly post-quantum. In this report we survey the state of the literature relating to SDPKE, providing a high-level discussion of security, as well as a comprehensive overview of the proposed platforms and the main cryptanalytic ideas relevant to each. [ABSTRACT FROM AUTHOR]

Let Γ be a finite graph and let A (Γ) be the corresponding right-angled Artin group. We characterize the Hamiltonicity of Γ via the structure of the cohomology algebra of A (Γ). In doing so, we define and develop a new canonical graph associated to a matrix, which as a consequence provides a novel perspective on the matrix determinant. [ABSTRACT FROM AUTHOR]

We characterize k-colorability of a simplicial graph via the intrinsic algebraic structure of the associated right-angled Artin group. As a consequence, we show that a certain problem about the existence of homomorphisms from right-angled Artin groups to products of free groups is NP-complete. [ABSTRACT FROM AUTHOR]

The theory of Engel groups plays an important role in group theory since these groups are closely related to the Burnside problems. In this survey we consider several classical and novel algorithmic problems for Engel groups and propose several open problems. We study these problems with a view towards applications to cryptography. [ABSTRACT FROM AUTHOR]

In this paper, we will offer a new symmetric-key cryptographic scheme which is based on the existence of exponentially distorted subgroups in arithmetic groups. Aside from this, we will also provide new examples of distorted subgroups in SL n ⁢ (ℤ ⁢ [ x ]) {\mathrm{SL}_{n}(\mathbb{Z}[x])} which can be utilized for the same purpose. [ABSTRACT FROM AUTHOR]

Abstract In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography. [ABSTRACT FROM AUTHOR]

We describe a practical fully homomorphic encryption (FHE) scheme based on homomorphisms between rings and show that it enables very efficient computation on encrypted data. Our encryption though is private-key; public information is only used to operate on encrypted data without decrypting it. Still, we show that our method allows for a third party search on encrypted data. [ABSTRACT FROM AUTHOR]

The Anshel-Anshel-Goldfeld (AAG) key-exchange protocol was implemented and studied with the braid groups as its underlying platform. The length-based attack, introduced by Hughes and Tannenbaum, has been used to cryptanalyze the AAG protocol in this setting. Eick and Kahrobaei suggest to use the polycyclic groups as a possible platform for the AAG protocol. In this paper, we apply several known variants of the length-based attack against the AAG protocol with the polycyclic group as the underlying platform. The experimental results show that, in these groups, the implemented variants of the length-based attack are unsuccessful in the case of polycyclic groups having high Hirsch length. This suggests that the length-based attack is in sufficient to cryptanalyze the AAG protocol when implemented over this type of polycyclic groups. This implies that polycyclic groups could be a potential platform for some cryptosystems based on conjugacy search problem, such as non-commutative Diffie-Hellman, El Gamal and Cramer-Shoup key-exchange protocols. Moreover, we compare for the first time the success rates of the different variants of the length-based attack. These experiments show that, in these groups, the memory length-based attack introduced by Garber, Kaplan, Teicher, Tsaban and Vishne does better than the other variants proposed thus far in this context. [ABSTRACT FROM AUTHOR]

In this paper, we study the conjugacy problem in polycyclic groups. Our main result is that we construct polycyclic groups Gn whose conjugacy problem is at least as hard as the subset sum problem with n indeterminates. As such, the uniform conjugacy problem over the groups Gn is NP-complete where the parameters of the problem are taken in terms of n and the length of the elements given on input. [ABSTRACT FROM AUTHOR]

Abstract: An abelian extension of the special orthogonal Lie algebra is a nonsemisimple Lie algebra , where is a finite-dimensional representation of , with the understanding that . We determine all abelian extensions of that may be embedded into the exceptional Lie algebra , , and . We then classify these embeddings, up to inner automorphism. As an application, we also consider the restrictions of irreducible representations of to , and discuss which of these restrictions are or are not indecomposable. [Copyright &y& Elsevier]

In this paper, we study the residual solvability of the generalized free product of solvable groups. [ABSTRACT FROM AUTHOR]

Machine learning and statistical techniques are powerful tools for analyzing large amounts of medical and genomic data. On the other hand, ethical concerns and privacy regulations prevent free sharing of this data. Encryption techniques such as fully homomorphic encryption (FHE) enable evaluation over encrypted data. Using FHE, machine learning models such as deep learning, decision trees, and Naive Bayes have been implemented for privacy-preserving applications using medical data. These applications include classifying encrypted data and training models on encrypted data. FHE has also been shown to enable secure genomic algorithms, such as paternity and ancestry testing and privacy-preserving applications of genome-wide association studies. This survey provides an overview of fully homomorphic encryption and its applications in medicine and bioinformatics. The high-level concepts behind FHE and its history are introduced, and details on current open-source implementations are provided. The state of fully homomorphic encryption for privacypreserving techniques in machine learning and bioinformatics is reviewed, along with descriptions of how these methods can be implemented in the encrypted domain. [ABSTRACT FROM AUTHOR]

We prove that one cannot algorithmically decide whether a finitely presented Z -extension admits a finitely generated base group, and we use this fact to prove the undecidability of the BNS invariant. Furthermore, we show the equivalence between the isomorphism problem within the subclass of unique Z -extensions, and the semi-conjugacy problem for deranged outer automorphisms. [ABSTRACT FROM AUTHOR]

This communication records some observations made in the course of studying one-relator groups from the point of view of residual solvability. As a contribution to classification efforts we single out some relator types that render the corresponding one-relator groups residually solvable. [ABSTRACT FROM AUTHOR]