2:00-3:00 pm

Room 8405, CUNY Graduate Center

365 Fifth Avenue at 34th Street

Room Peirce 220, Stevens Institute of Technology

Hoboken, NJ

directions

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