Department of Mathematics, University of Louisville, Louisville, KY, USA
We introduce a new class of rate one half codes, called complementary information set codes. A binary linear code of length 2n and dimension n is called a complementary information set code (CIS code for short) if it has two disjoint information sets. This class of codes contains self-dual codes as a subclass. It is connected to graph correlation immune functions of use in the security of hardware implementations of cryptographic primitives. In this talk, we give optimal or best known CIS codes of length <132. We derive general constructions based on cyclic codes, double circulant codes, strongly regular graphs, and doubly regular tournaments. We derive a Varshamov-Gilbert bound for long CIS codes, and show that they can all be classified in small lengths up to 12 by the building up construction. This is a joint work with Claude Carlet, Philippe Gaborit, and Patrick Sole.