Algebra and Cryptography Seminar, Spring 2018

Organizers: Delaram Kahrobaei, Vladimir Shpilrain, Robert Gilman, and Alexei Myasnikov

Fridays:

2:30-3:30 pm
365 Fifth Avenue at 34th Street

February 2: Jonathan Gryak (University of Michigan), Solving the Conjugacy Decision Problem via Machine Learning
Abstract: In this talk we consider the application of machine learning and pattern recognition techniques to solving algorithmic problems in finitely presented groups. In particular, we utilize supervised learning methods to solve the conjugacy decision problem in several finitely presented groups.
This is joint work with R. H. Haralick and D. Kahrobaei.

February 16: Tuval Foguel and Josh Hiller (Adelphi University), On Bruck's Prolongation and Contraction Maps
Abstract: We define a new family of quasigroups: Bruck quasigroups (where aa^2=a^2a and a^2=b^2 for all possible a and b). We use Bruck's prolongation and contraction maps to explore properties of this family of quasigroups. Among other results, we show that there is a one-to-one correspondence between Bruck quasigroups and uniquely 2-divisible quasigroups. As a corollary to this result we find a correspondence between idempotent quasigroups and loops of exponent 2. We then use this correspondence to study some interesting loops of exponent 2 and some interesting idempotent quasigroups. We also present an algebraic generalization of Bruck's prolongation.

Wednesday, April 25, 4:00, room 4421: Antonio Tortora (Universita di Salerno, Italy), On conciseness of some commutator words
Abstract: If w = w(x_1,..., x_n) is a group-word in variables x_1,...,x_n, we denote by w(G) the verbal subgroup of the group G generated by the set G_w of all values of w in G. A group-word w is called concise if the finiteness of G_w for every group G always implies the finiteness of w(G). The aim of this talk is to survey old and new results concerning the conciseness of some commutator words.

Wednesday, April 25, 4:45, room 4421: Maria Tota (Universita di Salerno, Italy), On the primitivity of PRESENT and other lightweight ciphers
Abstract: We provide two sufficient conditions to guarantee that the round functions of a translation based cipher generate a primitive group. Furthermore, we prove that, under certain hypotheses, such a group is the alternating group. As a consequence, we deduce that the round functions of some lightweight translation based ciphers, such as the PRESENT cipher, generate the alternating group.

April 27: Alexander Ushakov (Stevens Institute of Technology), An attack on WalnutDSA
Abstract: We analyze security properties of a digital signature algorithm recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels, named WalnutDSA, that has been accepted by the National Institute of Standards and Technology for evaluation as a standard for quantum-resistant public-key cryptography. At the core of the algorithm is an action, named e-multiplication, of a braid group on some finite set. The protocol assigns a pair of braids to the signer as a private key. A signature of a message $m$ is a specially constructed braid that is obtained as a product of private keys, the hash value of $m$ encoded as a braid, and three specially designed cloaking elements. We present a heuristic algorithm that allows a passive eavesdropper to recover a substitute for the signer's private key by removing cloaking elements and then solving a system of conjugacy equations in braids. Our attack has 100% success rate on randomly generated instances of the protocol. It works with braids only and its success rate is not affected by a choice of a base finite field. In particular, it has the same 100% success rate for recently suggested parameters values (including a new way to generate cloaking elements).
Based on a joint work with M. Kotov and A. Menshov

May 4: Gabriel Zapata (CUNY Graduate Center), Using transversals in public-key cryptography
Abstract: We present a key exchange protocol based on the idea of Kahrobaei and Shpilrain, which compares favorably to the Diffie-Hellman protocol based on a cyclic group. In their protocol, Kahrobaei and Shpilrain implement the semidirect product G = K \ltimes H, where K is a subgroup of G and H is normal in G. In our proposal we replace K \ltimes H with a set T \times H (where T is a transversal of a group G and H is a subgroup of G) and determine a rewriting method that allows for a description of a product in T \times H such that G becomes isomorphic to T \times H.