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.
The focus of the REU CAD 2015 research projects are mathematical problems that have applications to analysis and design of information protection strategies, analysis of sorting strategies occurring in natural processes, and the analysis of search strategies. During the program the students wil also have opportunities to work on the their projects with the invited speakers and REU alumni visiting the REU site.
Professor Babinkostova's Research Groups
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. Students working with Dr. Babinkostova will learn about various techniques used in determining the resilience of cryptographic tools against algebraic attacks. This research routinely leads to mathematical problems about number theory, algebra or combinatorics. Following are two potential research projects:
Generalizations of Cryptographic and Hashing Schemes and Their Security
Kaliski, Rivest and Sherman in their paper from 1998 asked several algebraic questions related to the DES cryptosystem, such as: Does the set of DES encryptions functions forms a group? What is the order of the group generated by the set of DES encryption functions? What subsets of DES encryption functions generate small groups? How many distinct permutations are represented by the DES keys? These questions are of importance to the security of any cryptosystem, not just DES. Some of the questions are still open, even for the DES cryptosystem. Recently Babinkostova and her students were able to generalize certain type of cryptosystems and hash functions and answer some of the questions in general. Students working on this project would attempt to extend these results for a wider (new) class of cryptosystems that includes the previous studied types of cryptosystems and hash functions.
Efficient search techniques have clear benefits for the party doing the search. But there is also interest in making things hard to find - an adversary is strategically intervening in communication between two points, aiming to find classified information. In 2001 Babinkostova and Scheepers introduced a game on finite groups that encapsulates an
adaptive chosen ciphertext attack against some cryptosystems, including El-Gamal and RSA type cryptosystems. Students working on this project would study the computational complexity of this game and attempt to extend previous results by considering more general classes of groups.
L. Babinkostova at al., A simplified and generalized treatment of DES related ciphers, Cryptologia (2014) (accepted)
L. Babinkostova at al., Algebraic Properties of Generalized Rijndael-like Ciphers, Groups-Complexity-Cryptography (2013) (accepted)
G. C. Kessler, An Overview of Cryptography (2014)
Professor Scheepers's Research Groups
Sorting occurs ubiquitously in nature, in laboratories and in everyday activities. The capabilities of a sorting technology has profound impact on what patterns are successfully sortable, and what sorting strategies are most economical. Students working with Dr. Scheepers will learn about techniques used to analyze sortability related problems. This research routinely leads to mathematical problems about graphs, games and various combinatorics. Following are two potential research projects:
Sorting with Restrictions
In a 2003 paper Ehrenfeucht, Prescott and Rozenberg proposed a model by which certain single cell organisms, ciliates, use two simple sorting operations to decrypt encrypted copies of their genes. The ciliate sorting mechanism is of fundamental interest as it is programmable, and evidence suggests that it has significant computational power. Nevertheless, for either of these two proposed sorting operations some patterns are not decryptable. Even among patterns decryptable by one of these operations, not all sorting strategies accomplish decryption. Scheepers and his REU teams have mathematically characterized the patterns that are sortable by either of these two operations, and introduced several two-player games to investigate strategic aspects of sorting by these operations. By a classical theorem of Zermelo in any of these games one of the players has a winning strategy. One fundamental problem is to find criteria by which to efficiently decide which player has a winning strategy. Another problem is to identify winning strategies. The summer research team will engage in such problems for several games, including games communicated to Scheepers by the late Paul Erdos.
Combinatorial Search Games
Searches often aim to identify any one of several objects that satisfy the search objective, using a minimal number of search steps. Very little work has been done on the extent to manipulating the search steps affect the search outcome. One approach to investigating this aspect of a search technique is to make the search competitive, with two players alternately performing the search-steps. The winner is determined by the outcome of the search. This new class of games will be examined for a specific set of popular combinatorial search techniques.
K. Adamyk at al., Sorting Permutation: Games, Genomes and Cycles, (arXiv 1410.2353)
C.L. Jansen at al., Permutation sorting and a game on graphs, (arXiv 1411.5429)
A.N. Siegel, Combinatorial Game Theory, American Mathematical Society, (2013)