13. April 2023
Prof. Michael Fellows
Combinatorial Cryptosystems Galore, for All Times!
The talk will tell the entertaining story of how an effort to explain modern algebraic public key cryptosystems to ten year olds, as part of the Computer Science Unplugged! Project led to an entirely new branch of modern cryptography that has proven to be of sustained interest, because of the possible immunity of combinatorial-algebraic (CA) cryptosystems to quantum attack.
The first "Kid Kryptosystem" was based on the NP-hard graph problem of PERFECT CODES IN GRAPHS. This cryptosystem turns out to be crackable by a linear system of n equations in n unknowns, and thus is only secure up through high school. However, it can be algebraically tweaked and developed into a CA system that might be of industrial-strength, and this has become a branch of modern cryptography research, that is now also known as Groebner bases cryptosystems.
One suspects that every NP-hard problem (and there are a galore of them) should lead in a fairly natural way to a distinct kid kryptosystem, but so far only two of them have been known, with the other based on the NP-hard problem of DIRECTED CYCLE COVER of digraphs.
The entire area is rich with possibilities for research projects that are probably of some interest to security agencies nowadays, such as the venerable NSA. The talk will try to highlight some of these intriguing directions that could be very fine for Masters Projects, and report on some new ways of tweaking these cryptosystems to make them harder to crack.
Joint work with Frances Rosamond.