Algebra and Cryptography Seminar, Fall 2013

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


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


11:00 am-12:00 pm
Room Peirce 220, Stevens Institute of Technology
Hoboken, NJ


October 11, Graduate Center: Ha Lam (CUNY Graduate Center), Public key exchange using semidirect product and matrices over a Galois field
Abstract: We describe a key exchange protocol based on an extension of a semigroup, of which a special case is the standard Diffie-Hellman protocol. We introduce semigroup of matrices over a Galois field as the platform and show that the security of the protocol, using this semigroup, is based on quite different assumptions compared to that of the standard Diffie-Hellman. Finally, we discuss the efficiency of our protocol over this platform.

October 18, Graduate Center (joint event with New York Applied Algebra Colloquium): Ki Hyoung Ko (KAIST, South Korea), Pseudo-Anosov braids with large conjugacy invariant sets
Abstract: I will talk about a family of pseudo-Anosov braids with large conjugacy invariant sets.

October 25, Graduate Center: Jordi Delgado (Universitat Politècnica de Catalunya), Computing intersections in Z^m \times F_n
Abstract: Both free abelian and free groups satisfy Howson's property (the intersection of two finitely generated subgroups is again finitely generated). The first is a classical result of Dedekind, while the free case was proved by Howson in the mid 20th century. Later, B. Baumslag generalized this result proving that Howson's property is preserved by free products. The same statement fails dramatically if we replace free product by direct product, and we can find very simple counterexamples in the family of free abelian times free groups. So, it is natural to ask for an algorithm that, given two finitely generated subgroups of Z^m \times F_n, decides whether their intersection is finitely generated, and if so, computes it. This is what we call the intersection problem. I will expose some elementary facts about the family of free abelian times free groups in order to solve the intersection problem for them. I will also comment on other problems that we solve using similar techniques.
This is joint work with Enric Ventura.

November 8, Graduate Center: William E. Skeith (The City College of New York), Translation-randomizable Distributions via Random Walks
Abstract: This work continues the search for viable intractability assumptions over infinite groups. In particular, we study the possibility of phrasing random self-reducibility properties for infinite groups in an analogous manner to the case of finite groups with the uniform distribution. As a first step, it is natural to look for distributions which are translation-invariant, i.e., the probability of an event and its translate by a group element are the same (as is the case for the uniform distribution). Indeed, this approach has been considered in cryptographic literature by E.Lee, who introduced the concept of right invariance. However, we argue a number of shortcomings for its applicability to cryptography, showing in particular that any computational problem defined on a right-invariant distribution will not yield a better (weaker) intractability assumption than some problem defined over a finite group with the uniform distribution.
Using a novel approach based on random walks, we construct families of distributions, which are translation-randomizable over infinite groups. The main ingredients in our construction are recurrence (meaning a random walk will invariably return to its origin), and shortcut sampling, which asserts the existence of an efficient method for sampling a long (super-polynomial length) walk. Given a suitable group with these properties (for instance Z), we demonstrate how one may formulate problems with random self reducibility properties akin to the familiar setting of finite groups and the uniform distribution.
This is joint work with Nirattaya Khamsemanan.

November 15, Graduate Center: Delaram Kahrobaei (New York City College of Technology and CUNY Graduate Center), A CCA secure cryptosystem using matrices over group rings
Abstract: In this talk, I will report on a proposal for a cryptosystem based on matrices over group rings and show that it is secure against adaptive chosen ciphertext attack. This is joint work with Bobby Koupparis (RBC) and Vladimir Shpilrain (CCNY).

December 6, Graduate Center: Manhattan Algebra Day

December 13, Graduate Center: Martin Kreuzer (University of Passau), Algebraic Fault Attacks
Abstract: Fault attacks are a special class of side-channel attacks. They use intentional manipulation of the hardware implementation of a cryptographic algorithm such as power supply manipulation or laser beams to create miscalculations. Then variants of differential cryptanalysis are employed to restrict the key space or fully compute the secret key. Algebraic fault attacks perform the actual computation by transforming the task to a system of polynomial equations over a finite field and solving this system using symbolic computation or other techniques. In this talk we discuss suitable fault models, several attack scenarios for algebraic fault attacks, ways to create the system of polynomial equations, various methods to solve these systems as efficiently as possible, and possibilities to defend cryptographic devices against fault attacks.


To subscribe to the seminar mailing list, click here

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