All students interested in combinatorics, algebra, game theory, number theory, crytography or set theory are encouraged to apply. The projects may involve both theoretical study and computer experimentation. Students with strong programming background are encouraged to apply, but such background is not required. Students will be expected to have basic knowledge in discrete mathametics and combinatorics.
A bridge between several worlds: Cryptography
Mentored by Dr.
Liljana Babinkostova
Cryptography is naturally a multidisciplinary field, drawing techniques from a
wide range of disciplines and connecting to many different subject areas. Cryptography requires problems that are computationally hard to achieve information security objectives in a world that is ever more information based. Mathematics
is the essential source for such hard problems. Although the instances of
such problems that serve as platform for current commercially deployed cryptosystems
are known by experience to be hard, none of them has been proven to be hard. Indeed, academic advances
on the instances of some of these problems suggest that some of these cryptosystems could be undermined in just
a decade. Algebraic attacks on stream/block ciphers is a recent and a very powerful type of attack. In our previous REU research we successfully investigated new platforms for symmetric key cryptography, thus opening several new lines of ongoing investigation. We continue this investigation by studying the algebraic structure of some AESbased stream cipher and hash functions and their security.
References
L. Babinkostova at al., A simplified and generalized treatment of DES related ciphers, Cryptologia (to appear)
L. Babinkostova at al., Algebraic Properties of Generalized Rijndaellike Ciphers,Groups Complexity Cryptology, Vol. 6 (1), 3754 (2014).
G. C. Kessler, An Overview of Cryptography (2014)
Combinatorial search and separating families
Mentored by Dr. Samuel Coskey
In this project we will tackle questions that arise in group testing, where one seeks to find one special item in a collection such as a counterfeit coin. Group testing is part of an area of mathematics known as combinatorial search, which has applications in almost every scientific discipline. For example, it has been recently used in medical, chemical and electrical testing, as well as crypotgraphy and error correction. Combinatorial search can be done with many different mathematical models, including discrete to probabilistic ones. We will be primarily interested in finding and studying special configurations that help one decide how to cut down the size of a search space (socalled separating families, splitting families, and variants of these). Our main goals are to find ways to generate examples of these configurations, and therefore to give bounds on their sizes and complexities. A further goal is to seek new applications of our findings to the algorithms used in cryptography. Finally, we may also study the infinitary counterparts to separating families, something that will take us to the crossroads of combinatorics, computation, and set theory.
References
G. O. H. Katona, Combinatorial search problems, A Survey of combinatorial theory, NorthHolland, Amsterdam, pp. 285–308 (1973).
A. C. H. Ling, P. C. Li, and G. H. J. van Rees, Splitting systems and separating systems, Discrete Mathematics, 279(13) pp. 355–368 (2004).
Genomes and Sorting Problems
Mentored by Dr.Marion Scheepers
Sorting problems with prescribed sorting operations abound in nature, science, technology, and everyday tasks. Decision and search aspects of these sorting problems often lead to mathematical problems that are known to be inherently difficult. These inherent difficulties are often exploited for various security objectives. We will use a game theoretic approach to analyze a new class of problems of this kind in finite mathematical structures. Game theory provides natural ways in which to introduce mathematical techniques developed for other purposes into the arena of this class of problems. Students will be immersed in the fundamentals of game theory while doing research on this class of problems. Mathematical findings on these problems may shed some light on the quality of sorting processes occurring in nature.
References
C.L. Jansen, M. Scheepers, S.L. Simon and E. Tatum, Permutation sorting and a game on graphs, arXiv:1411.5429
K.L.M. Adamyk, E. Holmes, G. Mayfield, D.J. Moritz, M. Scheepers, and H.C. Wauck, Sorting permutations: Games, Genomes and Graphs, arXiv1410.2353
R. Brijder, Models of Natural Computation: Gene Assembly and Membrane Systems (2008)
