DES over finite groups
The Data Encryption Standard is a symmetric key encryption standard published by the NIST
in 1975. DES and several analogous symmetrickey encryption algorithms transform a fixedlength
block of plaintext into a block of ciphertext of the same length. Some users of DES are the
BlackBerry Enterprise, Microsoft Outlook and the whole electronic payment industry. There is
strong relationship between algebraic and security properties of a cryptosystem. Several problems
about DESlike algorithms related to their algebraic structure are either unsolved or until
now had very labor intensive technical solutions. The question whether DES is a group is crucial
for its security and it has been solved only for DES over Z_2. We proved that DES over finite
groups is not a group which solves this open problem in general. We showed that DES over
finite groups can generate either the alternating group or a subgroup of the symmetric group
which solves another open problem in general. For educational purposes we designed the first
simplified version of DES over elliptic curve group.
L. Babinkostova, A. M. Bowden, A. M. Kimball, K. J. Williams, A simplified and generalized treatment of DES related ciphers,
Cryptologia (submitted)
arXiv:1205.5613
Conjugacy problem  Theory and Applications
At the center of a crypto system is a mathematical trapdoor, that is, a computational problem
that is easy to do in one direction (encryption) but hard to reverse (decryption). A good example
is integer multiplication: it is easy to multiply two numbers,but hard to factor a given number.
The security of classical crypto systems based on number factoring and related problems has various
weaknesses. Mathematicians search for trapdoors that involve computations in noncommutative
structures that provide more security in crypto systems. One such problem is the conjugacy
problem in group theory. For our project we investigate the conjugacy problem for the braid group.
No efficient algorithm is known for the solution of this problem. We investigate the complexity
of the known algorithms, one due to Garside, the other due to Thurston, and show that there are
algorithms to solve the conjugacy problem in the braid group on three strands
efficiently.
J. Harlander, H. Lewis, J. Siegel and C. Xu, The Conjugacy Problem in
Group Theory [Manuscript]
Mathematics and Genome remodeling
The genome sorting techniques used by hypotrichous ciliates determine a sorting distance between
the permuted genomes of species of fruitflies. We proved that the ciliate sorting algorithm successfully
sorts any given finite permutation back to the canonical (1,2,...,m) state, and that the complexity of
the algorithm is O(m^3). The ciliate sorting algorithm was implemented in Python. With one exception we
found an intriguing positive correlation between the published evolutionary distances among these species
and the number of applications of one of the three sorting operations used by the ciliate sorting mechanism.
J. Herlin, A. Nelson and M.Scheepers, Can ciliates compute
evolutionary distance? (arXiv:1210.0234)
