Calendar Site

Loading Events

« All Events

  • This event has passed.

Kid Krypto – encryption systems based on NP-hard problems

November 4, 2017 @ 11:00 am - 12:00 pm

The talk will describe how easily understood, but NP-hard combinatorial problems, can serve as the basis for a Kid Krypto public key crypto system (PKCS). There have been only two such constructions so far. The most known is Perfect Code Kid Crypto, which is described in Computer Science Unplugged ( Both Perfect Code and the new and unpublished Directed Cycle Cover based Kid Krypto PKCSs can be cracked with linear algebra—but this still leaves them appropriate for young audiences in the general project of communicating contemporary mathematical science, an important project that will be touched upon.

A general project is how to turn any NP-hard problem into a Kid Krypto system. The DIRECTED CYCLE COVER (DCC) problem asks, for input a digraph D = {V, A} whether there exists a family F = {C1, …, Cm} vertex-disjoint directed cycles that “spans D”, that is, for every v in V there is a unique directed cycle of F that passes through V. This is an NP-hard problem.


November 4, 2017
11:00 am - 12:00 pm
Event Category: