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 Theoretic and Algebraic Aspects of 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. Also, we generalized certain notions of elliptic pseudoprimes and elliptic Carmichael numbers to analogues of Euler-Jacobi and strong pseudoprimes and investigated their relationships. However, 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., On Types of Elliptic Pseudoprimes (2017)
L. Babinkostova at al., Anomalous Primes and the Elliptic Korselt Criterion (2016)
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
The concept of set splitting figures prominently in a number of research areas of pure and applied combinatorics such as cryptography, coding theory, discrepancy theory, and integer linear programming. Over the course of our project we will have the opportunity to learn and use a variety of mathematical methods, such as enumerations and asymptotics, the probabilistic method, graph colorings, and computational complexity theory. Students who wish to will have the opportunity to contribute by writing code to explore examples and generate conjectures.
The definition of set splitting is simple: The set A splits the set B if and only if A contains exactly half the elements of B. (If B has an odd number of elements, "half" really means "half rounded up or down.") This concept leads to two types of gadgets that will occupy most of our study, which are called splitting families and splittable families.
A splitting family is a collection of sets which together suffices to split any given set. Splitting families aid in search algorithms because the splitters help cut down on the size of a search space. Since they are useful, it is perhaps surprising that the optimal size splitting family is still poorly understood.
A group of REU students gave generic lower and upper bounds on the size of a splitting family, but the bounds are far from tight. Is the upper bound optimal? Is the lower bound optimal? Or is the answer somewhere in between?
The dual notion of a splittable family refers to a collection of sets which can all be split by a single set. The splittable families are highly uniform and represent configurations for which certain algorithms run the most efficiently.
A group of REU students showed that it is NP-complete to decide whether a given family is splittable or not. However many small modifications of this question are still unknown. For example, is it NP-complete to decide whether a given collection is nearly splittable, in the sense that it has small discrepancy? And if a given family is splittable, what is the algorithmic complexity of finding a splitter?
Studying these problems gives students the opportunity to experience combinatorial research and many key facets of mathematical investigation. There are a lot of deep mysteries involved, but there are many roads to progress and we always have a lot of fun along our way.
P. Bernstein, C. Bortner, S. Coskey, S. Li, and C. Simpson. The set splittability problem (2016)
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)
Game Theory and Sorting Algorithms
Mentored by Marion Scheepers
With the dramatic growth of "big data" the need for ecient 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 signicant portion of our resources are 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 and the survival of these species depends on the accuracy and the efciency 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 raise 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 classied 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 identied 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)