August  2013, 7(3): 267-278. doi: 10.3934/amc.2013.7.267

The classification of complementary information set codes of lengths $14$ and $16$

1. 

Department of Mathematics, Ohio Dominican University, 1216 Sunbury Road, Columbus, OH 43219, United States

Received  June 2012 Published  July 2013

In the paper ``A new class of codes for Boolean masking of cryptographic computations,'' Carlet, Gaborit, Kim, and Solé defined a new class of rate one-half binary codes called complementary information set (or CIS) codes. The authors then classified all CIS codes of length less than or equal to 12. CIS codes have relations to classical Coding Theory as they are a generali-zation of self-dual codes. As stated in the paper, CIS codes also have important practical applications as they may improve the cost of masking cryptographic algorithms against side channel attacks. In this paper, we give a complete classification result for length 14 CIS codes using an equivalence relation on $GL(n,\mathbb{F}_2)$. We also give a new classification for all binary $[16,8,3]$ and $[16,8,4]$ codes. We then complete the classification for length 16 CIS codes and give additional classifications for optimal CIS codes of lengths 20 and 26.
Citation: Finley Freibert. The classification of complementary information set codes of lengths $14$ and $16$. Advances in Mathematics of Communications, 2013, 7 (3) : 267-278. doi: 10.3934/amc.2013.7.267
References:
[1]

K. Betsumiya and M. Harada, Binary optimal odd formally self-dual codes, Des. Codes Crypt., 23 (2001), 11-21. doi: 10.1023/A:1011203416769.

[2]

K. Betsumiya and M. Harada, Classification of formally self-dual even codes of lengths up to 16, Des. Codes Crypt., 23 (2001), 325-332. doi: 10.1023/A:1011223128089.

[3]

K. Betsumiya, M. Harada and A. Munemasa, A complete classification of doubly-even self-dual codes of length 40, preprint, arXiv:1104.3727v2

[4]

J. Cannon and C. Playoust, "An Introduction to Magma,'' University of Sydney, Sydney, Australia, 1994.

[5]

C. Carlet, P. Gaborit, J.-L. Kim and P. Solé, A new class of codes for Boolean masking of cryptographic computations, preprint, arXiv:1110.1193v2 doi: 10.1109/TIT.2012.2200651.

[6]

I. A. Faradzev, Constructive enumeration of combinatorial objects, in "Problemes Combinatoires et Theorie des Graphes Colloque Internat,'' CNRS, Paris, (1978), 131-135.

[7]

J. E. Fields, P. Gaborit, W. C. Huffman and V. Pless, On the classification of extremal even formally self-dual codes of lengths 20 and 22, Discrete Appl. Math., 111 (2001), 75-86. doi: 10.1016/S0166-218X(00)00345-0.

[8]

F. Freibert, A classification of binary [16,8,4] codes; A classification of [14,7] CIS codes, available online at http://finleyfreibert.wordpress.com/mathematics-research/, 2012.

[9]

T. A. Gulliver and P. R. J. Östergard, Binary optimal linear rate 1/2 codes, Discrete Math., 283 (2004), 255-261. doi: 10.1016/j.disc.2003.10.027.

[10]

S. Han, H. Lee and Y. Lee, Binary formally self-dual odd codes, Des. Codes Crypt., 61 (2010), 141-150. doi: 10.1007/s10623-010-9444-2.

[11]

W. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'' Cambridge University Press, Cambridge, 2003.

[12]

P. Kaski and P. R. J. Östergard, "Classification Algorithms for Codes and Designs,'' Springer, Berlin, 2006.

[13]

H. Maghrebi, C. Carlet, S. Guilley and J.-L. Danger, Optimal first-order masking with linear and non-linear bijections, in "Progress in Cryptology - AFRICACRYPT 2012,'' (2012), 360-377. doi: 10.1007/978-3-642-31410-0_22.

[14]

H. Maghrebi, S. Guilley, C. Carlet and J.-L. Danger, Classification of high-order Boolean masking Schemes and improvements of their efficiency, available online at http://eprint.iacr.org/2011/520.pdf, 2011.

[15]

H. Maghrebi, S. Guilley and J.-L. Danger, Leakage squeezing countermeasure against high-order attacks, in "Information Security Theory and Practice,'' Springer, Berlin, (2011), 208-223. doi: 10.1007/978-3-642-21040-2_14.

[16]

B. D. McKay, Nauty user's guide (version 2.4), available online at http://cs.anu.edu.au/~bdm/nauty/nug.pdf, 2009.

[17]

P. R. J. Östergard, Classifying subspaces of hamming spaces, Des. Codes Crypt., 27 (2000), 297-305. doi: 10.1023/A:1019903407222.

[18]

V. Pless, A classification of self-orthogonal codes over $GF(2)$, Discrete Math., 3 (1972), 215-228. doi: 10.1016/0012-365X(72)90034-9.

[19]

R. C. Read, Every one a winner; or, how to avoid isomorphism search when cataloguing combinatorial configurations, Ann. Discrete Math., 2 (1978), 107-120. doi: 10.1016/S0167-5060(08)70325-X.

[20]

M. Rivain and E. Prouff, Provably secure higher-order masking of AES, in "Cryptographic Hardware and Embedded Systems, CHES 2010,'' Springer, Berlin, (2010), 413-427. doi: 10.1007/978-3-642-15031-9_28.

[21]

H. G. Schaathun, On higher weights and code existence, in "Cryptography and Coding,'' Springer, Berlin, (2009), 56-64. doi: 10.1007/978-3-642-10868-6_4.

[22]

J. Simonis, A description of the $[16,7,6]$ codes, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes,'' Springer, Berlin, (1991), 25-35. doi: 10.1007/3-540-54195-0_36.

show all references

References:
[1]

K. Betsumiya and M. Harada, Binary optimal odd formally self-dual codes, Des. Codes Crypt., 23 (2001), 11-21. doi: 10.1023/A:1011203416769.

[2]

K. Betsumiya and M. Harada, Classification of formally self-dual even codes of lengths up to 16, Des. Codes Crypt., 23 (2001), 325-332. doi: 10.1023/A:1011223128089.

[3]

K. Betsumiya, M. Harada and A. Munemasa, A complete classification of doubly-even self-dual codes of length 40, preprint, arXiv:1104.3727v2

[4]

J. Cannon and C. Playoust, "An Introduction to Magma,'' University of Sydney, Sydney, Australia, 1994.

[5]

C. Carlet, P. Gaborit, J.-L. Kim and P. Solé, A new class of codes for Boolean masking of cryptographic computations, preprint, arXiv:1110.1193v2 doi: 10.1109/TIT.2012.2200651.

[6]

I. A. Faradzev, Constructive enumeration of combinatorial objects, in "Problemes Combinatoires et Theorie des Graphes Colloque Internat,'' CNRS, Paris, (1978), 131-135.

[7]

J. E. Fields, P. Gaborit, W. C. Huffman and V. Pless, On the classification of extremal even formally self-dual codes of lengths 20 and 22, Discrete Appl. Math., 111 (2001), 75-86. doi: 10.1016/S0166-218X(00)00345-0.

[8]

F. Freibert, A classification of binary [16,8,4] codes; A classification of [14,7] CIS codes, available online at http://finleyfreibert.wordpress.com/mathematics-research/, 2012.

[9]

T. A. Gulliver and P. R. J. Östergard, Binary optimal linear rate 1/2 codes, Discrete Math., 283 (2004), 255-261. doi: 10.1016/j.disc.2003.10.027.

[10]

S. Han, H. Lee and Y. Lee, Binary formally self-dual odd codes, Des. Codes Crypt., 61 (2010), 141-150. doi: 10.1007/s10623-010-9444-2.

[11]

W. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'' Cambridge University Press, Cambridge, 2003.

[12]

P. Kaski and P. R. J. Östergard, "Classification Algorithms for Codes and Designs,'' Springer, Berlin, 2006.

[13]

H. Maghrebi, C. Carlet, S. Guilley and J.-L. Danger, Optimal first-order masking with linear and non-linear bijections, in "Progress in Cryptology - AFRICACRYPT 2012,'' (2012), 360-377. doi: 10.1007/978-3-642-31410-0_22.

[14]

H. Maghrebi, S. Guilley, C. Carlet and J.-L. Danger, Classification of high-order Boolean masking Schemes and improvements of their efficiency, available online at http://eprint.iacr.org/2011/520.pdf, 2011.

[15]

H. Maghrebi, S. Guilley and J.-L. Danger, Leakage squeezing countermeasure against high-order attacks, in "Information Security Theory and Practice,'' Springer, Berlin, (2011), 208-223. doi: 10.1007/978-3-642-21040-2_14.

[16]

B. D. McKay, Nauty user's guide (version 2.4), available online at http://cs.anu.edu.au/~bdm/nauty/nug.pdf, 2009.

[17]

P. R. J. Östergard, Classifying subspaces of hamming spaces, Des. Codes Crypt., 27 (2000), 297-305. doi: 10.1023/A:1019903407222.

[18]

V. Pless, A classification of self-orthogonal codes over $GF(2)$, Discrete Math., 3 (1972), 215-228. doi: 10.1016/0012-365X(72)90034-9.

[19]

R. C. Read, Every one a winner; or, how to avoid isomorphism search when cataloguing combinatorial configurations, Ann. Discrete Math., 2 (1978), 107-120. doi: 10.1016/S0167-5060(08)70325-X.

[20]

M. Rivain and E. Prouff, Provably secure higher-order masking of AES, in "Cryptographic Hardware and Embedded Systems, CHES 2010,'' Springer, Berlin, (2010), 413-427. doi: 10.1007/978-3-642-15031-9_28.

[21]

H. G. Schaathun, On higher weights and code existence, in "Cryptography and Coding,'' Springer, Berlin, (2009), 56-64. doi: 10.1007/978-3-642-10868-6_4.

[22]

J. Simonis, A description of the $[16,7,6]$ codes, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes,'' Springer, Berlin, (1991), 25-35. doi: 10.1007/3-540-54195-0_36.

[1]

Stefka Bouyuklieva, Iliya Bouyukliev. Classification of the extremal formally self-dual even codes of length 30. Advances in Mathematics of Communications, 2010, 4 (3) : 433-439. doi: 10.3934/amc.2010.4.433

[2]

Masaaki Harada, Katsushi Waki. New extremal formally self-dual even codes of length 30. Advances in Mathematics of Communications, 2009, 3 (4) : 311-316. doi: 10.3934/amc.2009.3.311

[3]

Masaaki Harada, Akihiro Munemasa. Classification of self-dual codes of length 36. Advances in Mathematics of Communications, 2012, 6 (2) : 229-235. doi: 10.3934/amc.2012.6.229

[4]

Steven T. Dougherty, Joe Gildea, Abidin Kaya, Bahattin Yildiz. New self-dual and formally self-dual codes from group ring constructions. Advances in Mathematics of Communications, 2020, 14 (1) : 11-22. doi: 10.3934/amc.2020002

[5]

Lars Eirik Danielsen. Graph-based classification of self-dual additive codes over finite fields. Advances in Mathematics of Communications, 2009, 3 (4) : 329-348. doi: 10.3934/amc.2009.3.329

[6]

Gabriele Nebe, Wolfgang Willems. On self-dual MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 633-642. doi: 10.3934/amc.2016031

[7]

Adrian Korban, Serap Şahinkaya, Deniz Ustun. A novel genetic search scheme based on nature-inspired evolutionary algorithms for binary self-dual codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022033

[8]

Stefka Bouyuklieva, Anton Malevich, Wolfgang Willems. On the performance of binary extremal self-dual codes. Advances in Mathematics of Communications, 2011, 5 (2) : 267-274. doi: 10.3934/amc.2011.5.267

[9]

Nikolay Yankov, Damyan Anev, Müberra Gürel. Self-dual codes with an automorphism of order 13. Advances in Mathematics of Communications, 2017, 11 (3) : 635-645. doi: 10.3934/amc.2017047

[10]

Steven T. Dougherty, Cristina Fernández-Córdoba, Roger Ten-Valls, Bahattin Yildiz. Quaternary group ring codes: Ranks, kernels and self-dual codes. Advances in Mathematics of Communications, 2020, 14 (2) : 319-332. doi: 10.3934/amc.2020023

[11]

Keita Ishizuka, Ken Saito. Construction for both self-dual codes and LCD codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021070

[12]

Steven Dougherty, Adrian Korban, Serap Șahinkaya, Deniz Ustun. Binary self-dual and LCD codes from generator matrices constructed from two group ring elements by a heuristic search scheme. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022036

[13]

Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251

[14]

Hyun Jin Kim, Heisook Lee, June Bok Lee, Yoonjin Lee. Construction of self-dual codes with an automorphism of order $p$. Advances in Mathematics of Communications, 2011, 5 (1) : 23-36. doi: 10.3934/amc.2011.5.23

[15]

Minjia Shi, Daitao Huang, Lin Sok, Patrick Solé. Double circulant self-dual and LCD codes over Galois rings. Advances in Mathematics of Communications, 2019, 13 (1) : 171-183. doi: 10.3934/amc.2019011

[16]

Bram van Asch, Frans Martens. Lee weight enumerators of self-dual codes and theta functions. Advances in Mathematics of Communications, 2008, 2 (4) : 393-402. doi: 10.3934/amc.2008.2.393

[17]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65

[18]

Katherine Morrison. An enumeration of the equivalence classes of self-dual matrix codes. Advances in Mathematics of Communications, 2015, 9 (4) : 415-436. doi: 10.3934/amc.2015.9.415

[19]

Steven T. Dougherty, Joe Gildea, Adrian Korban, Abidin Kaya. Composite constructions of self-dual codes from group rings and new extremal self-dual binary codes of length 68. Advances in Mathematics of Communications, 2020, 14 (4) : 677-702. doi: 10.3934/amc.2020037

[20]

Suat Karadeniz, Bahattin Yildiz. New extremal binary self-dual codes of length $68$ from $R_2$-lifts of binary self-dual codes. Advances in Mathematics of Communications, 2013, 7 (2) : 219-229. doi: 10.3934/amc.2013.7.219

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (69)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]