Algebra and Cryptography Seminar, Spring 2009

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

February 6, Graduate Center: Antonio Nicolosi (Stevens Institute), Average-Case vs. Generic-Case Complexity of Lattice Problems
Abstract: Lattice problems whose average-case complexity is connected to worst-case assumptions are appealing foundations for provably secure cryptosystems. A sharper understanding of their inherent hardness would enable more precise security analysis, thus resulting in more efficient cryptographic primitives. In this talk, we review the landscape of the average-case complexity of lattice problems, sketch some of the technical tools employed in their analysis, and discuss our ongoing efforts to assess their generic-case complexity.

February 20, Graduate Center: Igor Lysenok (Moscow Steklov Institute and Stevens Institute), On complexity of solving equations in free groups

March 3, 4, 5, at 1:15 pm, Stevens Institute, room Babbio 203, Peirce 216, Babbio 210: Rainer Steinwandt (Florida Atlantic University), Mini-course on Mathematical Techniques in Modern Cryptography

March 13, Graduate Center: Marina Pudovkina (Moscow Engineering Physics Institute), Group properties of generalized Feistel ciphers

April 24, Graduate Center: Ayan Mahalanobis (Stevens Institute of Technology), The MOR cryptosystem
Abstract: The MOR cryptosystem is an elementary and straightforward generalization of the ElGamal cryptosystem. In this case, the discrete logarithm problem works in the automorphism group of a group G, rather than G itself. This allows us to use almost any group for the MOR cryptosystem.
In this talk we will see the definition of this cryptosystem and one instance of a secure and fast MOR cryptosystem -- using the group of non-singular circulant matrices over a finite field of characteristic 2.

May 1, Graduate Center: Alexander Ushakov (Stevens Institute of Technology), Strong Law of Large Numbers for Graph(Group)-Valued Random Elements
Abstract: We introduce the notion of the mean-set (expectation) of a graph- (group-) valued random element $\xi$ and prove a generalization of the strong law of large numbers on graphs and groups. Furthermore, we prove an analogue of the classical Chebyshev's inequality for $\xi$. We show that our generalized law of large numbers, as a new theoretical tool, provides a framework for practical applications; namely, it has implications for cryptanalysis of group-based authentication protocols. In addition, we prove several results about configurations of mean-sets in graphs and their applications. In particular, we discuss computational problems and methods of computing of mean-sets in practice and propose an algorithm for such computation.
Based on a joint work with Natalia Mosina (Columbia University).

May 8, Graduate Center: Vitaly Romankov (Omsk State University), The twisted conjugacy problem in solvable groups
Abstract: We prove that the problem in the title is decidable in every finitely generated metabelian group M for any endomorphism identical modulo a normal subgroup N of [M, M], and in every polycyclic group P for any endomorphism. Also, it is proved that any free nilpotent group of a big enough class is in the Reidemeister class R_{\infty }.

To subscribe to the seminar mailing list, click here