Algebra and Cryptography Seminar, Spring 2006

Organizers: Robert Gilman, Alexei Myasnikov, and Vladimir Shpilrain


2:00-3:00 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

February 3, Graduate Center: Vladimir Shpilrain (City College), How to choose a random element from a given infinite group?
Abstract: It turns out that the answer to this question depends on the given group as well as on the purpose of choosing a random element. In particular, an infinite group in this context cannot be considered, by any means, as a "very large finite" group.

February 10, Graduate Center: Ayan Mahalanobis (Stevens Institute), Diffie-Hellman key exchange protocol in non-abelian p-groups.
Abstract: In this talk we discuss a key exchange protocols similar to the Diffie-Hellman key exchange protocol using an abelian subgroup of the automorphism group of a non-abelian group. We also generalize group no.92 of the Hall-Senior table, for arbitrary prime $p$ and study the automorphism group of these generalized group. We show that for those groups, the group of central automorphisms is an abelian group. We use these central automorphisms for the key exchange we are studying.

February 24, Graduate Center: Alexander Ushakov (Stevens Institute), A practical attack on the Anshel-Anshel-Goldfeld key exchange protocol
Abstract: The talk will be in three parts. The first part will be a friendly introduction to the theory of braids. In the second part we will define the commutator key exchange protocol and its particular instance, the Anshel-Anshel-Goldfeld [AAG] key exchange protocol, based on braid groups. In the third part of the talk we will present a new attack on the AAG protocol, which we call a subgroup attack, and show that the current way of generating parameters of the AAG protocol yields insecure keys.

March 10, Stevens Institute: Rainer Steinwandt (Florida Atlantic University), Non-Abelian Groups as Candidate Platform for Cryptographic Schemes: Strengths and Weaknesses
Abstract: In recent years, cryptographic proposals building on non-abelian groups proliferated. A number of interesting constructions building on finite or infinite groups have been identified, but only few of them meet modern cryptographic requirements. Often, the proposed schemes are still at a rather conceptual level, leaving the question of making them practical as a topic for future research. The talk surveys several cryptographic constructions basing on finite or infinite non-abelian groups. Strengths and weaknesses in respect to the construction of practically meaningful schemes are discussed.

March 31, Stevens Institute: Stefan Maubach (University of Texas at Brownsville), Polynomial maps over finite fields
Abstract: Up until now it is not known how to compute the inverse of a polynomial map efficiently. This fact has been used in at least one attempt at making a cryptosystem. I will talk about this attempt and the reason why it failed. In some sense, it may still be too early to make a cryptographic system based on polynomial maps: the theoretical foundation is just not solid enough yet, which (1) makes it quite unsure if a proposal will work, and (2) makes it difficult to get it accepted by the cryptographic community. The main part of the talk will be filled with giving an answer to one of the basic questions that one could address: can one obtain all bijections of the set $k^n$ (where $k$ is the finite field) from invertible polynomial maps on $k[X_1,\ldots,X_n]$? The answer is kind of surprising, and the proof is, in the speaker's opinion, kind of entertaining.

April 7, Stevens Institute:Yacov Yacobi (Microsoft), A New Related Message Attack on RSA
Abstract: Coppersmith, Franklin, Patarin, and Reiter show that given two RSA cryptograms x^e mod N and (ax+b)^e mod N for known constants a, b \in Z_N, one can usually compute x in O(e log^2 e) Z_N -operations (there are O(e) messages for which the method fails). We show that given e cryptograms c_i (a_i x+b_i)^e mod N, i=0, 1,..., e-1, for any known constants a_i, b_i \in Z_N, one can deterministically compute x in O(e) Z_N-operations that depend on the cryptograms, after a pre-processing that depends only on the constants. The complexity of the pre-processing is O(e log^2 e) Z_N-operations, and can be amortized over many instances. We also consider a special case where the overall cost of the attack is O(e) Z_N-operations. Our tools are borrowed from numerical analysis, and to the best of our knowledge their use in cryptanalysis is novel.
Joint with Oded Yacobi, Mathematics Department, University of California, San Diego.

April 19, *Wednesday*, 2:15pm, room P-216, Stevens Institute: Yuri Gurevich (Microsoft), What is an Algorithm?
Abstract: One may think that the title problem was solved long ago by Church and Turing but it wasn't; there is more to an algorithm than the function it computes. (Besides, what function does an operating system compute?) The interest to the problem is not only theoretical; applications include specification and verification of software and hardware. In the main part of the talk, we formalize the notion of sequential algorithm, recall the definition of sequential abstract state machines (ASMs), and then state precisely the Sequential Characterization Theorem according to which, for every sequential algorithm A, there exists a sequential ASM B indistinguishable from A as far as behavior is concerned; in particular B simulates A step-for-step.
If time allows, we will also discuss
(a) generalizations of the Sequential Characterization Theorem to parallel and interactive algorithms,
(b) the applications of the ASM approach.

April 28, Graduate Center: Rainer Steinwandt (Florida Atlantic University), Towards Provably Secure Asymmetric Encryption Building on Finite Non-Abelian Groups
Abstract: The talk discusses a construction for public key encryption schemes that builds on certain group-theoretic tools. The idea is to adapt a known abelian construction of Cramer and Shoup to a non-abelian setting: As will be discussed in the talk, if suitable group-theoretic tools can be provided, it is possible to construct an asymmetric encryption scheme offering provable security in the sense of IND-CCA, i.e., indistinguishable encryptions under adaptive chosen ciphertext attacks. The security proof is in the standard model, i.e., no random oracle assumption is needed.
Based on joint work with María Isabel González Vasco, Consuelo Martínez and Jorge L. Villar.

To subscribe to the seminar mailing list, click here

Fall 2005 talks