2:30-3:30 pm
October 11, Graduate Center: Ha Lam (CUNY Graduate Center),
Public key exchange using semidirect product and matrices over a Galois field
Abstract: We describe a key exchange protocol based on an extension of a semigroup, of which a
special case is the standard Diffie-Hellman protocol. We introduce semigroup of matrices over a Galois field as
the platform and show that the security of the protocol, using this semigroup, is based on quite different
assumptions compared to that of the standard Diffie-Hellman. Finally, we discuss the efficiency of our protocol
over this platform.
October 18, Graduate Center (joint event with
New York Applied Algebra Colloquium): Ki Hyoung Ko (KAIST, South Korea), Pseudo-Anosov braids with
large conjugacy invariant sets
Abstract: I will talk about a family of pseudo-Anosov braids with large conjugacy invariant
sets.
October 25, Graduate Center: Jordi Delgado (Universitat Politècnica
de Catalunya), Computing intersections in Z^m \times F_n
Abstract: Both free abelian and free groups satisfy Howson's property (the intersection of two
finitely generated subgroups is again finitely generated). The first is a classical result of Dedekind, while
the free case
was proved by Howson in the mid 20th century.
Later, B. Baumslag generalized this result proving that Howson's property is preserved by free products. The
same
statement fails dramatically if we replace free product by direct product, and we can find very simple
counterexamples in the family of free abelian times free groups. So, it is natural to ask for an algorithm
that,
given two finitely generated subgroups of Z^m \times F_n, decides whether their intersection is finitely
generated,
and if so, computes it. This is what we call the intersection problem.
I will expose some elementary facts about the family of free abelian times free groups in order to solve the
intersection problem for them. I will also comment on other problems that we solve using similar techniques.
This is joint work with Enric Ventura.
November 8, Graduate Center: William E. Skeith (The City College of
New
York), Translation-randomizable Distributions via Random Walks
Abstract: This work continues the search for viable intractability assumptions over infinite
groups. In particular, we study the possibility of phrasing random self-reducibility properties for infinite
groups in an analogous manner to the case of finite groups with the uniform distribution. As a
first step, it is natural to look for distributions which are translation-invariant, i.e., the probability
of an event and its translate by a group element are the same (as is the case for the
uniform distribution). Indeed, this approach has been considered in cryptographic literature by
E.Lee, who introduced the concept of right invariance. However, we argue a number of
shortcomings for its applicability to cryptography, showing in particular that any computational
problem defined on a right-invariant distribution will not yield a better (weaker) intractability
assumption than some problem defined over a finite group with the uniform distribution.
Using a novel approach based on random walks, we construct families of distributions,
which are translation-randomizable over infinite groups. The main ingredients in our construction
are recurrence (meaning a random walk will invariably return to its origin), and shortcut sampling, which
asserts the existence of an efficient method for sampling a long (super-polynomial
length) walk. Given a suitable group with these properties (for instance Z), we demonstrate how
one may formulate problems with random self reducibility properties akin to the familiar setting
of finite groups and the uniform distribution.
This is joint work with Nirattaya Khamsemanan.
November 15, Graduate Center: Delaram Kahrobaei (New York City
College of Technology and CUNY Graduate Center),
A CCA secure cryptosystem using matrices over group rings
Abstract: In this talk, I will report on a proposal for a cryptosystem based on matrices over
group rings and show that it is secure against adaptive chosen ciphertext attack.
This is joint work with Bobby Koupparis (RBC) and Vladimir Shpilrain (CCNY).
December 6, Graduate Center: Manhattan Algebra Day
December 13, Graduate Center: Martin Kreuzer (University of
Passau),
Algebraic Fault Attacks
Abstract: Fault attacks are a special class of side-channel attacks.
They use intentional manipulation
of the hardware implementation of a cryptographic algorithm such as
power supply manipulation
or laser beams to create miscalculations. Then variants of differential
cryptanalysis are employed
to restrict the key space or fully compute the secret key. Algebraic
fault attacks perform the actual
computation by transforming the task to a system of polynomial equations
over a finite field
and solving this system using symbolic computation or other techniques.
In this talk we discuss
suitable fault models, several attack scenarios for algebraic fault
attacks, ways to create the
system of polynomial equations, various methods to solve these systems
as efficiently as possible, and
possibilities to defend cryptographic devices against fault attacks.
To subscribe to the seminar mailing list, click here