Grant: Discovery Grants Program - Individual
Carleton University
$24,000.00
Combinatorial Arrays
FY 2018-19
Summary
I am interested in the mathematics of finite systems of sets that have interest theoretically and have applications to industrial processes. I am proposing research on objects that can be represented as a two-dimensional array of symbols and have the property that when a small set of columns are chosen every possible row appears somewhere. These arrays have beautiful connections to geometry, the mathematics of rigid structure and to topology, the mathematics of plastic structure. The applications vary widely from reliability testing of software and circuits, optimizing welding design and cryptography.*For reliability testing and welding design the rows of an array are used to determine real tests that are run on software or trial welds for example. The column property of the arrays guarantees that the data gathered from these tests detects faults in the software or tells us about the stress impact of one weld on another. I am interested in taking the constraints and needs of the engineers and translating them into new mathematical objects. I then use algebraic and combinatorial tools to understand how small and what structure these objects must have to construct examples that can be used in practice. I am proposing research on the structures that result when we know that not all the combinations of test parameters matter so we can save time by not testing them. I am also interested in mathematically determining the best order to run the tests to be more efficient in practice. Finally the welding application requires that no symbols appear more than once in a row because you cannot weld the same part twice. One exciting aspect is that these constraints from the practical application result in beautiful mathematics as well as enhance the application.*In cryptography rows are thought of as maps rather than tests to be run. Many of the attacks on cryptosystems rely on correlations between the unencrypted and encrypted version of a message. Many ciphers contain ""substitution boxes"" that attempt to break these correlations to make the system resilient to attack. The properties required for resilience turn out to be very similar to the properties required for test runs. In most cryptosystems these s-boxes are constructed from an algebraic object called group which comes from a finite field. Finite fields are beautiful objects which have addition, multiplication and division but behave differently than familiar numbers and groups only have addition and subtraction. In my previous NSERC supported research I showed that using different groups has the potential to be more resilient to attack and constructed some s-boxes which were provably optimal. I am proposing to extend this research to construct more s-boxes and prove that they have all the properties required for use.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2017-06392
Name nom
stevens, brett
Department département
Mathematics and Statistics, School of
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2017
Award amount
24000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
2
Nb partie
5
Application title
Combinatorial Arrays
Keyword
NSERC
Application summary
I am interested in the mathematics of finite systems of sets that have interest theoretically and have applications to industrial processes. I am proposing research on objects that can be represented as a two-dimensional array of symbols and have the property that when a small set of columns are chosen every possible row appears somewhere. These arrays have beautiful connections to geometry, the mathematics of rigid structure and to topology, the mathematics of plastic structure. The applications vary widely from reliability testing of software and circuits, optimizing welding design and cryptography.*For reliability testing and welding design the rows of an array are used to determine real tests that are run on software or trial welds for example. The column property of the arrays guarantees that the data gathered from these tests detects faults in the software or tells us about the stress impact of one weld on another. I am interested in taking the constraints and needs of the engineers and translating them into new mathematical objects. I then use algebraic and combinatorial tools to understand how small and what structure these objects must have to construct examples that can be used in practice. I am proposing research on the structures that result when we know that not all the combinations of test parameters matter so we can save time by not testing them. I am also interested in mathematically determining the best order to run the tests to be more efficient in practice. Finally the welding application requires that no symbols appear more than once in a row because you cannot weld the same part twice. One exciting aspect is that these constraints from the practical application result in beautiful mathematics as well as enhance the application.*In cryptography rows are thought of as maps rather than tests to be run. Many of the attacks on cryptosystems rely on correlations between the unencrypted and encrypted version of a message. Many ciphers contain ""substitution boxes"" that attempt to break these correlations to make the system resilient to attack. The properties required for resilience turn out to be very similar to the properties required for test runs. In most cryptosystems these s-boxes are constructed from an algebraic object called group which comes from a finite field. Finite fields are beautiful objects which have addition, multiplication and division but behave differently than familiar numbers and groups only have addition and subtraction. In my previous NSERC supported research I showed that using different groups has the potential to be more resilient to attack and constructed some s-boxes which were provably optimal. I am proposing to extend this research to construct more s-boxes and prove that they have all the properties required for use.