Algebra and Cryptography Seminar, Fall 2008

Organizers: Robert Gilman, 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

Security seminars at Stevens

October 3, Graduate Center: Vladimir Shpilrain (The City College of New York), Authentication schemes
Abstract: In the first part of my talk, I will describe a couple of general ways of constructing Feige-Fiat-Shamir-like authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then I will give several concrete realizations of this general idea, and in particular, describe several authentication schemes where both forgery (a.k.a. impersonation) and recovering the prover's long-term private key are NP-hard. Computationally hard problems that can be employed in these realizations include Graph Homomorphism, Graph Colorability, Diophantine Problem, and many others.
In the second part of the talk, I will describe an authentication scheme, based on an altogether different idea, where forgery is apparently infeasible without finding the prover's long-term private key.
This is joint work with Dima Grigoriev.

October 17, Graduate Center: Alex Myasnikov (Stevens Institute), Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux key agreement protocol
Abstract: The Anshel-Anshel-Goldfeld-Lemieux (abbreviated AAGL) key agreement protocol is proposed to be used on low-cost platforms that constrain the use of computational resources. The core of the protocol is the concept of an Algebraic Eraser (abbreviated AE) which is claimed to be a suitable primitive for use within lightweight cryptography. The underlying motivation for AAGL protocol is the need to secure networks which deploy Radio Frequency Identification (RFID) tags used for identification, authentication, tracing and point-of-sale applications.
In this talk we revisit the computational problem on which AE relies and heuristically analyze its hardness. We show that for proposed parameter values it is impossible to instantiate the secure protocol. To be more precise, in 100% of randomly generated instances of the protocol we were able to find a secret conjugator z generated by the TTP algorithm (part of AAGL protocol).

October 31, Graduate Center: Ben Fine (Fairfield University), Challenge-Response Password Security Using Combinatorial Group Theory

November 7, Graduate Center: Alexander Ushakov (Stevens Institute of Technology), The conjugacy problem in Grigorchuk's group

To subscribe to the seminar mailing list, click here

Spring 2008 talks

Fall 2007 talks

Spring 2007 talks

Fall 2006 talks

Spring 2006 talks

Fall 2005 talks