Department of Mathematical Sciences
Florida Atlantic University
Boca Raton, Florida 33431-0991

Algebra-Cryptology Seminar

Fall 2002

Tuesday, November 26, 2002, at 2 p.m. in S&E 215

An Inquiry into the Mathematical Basis
for the Cryptographic Strength
of the 'Dedicated' Hash
Functions like SHA-1

Michael G. Lisanke (IBM)

Abstract.  This talk will be based on a question raised in Dr. Schmidmeier's "Number Theory and Cryptography" class. In discussing hash functions, I asked why the hash functions that I had coded in 'C' from standards documents, did not appear to be based on the known hard mathematical problems (prime factorization, discrete logarithm problem, and others) described in class.

In this talk, I will present the motivation for hashing functions, and (as best possible) describe the SHA-1 hash function and the operators used to implement it. The talk will be constructed from material taken from the
paper "Cryptographic Hash Functions: A Survey", by Bakhtiari, Safavi-Naini, and Pieprzyk, and the IETF working group draft "US Secure Hash Algorithm 1 SHA1", by Eastlake.

I hope to instigate discussion among our attendees directed towards answering this question.

Tuesday, November 19, 2002, at 2 p.m. in S&E 215

Deterministic and Non-Deterministic Basis Reduction Techniques
for NTRU Lattices

Daniel Socek

Abstract.  Finding the shortest or a "short enough" vector in an integral lattice of substantial dimension is a difficult problem. The problem is not known to be NP-hard but most people believe it is.  The security of newly proposed NTRU cryptosystem solely depends on this fact. However, by virtue of its definition, NTRU lattices possess a certain symmetry.  This suggests that there may be a way of taking advantage of this symmetry to enable a new cryptanalytical approach in combination with existing good lattice reduction algorithms. We designed a method for
reducing bases of integral lattices with non-trivial automorphisms.  Our method combines deterministic and non-deterministic components and it can be parallelized.

Tuesday, November 5, 2002, at 10 a.m. in S&E 215

Galois Action on the Algebraic Integers

Dr. Griff Elder
(University of Nebraska at Omaha)

Tuesday, October 29, 2002, at 2 p.m. in S&E 215

Some Trends in Algebra, part 2

Markus Schmidmeier

Tuesday, October 22, 2002, at 2 p.m. in S&E 215

Some Trends in Algebra

Markus Schmidmeier

Last weekend, Lee Klingler and I had attended the Southern Weekend Algebra Conference at the University of Lousiana at Lafayette.  At this meeting, Lee and I have proposed that the next conference in this series
will take place here in Boca, probably in October 2003.

In my lecture I will review some of the results presented to the Lafayette meeting.

Tuesday, October 15, 2002, at 2 p.m. in S&E 215

Modules which are Complemented
with Respect to a Torsion Theory

Jorge Viola-Prioli

Abstract.  The analysis of when complemented  submodules are direct summands has produced a great deal of results, some of them surprising given the different structural nature of the modules that satisfy the required property.  Although the vast literature shows this is an area of importance in itself, the introduction of Torsion Theories in the subject has proved enriching; I will indicate why.  (This stems from joint work with P. Smith (UK) and Ana Viola-Prioli, and more recently, an article by the latter author and myself.)

Tuesday, October 1, 2002, at 11 S&E 215

On Covering Arrays

Ms. Sosina Martirosyan

Abstract. A covering array  CA(N;t,k,v)  of size  N ,  strength  t , degree  k , and order   v   is  a  k x N   array  on   v  symbols such that every   t x N  subarray contains each  t x 1  column on   v   symbols at least once.   Applications of covering arrays include software testing, drug screening, and data compression.

We present  a constructive upper bound for the size of  covering arrays of strength 4.  We generalize  Roux's  Theorem to this case; the original result for binary covering arrays of strength 3 has been generalized by   Chateauneuf and Kreher for any alphabet  size  v . We also present an idea for generalizing the construction method for any strength  t ,  this is work currently under way.  Finally, a relationship  between Perfect Hashing Families  and  Covering Arrays  will  be presented.

Tuesday, September 24, 2002, 2 p.m. in S&E 215

 Finitely Generated Modules over the Ring of Integer Quaternions

Lee Klingler

Abstract.  It is well known that the ring R = Z[i,j,k] of integer quaternions is not a maximal Z-order in the division algebra Q[i,j,k] of rational quaternions, but adjoining to R the element (1+i+j+k)/2 yields a maximal Z-order S which is in fact a (noncommutative) PID.  The conductor ideal is C = S(1+i), where R/C and S/C are fields of 2 and 4 elements, respectively.  Thus, R is a noncommutative version of the unsplit Dedekind-like rings studied by L. Levy and myself in recent joint work.

In this talk, I shall show how to adapt our methods from the commutative context to this noncommutative situation, in order to describe all isomorphism classes of finitely generated modules over the ring R of integer quaternions.

Tuesday, September 17, 2002, 11 a.m., in S&E 215

Why study subgroups of  p^6 -bounded finite abelian groups ?

Markus Schmidmeier

Abstract.  For  n<6, the possible embeddings of a subgroup in a  p^n -bounded finite abelian groups have been classified by Hunter, Richman, and Walker (1984) and by Richman and Walker (1999).

The cases   n<6   being settled, one obvious reason for studying the category  S(6)  of subgroups of p^6 -bounded groups mentioned in the title is that it is the next category of interest.  It is the aim of my talk to describe four more reasons, each even better than this.

Consider the sequence of embeddings,

                   S(1)    --->     S(2)     --->         ...       --->      S(6)       --->         ...

clearly, the union of this sequence consists of all possible embeddings  of a subgroup in a finite abelian  p-group.  In my talk I hope to convince you that within this sequence,   S(6)  sits in fact at the most distinguished position.

Tuesday, September 10, 2002, 2 p.m. in S&E 215

PRIMES is in P

Fred Richman

Abstract.  "PRIMES is in P" is the title of a recent paper by Agrawal, Kayal and Saxena. Their abstract reads: "We present a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite." The paper settles a question that had been around for some time.

PRIMES is the problem of determining whether an input number is prime or composite (but not necessarily factoring a composite). P is the class of problems that can be solved by an algorithm in "polynomial time". The running time of the authors' algorithm is bounded by a constant times the twelfth power of the number of digits in the input number.

Tuesday, September 3, 2002, 2 p.m. in S&E 215

Integrally Closed Domains and Minimal Polynomials of Matrices

James Brewer

Last modified:  , by Markus Schmidmeier