Parallel programs for autocorrelation problems (PAAP)
Ilias Kotsireas, Wilfrid Laurier University
Maplesoft and IBM Canada Ltd.
SOSCIP, IBM Canada Ltd.
According to IBM, more than 2.5 billion gigabytes of digital data is generated every day. This includes emails, text messages, voice and video data and other types of digital information. Keeping this information secure costs companies and governments billions every year and relies on talent, determination and supercomputers.
At Wilfrid Laurier, Prof. Ilias Kotsireas is conducting research to build the cryptographic infrastructure needed to keep data secure. His research involves searching for particular sequences that have ideal characteristics with respect to their autocorrelation values. Autocorrelation is a measure of how similar a sequence is with itself. Where sequences of specific lengths are not known to exist via known theoretical construction methods, the only way to find them is to employ computational algorithms.
“People are interested in these sequences because their existence has consequences and implications for security,” explained Prof. Kotsireas, who is director of the Computer Algebra Research Group at Laurier.
“Using Canada’s fastest computer will allow Dr. Kotsireas to make important progress in the area of combinatorial designs,” said Dr. Robert Gordon, vice president, research, Wilfrid Laurier. “We are delighted to support partnerships such as SOSCIP to support his innovative work.”
Through the BGQ, algorithms have exhibited a 2000-fold speedup, which considerably increases the speed and efficiency of Prof. Kotsireas’ research. He has developed highly parallelized code and was able to use all BGQ’s 65,536 cores in a single run.
“Metaprogramming is a reliable technique to produce bug-free millions of lines of C code that go into the project,” said Prof. Kotsireas, adding that these problems will be useful in designing cryptographic protocols. “The adversary would have to perform exhaustive searches which could take even automated code breakers forever.”
“You have to think of the adversary as someone with infinite resources and infinite time.”
Indeed, he admits the security of cryptosystems has become a very active and competitive area of research, but one that has been nurtured by mentors, Prof. Dragomir Djokovic, his main collaborator, and Prof. Jennifer Seberry, the “Mother of Cryptology” in Australia.
Prof. Kotsireas is seeking to acheive the solution of the famous open problem, the construction of a Hadamard matrix of order 686 (pictured).