Risc Colloquium

Abstract:
In last 50 years, combinatorial designs have had profound applications in coding theory, cryptology, networking and computer science. Combinatorial designs  are the branch of discrete mathematics dealing with the study of sets and their elements that exhibit certain intersection properties. Various classes of combinatorial designs, such as block designs or geometric t-designs over finite fields, appear in various disguises in cryptology, error correcting codes, and the theory of algorithms. Yet, applications of combinatorial designs to computer science continue to arise, and it comes as no surprise that in particular the field of information security provides a rich source of problems that seek solutions (also) from discrete mathematics.
In this talk, we will consider a number of research challenges coming from information security, where the interaction with discrete mathematics, and in particular combinatorial designs, is substantial.
 * The problem of efficient test generation when software or hardware defects that can trigger security vulnerabilities depend on a small number of parameters is in general NP-hard. Therefore, seeking theoretical and algorithmic solutions to this problem from the field of discrete mathematics is a challenging task.
 * The challenge of deriving accurate models of software systems and designing efficient security testing methods considerably reducing the amount of resources needed with mathematical levels of trustworthiness in the evaluation results.
 * Novel research efforts in discrete mathematics are also needed w.r.t. theoretical computer virology and concern the problem of characterization and detection of unforeseen families of computer viruses.
 * The development of the necessary mathematical foundations to withstand cryptographic attacks when these are carried out by quantum computers.
For each one of the previous challenges, asides discussing past work of ours we will highlight the most important open research problems and bridge discrete mathematics with symbolic computation and rewriting techniques, where applicable.