Algebra and Cryptography Seminar, Fall 2012

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

Fridays:

2:30-3:30 pm
365 Fifth Avenue at 34th Street

or

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

directions

September 28, Graduate Center: Georg Zetzsche (University of Kaiserslautern), Valence automata as a generalization of automata with storage
Abstract: A valence automaton over a monoid M is a finite automaton in which each edge carries an input word and an element of M. A word is then accepted if there is a run that spells the word such that the product of the monoid elements is the identity.
By choosing appropriate monoids M, one can obtain various kinds of automata with storage as special valence automata. Examples include pushdown automata, blind multicounter automata, and partially blind multicounter automata. Therefore, valence automata offer a framework to generalize results on such automata with storage.
This talk will present recent results on valence automata. The addressed questions include: For which monoids can we accept non-regular languages? For which monoids can we determinize automata? For which monoids can we avoid silent edges (i.e., those which read no input symbol)?

October 12, Graduate Center: Alexander Guterman (Moscow State University), On the Polya permanent/determinant conversion problem
Abstract: Two important functions in matrix theory, determinant and permanent, look very similar. While computation of the determinant can be done in polynomial time, it is still an open question if there is a polynomial time algorithm to compute the permanent. For this reason, starting from the work by Polya, 1913, different approaches to converting the permanent into the determinant were under the intensive investigation.
Among our results we prove the following theorem: Suppose n \ge 3, and let F be a finite field of characteristic \ne 2. Then no bijective map T : M_n(F) \to M_n(F) satisfies per A= det T(A).
This talk is based on several joint works with Mikhail Budrevich, Gregor Dolinar, Bojan Kuzma and Marko Orel.

October 26, Graduate Center: Alexander Ushakov (Stevens Institute of Technology), Cryptanalysis of matrix conjugation schemes
Abstract: We cryptanalyze two protocols: Grigoriev-Shpilrain authentication protocol and Wang et al. public key encryption protocols that use computational hardness of some variations of the conjugacy search problem in noncommutative monoids. We devise an efficient heuristic algorithm, similar to length based attacks for braid-based schemes, solving those problems. As a conclusion, we claim that these protocols are insecure for the proposed parameter values.

Abstract: We employ physical properties of the real world to design a secure cryptographic protocol where one of the parties is able to transmit secret information to another party over an insecure channel, without any prior secret arrangements between the parties. The distinctive feature of this protocol, compared to all known public-key protocols, is that neither party uses a one-way function. In particular, our protocol is secure against (passive) computationally unbounded adversary.
This is joint work with Dima Grigoriev.

December 7, Graduate Center: Manhattan Algebra Day