Higher-Order CIS Codes

DOI10.1109/TIT.2014.2332468zbMATH Open1360.94362arXiv1406.4547OpenAlexW2000812559MaRDI QIDQ2986146FDOQ2986146

Finley Freibert, Sylvain Guilley, Jon-Lark Kim, Michael Kiermaier, Patrick Solé, Claude Carlet

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We introduce {�f 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 $le12$ is given. Nonlinear codes better than linear codes are derived by taking binary images of $$-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 $1leklelfloor256/tfloor$ 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$.

Full work available at URL: https://arxiv.org/abs/1406.4547

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Cited In (4)

• Long quasi-polycyclic \(t\)-CIS codes
• Complementary information set codes over \(\mathrm{GF}(p)\)
• CIS codes over ${\mathbb F}_4$
• \(t\)-CIS codes over \(\mathrm{GF}(p)\) and orthogonal arrays

This page was built for publication: Higher-Order CIS Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986146)