Abstract | ||
---|---|---|
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 ≤ 12 is given. Nonlinear codes better than linear codes are derived by taking binary images of Z4-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, . . . , 256 and 1≤ k ≤⌊256/t⌋ 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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/TIT.2014.2332468 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
( {mathbb z}_{4}) -linear codes,3-cis code classification,cyclic codes,cryptography,linear codes,dual distance,matroid theory,side channel attacks,quasi-cyclic codes,higher order cis codes,matrix algebra,pairwise disjoint information sets,set theory,complementary information set,error correction codes,masking scheme,higher order statistics,cryptographic algorithm,z4-linear code,edmonds basis packing algorithm,binary codes,binary linear code,boolean functions,cost reduction | Journal | 60 |
Issue | ISSN | Citations |
9 | 0018-9448 | 5 |
PageRank | References | Authors |
0.49 | 18 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Claude Carlet | 1 | 2925 | 226.81 |
Finley Freibert | 2 | 6 | 1.86 |
Sylvain Guilley | 3 | 214 | 15.47 |
Michael Kiermaier | 4 | 7 | 0.90 |
Jon-Lark Kim | 5 | 312 | 34.62 |
Patrick Solé | 6 | 636 | 89.68 |