The projects we offer at REU CAD are hard and at the same time easy. They seem deceptively easy because the fundamentals of the problems are so familiar. After all, you have probably solved a cryptogram or a sudoku; you have probably played games and worked out a strategy to help you win; you have probably had your computer check a message or storage drive for errors. But these types of problems have become much more elaborate in the last half century because they are so central to our modern computer based society. The underlying problems in the REU CAD projects are easy to state and understand, but the technical mechanisms we use to solve them are challenging to build and make broadly applicable. The projects all belong to fast growing mathematical fields. As we are writing the description of the projects for this year's REU CAD we are reading about new sorting algorithms new cryptographic schemas, and new techniques to improve search algorithms. These new results are based on mathematical problems from algebra, combinatorics, number theory, and so on. The challenges might
seem very tough indeed, but remember that one feature of the program is collaboration and team work. And that is one big reason why the problems are also easy.
Number Theory, Elliptic Curves and Cryptography
Mentored by Dr. Liljana Babinkostova
In the 10 minutes it takes you to read the description of this project, the amount of data being generated by the humans will have expanded by more than 10 petabytes, equivalent to about one third of all written works from the beginning of recorded history in all languages. Currently less than a third of the world's data is properly protected. Data must be protected by making sure that (1) ``you really are who you say you are" when you do online shopping or registering for classes, (2) the data is not lost or leaked, and (3) the critical data can not be recovered by adversaries. The use of cryptographic techniques are one of the key components in data protection. However, encryption by itself does not provide security, it only ensures the confidentiality of data exchanges and authenticity through proper use. To be effective, it must be part of a comprehensive process of analysis to ensure information security.
All cryptographic techniques use problems that are computationally hard and mathematics is the essential source for such hard problems. However, academic advances on instances of some of these problems suggest that some current cryptosystems could be undermined in just a decade. One of the pillars of this project's approach to sustainable cryptography is the pursuit of generalizing these computationally hard problems to an abstract class of group-theoretic or combinatorial problems. Besides being of interest in its own right, this generalization opens the way to a new approach for basing cryptography on combinatorial group theory.
In prior REU research it was proven that for certain AES based cryptosystems the only groups generated by the set of encryption functions are the symmetric and the alternating group. These results answer the question whether multiple encryptions can improve the security of the crypto system and provide a method of more efficiently analyzing whether certain hash functions are collision- or preimage- resistant.
However, while these results completely answer the question for one class of cryptosystems, for others this approach assumed that certain permutations deployed in their basic construction are ``ideal". The question of how "ideal" these permutations really are leads to very interesting combinatorial problems, including counting the number of transversals in a Cayley table over the additive group of a finite field. During prior REU research the number of so-called partial transversals in such a Cayley tables has been determined.
Also, in prior REU work the algebraic structure and properties of a certain class of elliptic curve groups has been investigated - a question of importance in public key cryptography and in pairing based cryptography. Namely, it was shown that under certain conditions there are infinitely many primes of special form that could produce elliptic curves of prime order. However, this is just one finding. Much is left to be discovered.
In these projects you will learn how to use various mathematical tools, including number theory, group theory, and the combinatorics of permutations. The research also gives an opportunity to get involved in code writing with the purpose of analyzing data in attempts to prove conjectures.
L. Babinkostova at al., A simplified and generalized treatment of DES related ciphers (2014)
L. Babinkostova at al., Algebraic Properties of Generalized Rijndael-like Ciphers (2015)
G. C. Kessler, An Overview of Cryptography (2014)
The Combinatorics of Separating and Splitting Families
Mentored by Samuel Coskey
It is a common situation to have to find one faulty item in a group of many: consider the examples of a sick cow in a herd, a false coin in a roll, or a blown conductor in a circuit. This project aims to study the nature of separating separating families and splitting families (also called systems), which are combinatorial gadgets that can help one to cut down the size of a search space. These gadgets arise in a wide variety of applications including combinatorial search as mentioned above, and also coding theory, cryptography, and more. Thus while the subject lies primarily in pure combinatorics, we will also be able to explore many connections with these other fields.
One of the primary types of questions we wish to investigate is that of finding examples of such families which are small enough to be useful, and more generally to find lower and upper bounds on their sizes. The most recent group of REU researchers studied minimal separating families, that is, families which cease to be separating after one element is removed. While they were able to find some upper bounds on such families, their experimental evidence led them to conjecture that much tighter bounds should be achieved.
A second type of investigation is to discover our own new variants on these notions, and explore their properties and applications. Another team of REU researchers defined the notions of n-separating and n-splitting families, that is, families capable of separating or splitting several sets at once. They were able to find lower and upper bounds on the least size of such a family when n≤3, but left many questions open for larger n. They also asked how one can distinguish splittable from unsplittable configurations.
In the course of our work you will have the opportunity to learn and use a variety of tools such as the probabilistic method, Polya enumeration theory, computational complexity theory, and graph theory. Those who wish will also have the opportunity to contribute by writing code to explore examples and generate experimental data. The possibilities are endless but all roads lead to fun!
D. Condon, S. Coskey, L. Serafin, and C. Stockdale, On generalizations of separating and splitting families (2014)
G. O. H. Katona, Combinatorial search problems (1973)
D. L. Stinson, Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem (1999)
Sorting, Graphs and Games
Mentored by Marion Scheepers
With the dramatic growth of "big data" the need for efficient search methods is as great as ever. The fundamental step in making large data sets searchable is to organize the data items in a useful way. This organizing step is called sorting. In our modern computing based civilization a significant portion of our resources is spent on sorting. Large scale sorting and its importance is not a new phenomenon, and not even only a human activity. Nearly 35 years ago biologists discovered that in certain single cell organisms, ciliates, large scale sorting routinely occurs at genome level. The survival of these species depends on the accuracy and the efficiency of their native sorting technology. According to the current model the native ciliate sorting algorithm relies on two specific sorting operations, call them A and B. The operations A and B have been studied by mathematicians before the discovery that A and B have been at work for billions of years in a natural system. This new context for operations A and B raises interesting questions that are of independent mathematical interest.
In the projects inspired by these two sorting operations the focus is on the robustness, eficiency and limitations of these two operations in accomplishing successful sorting. In prior REU research it was proven, for sorting operation A, that if a permutation is sortable by it, then indiscriminate applications of sorting operation A will succeed in sorting that permutation. However, for sorting operation B this is far from true: there are signed permutations sortable by B, but not all applications of B lead to a successful sorting. During REU research it has been proven that sorting operation A comes to the rescue by sorting the result of failed attempts of operation B.
The question of how prevalent are signed permutations sortable by operation A or operation B leads to the investigation of the structure of the set of signed permutations, when classified according to their sortability by A or B. A very interesting mathematical structure is emerging, leading to a deeper understanding of the mathematical power of sorting operations A and B. For example: Investigation of reasons for failure of sorting operations A or B reveals that there are several ways in which a sorting attempt can fail. This phenomenon inspires an analysis by means of games. The corresponding game theoretic problems are of independent interest. Prior REU work identified one general scenario under which one of the two players has a winning strategy, and proved that the result is optimal for this scenario. But, that is just one scenario. Much more is to be discovered.
In these projects you will learn how to use various mathematical tools, including graph theory, game theory, and the combinatorics of permutations, to analyze sorting related problems. Although the notions under study arose in a different scientific field, the focus of the work is on mathematical structure.
K. Adamyk at al., Sorting Permutation: Games, Genomes and Cycles (2013)
C.L. Jansen at al., Permutation sorting and a game on graphs (2014)
A.N. Siegel, Combinatorial Game Theory (2013)