Higher-Order CIS Codes.

We introduce complementary information set codes of higher order. A binary linear code of length \(tk\) and dimension \(k\) is called a complementary information set code of order \(t\) ( \(t\) -CIS code for short) if it has \(t\) pairwise disjoint information sets. The duals of such codes permit to reduce the cost of masking cryptographic algorithms against side-channel attacks. As in the case of codes for error correction, given the length and the dimension of a \(t\) -CIS code, we look for the highest possible minimum distance. In this paper, this new class of codes is investigated. The existence of good long CIS codes of order 3 is derived by a counting argument. General constructions based on cyclic and quasi-cyclic codes and on the building up construction are given. A formula similar to a mass formula is given. A classification of 3-CIS codes of length \(\le 12\) is given. Nonlinear codes better than linear codes are derived by taking binary images of \( {\mathbb Z}_{4}\) -codes. A general algorithm based on Edmonds’ basis packing algorithm from matroid theory is developed with the following property: given a binary linear code of rate \(1/t\) , it either provides \(t\) disjoint information sets or proves that the code is not \(t\) -CIS. Using this algorithm, all optimal or best known \([tk, k]\) codes, where \(t=3, 4, {\dots }, 256\) and \(1 \le k \le \lfloor 256/t \rfloor \) are shown to be \(t\) -CIS for all such \(k\) and \(t\) , except for \(t=3\) with \(k=44\) and \(t=4\) with \(k=37\) . [ABSTRACT FROM AUTHOR]