Algebra and Cryptography Seminar, Fall 2007

Organizers: Robert Gilman, Alexei Myasnikov, and Vladimir Shpilrain

Fridays:

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

or

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

directions
Security seminars at Stevens


October 5, Graduate Center: Alexander Ushakov (Stevens Institute of Technology), A Practical Attack on Shifted Conjugacy Based Authentication Protocol
Abstract: A left self-distributive operation on a set S is a binary operation satisfying the law u*(v*w)=(u*v)*(u*w). For example, conjugation in groups satisfies self-distributive condition. There might be other self-distributive operations in specific groups. P. Dehornoy showed that this property can be naturally used for cryptographic purposes, namely for authentication schemes. In this talk I will discuss security assumptions of a new cryptographic primitive proposed by P. Dehornoy, called "Shifted Conjugacy Problem", in braid groups and present two attacks on his scheme.


October 19, Graduate Center: Vladimir Shpilrain (The City College of New York), Authentication schemes and digital signatures
Abstract: Until now, noncommutative public-key cryptography has been primarily focused on key establishment protocols. In this talk, I will show that there is an "hierarchy" of cryptographic products in terms of difficulties in their design, with designing a (secure) key establishment protocol being the most difficult task, followed by designing an authentication scheme, followed by designing a digital signature scheme. In particular, it is possible to design a zero-knowledge authentication scheme whose breaking (i.e., obtaining a secret key) is NP-complete. My talk will mostly focus on authentication schemes, although I will discuss digital signatures as well.


Tuesday, October 23, Stevens Institute, room Peirce 309: Jaime Gutierrez (University of Cantabria, Spain), Lattices in Cryptography
Abstract: Our world is not linear. Many phenomena, however, are often "linearized" because only then a reasonably well-working mathematical machinery can describe the phenomena and produce meaningful forecasts. Lattices are geometric objects that have been used to solve many problems in mathematics and computer science. Lattice reduction strategies or the so called LLL-techniques seem inherently linear. The general idea of this technique is to translate our non linear problem to finding a short vector in a lattice built from the nonlinear equation. Then, the so-called Shortest Vector Problem and Closest Vector Problem in lattices play a major role. In recent years, these techniques have been used repeatedly in algorithmic coding theory and cryptography.
In this talk I will investigate lattice reduction technique on some cryptography problems, namely
- finding roots of multivariate integer polynomials and attacking cryptosystems,
- Integer factoring and RSA,
- predicting pseudorandom number congruential generators over Elliptic Curves


November 2, Graduate Center: Ayan Mahalanobis (Stevens Institute), The MOR cryptosystem and finite p-groups
Abstract: This talk focuses on using p-groups for the MOR cryptosystem. We start with the question: is the MOR cryptosystem over an elementary abelian p-group better than that over a finite field? We then follow the direction this answer leads us to.
 


To subscribe to the seminar mailing list, click here

Spring 2007 talks

Fall 2006 talks

Spring 2006 talks

Fall 2005 talks