Algebra and Cryptography Seminar, Spring 2018

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

Fridays:

2:30-3:30 pm
Room 3307, CUNY Graduate Center
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.


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), TBA
 


To subscribe to the seminar mailing list, click here

Fall 2017 talks

Spring 2017 talks

Fall 2016 talks

Spring 2016 talks

Fall 2015 talks

Spring 2015 talks

Fall 2014 talks

Spring 2014 talks

Fall 2013 talks

Spring 2013 talks

Fall 2012 talks

Spring 2012 talks

Fall 2011 talks

Spring 2011 talks

Fall 2010 talks

Spring 2010 talks

Fall 2009 talks

Spring 2009 talks

Fall 2008 talks

Spring 2008 talks

Fall 2007 talks

Spring 2007 talks

Fall 2006 talks

Spring 2006 talks

Fall 2005 talks