Algebra and Cryptography Seminar, Spring 2016

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

Fridays:

2:30-3:30 pm
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.