Home    :    Projects    :    Software    :    Schedule    :    REU Alumni    :    Publications    :    FAQ    :    Links
2012 Research Projects   |   2013 Research Projects   |   2014 Research Projects   |   2015 Research Projects

2011 Research Projects

 

DES over finite groups

The Data Encryption Standard is a symmetric key encryption standard published by the NIST in 1975. DES and several analogous symmetric-key encryption algorithms transform a fixed-length 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 DES-like 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 non-commutative 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)