Algebra and Cryptography Seminar, Spring 2016

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


2:30-3:30 pm
Room 3307, CUNY Graduate Center
365 Fifth Avenue at 34th Street

February 5: Alexander A. Mikhalev (Moscow State University), Cryptographic algorithms on groups and algebras
Abstract: We analyze algorithms for public key exchange on some noncommutative groups. Algorithms for factorization and decomposition in associative algebras (of small dimension) are considered, too. We also give a survey of applications (in particular, to cryptography) of the so-called ``hidden matrices''.
This talk is based on a joint work with A. S. Kuzmin, V. T. Markov, A.V. Mikhalev, and A. A. Nechaev.

February 19: Bianca Sosnovski (Queensborough Community College and CUNY Graduate Center), Cayley graphs of semigroups and applications to hashing
Abstract: Tillich and Zemor proposed a scheme for a family of hash functions (1994), which uses products of matrices in groups of the form SL_2(F_{2^n}). In 2009, Grassl et al. developed an attack to obtain collisions for palindromic bit strings by exploring a connection between the Tillich-Zemor functions and maximal length chains in the Euclidean algorithm for polynomials over F_2. We propose a new platform to be used in the Tillich-Zemor scheme (1994). The platform consists of the (semi)group of linear functions in one variable over F_p under composition generated by f(x)=2x+1 and g(x)=3x+1. The corresponding hash functions are efficient and a lower bound is provided on the minimum length of bit strings where a collision may occur.
Based on joint work with Vladimir Shpilrain.

February 26: Tullia Dymarz (University of Wisconsin-Madison), Nonrectifiable Delone sets in amenable groups
Abstract: In 1998 Burago-Kleiner and McMullen constructed the first examples of coarsely dense and uniformly discrete subsets of R^n that are not bi-Lipschitz equivalent to the standard lattice Z^n for n \geq 2. We will show how to find such sets inside certain other solvable Lie groups. The techniques involve combining ideas from Burago-Kleiner with quasi-isometric rigidity results from geometric group theory.

March 4: Funda Gul (Stevens Institute of Technology), Distortion of embeddings of \tau-groups into group of untriangular matrices
Abstract: In this talk we will introduce some well-known embeddings of \tau-groups (non-abelian, finitely generated nilpotent groups) into group of unitriangular matrices. We will have a look at these embeddings from a geometric point of view and provide some results about the distortion of some of those embeddings. What we mean by the distortion of an embedding is the distortion of the image of \tau-group in the group of unitriangular matrices.

April 1: Dmitry Panteleev (Stevens Institute of Technology), Conjugacy search problem and the Andrews--Curtis conjecture
Abstract: In this talk I will present some new computational methods for studying potential counterexamples to the Andrews--Curtis conjecture, in particular, Akbulut--Kurby examples AK(n). To improve metric properties of the search space (which is a set of balanced presentations of a trivial group) we consider a new transformation that generalizes the original Andrews-Curtis transformations. We will discuss details of a practical implementation of the new move (which uses Pseudo-Conjugacy graphs) and methods to reduce the number of pairs to be considered.
This is joint work with Sasha Ushakov.

April 8: Andrew Sale (Vanderbilt University), The permutation conjugacy length function
Abstract: I will describe a geometric version of the conjugacy problem, which involves determining the length of short conjugators between elements in a group, and defining the conjugacy length function. I will then explain recent work with Y. Antolin in which we define the permutation conjugacy length function, a similar but more delicate notion, which has the potential to form a base for a geometric study of the conjugacy problem that yields fast algorithms solving the conjugacy search problem.

May 13: Anand Sarwate (Rutgers University), From local to distributed differential privacy
Abstract: Differential privacy has become a widely-studied framework for understanding how the results of computation on a database of individuals' private data can reveal information about individual records in the database. In this talk I will describe the differential privacy model and some connections to information theory. I will then discuss recent results on understanding local privacy-distortion tradeoffs from a rate-distortion perspective. Finally, I will describe ongoing work on designing differentially private algorithms for distributed data.


To subscribe to the seminar mailing list, click here

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