Complementary dual codes for counter-measures to side-channel attacks

Previous Article
Further results on fibre products of Kummer covers and curves with many points over finite fields
AMC Home
This Issue
Next Article
On applications of orbit codes to storage

February 2016, 10(1): 131-150. doi: 10.3934/amc.2016.10.131

Complementary dual codes for counter-measures to side-channel attacks

Claude Carlet ^1, and Sylvain Guilley ^2,

1.	LAGA, UMR 7539, CNRS, University of Paris VIII and University of Paris XIII, Department of Mathematics, 2 rue de la liberte, 93 526 Saint-Denis Cedex, France
2.	TELECOM-ParisTech, Crypto Group \| Paris-Saclay University \| CNRS LTCI, 37/39 rue Dareau, 75 634 Paris Cedex 13, France

Received December 2014 Revised September 2015 Published March 2016

Abstract
Related Papers

We recall why linear codes with complementary duals (LCD codes) play a role in counter-measures to passive and active side-channel analyses on embedded cryptosystems. The rate and the minimum distance of such LCD codes must be as large as possible. We recall the known primary construction of such codes with cyclic codes, and investigate other constructions, with expanded Reed-Solomon codes and generalized residue codes, for which we study the idempotents. These constructions do not allow to reach all the desired parameters. We study then those secondary constructions which preserve the LCD property, and we characterize conditions under which codes obtained by direct sum, direct product, puncturing, shortening, extending codes, or obtained by the Plotkin sum, can be LCD.

Keywords: cyclic codes, fault injection analysis, hardware trojan horses, linear codes with complementary duals (LCD), generalized residue codes., Ray-Chaudhuri and Hocquenghem (BCH) codes, Side-channel analysis, Bose.

Mathematics Subject Classification: Primary: 94B15, 94B65; Secondary: 14G5.

Citation: Claude Carlet, Sylvain Guilley. Complementary dual codes for counter-measures to side-channel attacks. Advances in Mathematics of Communications, 2016, 10 (1) : 131-150. doi: 10.3934/amc.2016.10.131

References:

[1]	S. Barnett, Matrices: Methods and Applications, Clarendon Press, Oxford, 1990.
[2]	K. Betsumiya and M. Harada, Binary optimal odd formally self-dual codes, Des. Codes Crypt., 23 (2001), 11-22. doi: 10.1023/A:1011203416769.
[3]	S. Bhasin, J.-L. Danger, S. Guilley and Z. Najm, A low-entropy first-degree secure provable masking scheme for resource-constrained devices, in Workshop Embedded Syst. Sec., New York, 2013. doi: 10.1145/2527317.2527324.
[4]	S. Bhasin, J.-L. Danger, S. Guilley, Z. Najm and X. T. Ngo, Linear complementary dual code improvement to strengthen encoded circuit against hardware trojan horses, in 2015 IEEE Int. Symp. Hardware-Oriented Sec. Trust, McLean, 2015, 82-87. doi: 10.1109/HST.2015.7140242.
[5]	S. Bhasin, J.-L. Danger, S. Guilley, T. Ngo and L. Sauvage, Hardware trojan horses in cryptographic IP cores, in FDTC, Santa Barbara, 2013, 15-29.
[6]	S. Bhasin, J.-L. Danger, X. T. Ngo, S. Guilley and Z. Najm, Encoding the state of integrated circuits: a proactive and reactive protection against hardware trojans horses, in Proc. 9th Workshop Embedded Syst. Sec., New York, 2014. doi: 10.1145/2668322.2668329.
[7]	A. Bojilov, A. J. van Zanten and S. M. Dodunekov, Minimal distances in generalized residue codes, in Proc. 12th Int. Workshop Algebr. Combin. Coding Theory, Novosibirsk, 2010.
[8]	J. Bringer, C. Carlet, H. Chabanne, S. Guilley and H. Maghrebi, Orthogonal direct sum masking - a smartcard friendly computation paradigm in a code, with builtin protection against side-channel and fault attacks, in WISTP, Springer, Heraklion, 2014, 40-56.
[9]	C. Carlet, Boolean functions for cryptography and error correcting codes, in Chapter of the Monography Boolean Models and Methods (eds. Y. Crama and P. Hammer), Cambridge University Press, 2010, 257-397.
[10]	C. Carlet, A. Daif, J.-L. Danger, S. Guilley, Z. Najm, X. T. Ngo and C. Tavernier, Optimized linear complementary codes implementation for hardware trojan prevention, in 22nd Europ. Conf. Circuit Theory Des., Trondheim, 2015.
[11]	C. Carlet, P. Gaborit, J.-L. Kim and P. Solé, A new class of codes for Boolean masking of cryptographic computations, IEEE Trans. Inf. Theory, 58 (2012), 6000-6011. doi: 10.1109/TIT.2012.2200651.
[12]	B. Chen, H. Q. Dinh and H. Liu, Repeated-root constacyclic codes of length $2l^mp^n$, preprint, arXiv:1406.1848
[13]	J. Etesami, F. Hu and W. Henkel, LCD codes and iterative decoding by projections, a first step towards an intuitive description of iterative decoding, in GLOBECOM, IEEE, 2011, 1-4.
[14]	M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, available online at http://www.codetables.de/
[15]	V. Grosso, F.-X. Standaert and E. Prouff, Low entropy masking schemes, revisited, in CARDIS (eds. A. Francillon and P. Rohatgi), Springer, 2013, 33-43.
[16]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003. doi: 10.1017/CBO9780511807077.
[17]	W. B. V. Kandasamy, F. Smarandache, R. Sujatha and R. S. R. Durai, Erasure Techniques in MRD Codes, Infinite Study, 2012.
[18]	S. Ling and C. Xing, Polyadic codes revisited, IEEE Trans. Inf. Theory, 50 (2004), 200-207. doi: 10.1109/TIT.2003.821986.
[19]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier, Amsterdam, 1977.
[20]	J. L. Massey, Linear codes with complementary duals, Discrete Math., 106/107 (1992), 337-342. doi: 10.1016/0012-365X(92)90563-U.
[21]	G. L. Mullen and D. Panario, Handbook of Finite Fields, Chapman and Hall/CRC, 2013. doi: 10.1201/b15006.
[22]	E. Prouff, M. Rivain and R. Bevan, Statistical Analysis of Second Order Differential Power Analysis, IEEE Trans. Computers, 58 (2009), 799-811. doi: 10.1109/TC.2009.15.
[23]	N. Sendrier, Linear codes with complementary duals meet the Gilbert-Varshamov bound, Discrete Math., 285 (2004), 345-347. doi: 10.1016/j.disc.2004.05.005.
[24]	A. Sharma, G. K. Bakshi and M. Raka, Polyadic codes of prime power length, Finite Fields Appl., 13 (2007), 1071-1085. doi: 10.1016/j.ffa.2006.12.006.
[25]	J. H. van Lint and F. J. MacWilliams, Generalized quadratic residue codes, IEEE Trans. Inf. Theory, 24 (1978), 730-737. doi: 10.1109/TIT.1978.1055965.
[26]	H. N. Ward, Quadratic residue codes and divisibility, in Handbook of Coding Theory (eds. V.S. Pless and W.C. Huffman), Elsevier Sci., 1998, 827-870.
[27]	X. Yang and J. L. Massey, The condition for a cyclic code to have a complementary dual, Discrete Math., 126 (1994), 391-393. doi: 10.1016/0012-365X(94)90283-6.

show all references

References:

[1]	S. Barnett, Matrices: Methods and Applications, Clarendon Press, Oxford, 1990.
[2]	K. Betsumiya and M. Harada, Binary optimal odd formally self-dual codes, Des. Codes Crypt., 23 (2001), 11-22. doi: 10.1023/A:1011203416769.
[3]	S. Bhasin, J.-L. Danger, S. Guilley and Z. Najm, A low-entropy first-degree secure provable masking scheme for resource-constrained devices, in Workshop Embedded Syst. Sec., New York, 2013. doi: 10.1145/2527317.2527324.
[4]	S. Bhasin, J.-L. Danger, S. Guilley, Z. Najm and X. T. Ngo, Linear complementary dual code improvement to strengthen encoded circuit against hardware trojan horses, in 2015 IEEE Int. Symp. Hardware-Oriented Sec. Trust, McLean, 2015, 82-87. doi: 10.1109/HST.2015.7140242.
[5]	S. Bhasin, J.-L. Danger, S. Guilley, T. Ngo and L. Sauvage, Hardware trojan horses in cryptographic IP cores, in FDTC, Santa Barbara, 2013, 15-29.
[6]	S. Bhasin, J.-L. Danger, X. T. Ngo, S. Guilley and Z. Najm, Encoding the state of integrated circuits: a proactive and reactive protection against hardware trojans horses, in Proc. 9th Workshop Embedded Syst. Sec., New York, 2014. doi: 10.1145/2668322.2668329.
[7]	A. Bojilov, A. J. van Zanten and S. M. Dodunekov, Minimal distances in generalized residue codes, in Proc. 12th Int. Workshop Algebr. Combin. Coding Theory, Novosibirsk, 2010.
[8]	J. Bringer, C. Carlet, H. Chabanne, S. Guilley and H. Maghrebi, Orthogonal direct sum masking - a smartcard friendly computation paradigm in a code, with builtin protection against side-channel and fault attacks, in WISTP, Springer, Heraklion, 2014, 40-56.
[9]	C. Carlet, Boolean functions for cryptography and error correcting codes, in Chapter of the Monography Boolean Models and Methods (eds. Y. Crama and P. Hammer), Cambridge University Press, 2010, 257-397.
[10]	C. Carlet, A. Daif, J.-L. Danger, S. Guilley, Z. Najm, X. T. Ngo and C. Tavernier, Optimized linear complementary codes implementation for hardware trojan prevention, in 22nd Europ. Conf. Circuit Theory Des., Trondheim, 2015.
[11]	C. Carlet, P. Gaborit, J.-L. Kim and P. Solé, A new class of codes for Boolean masking of cryptographic computations, IEEE Trans. Inf. Theory, 58 (2012), 6000-6011. doi: 10.1109/TIT.2012.2200651.
[12]	B. Chen, H. Q. Dinh and H. Liu, Repeated-root constacyclic codes of length $2l^mp^n$, preprint, arXiv:1406.1848
[13]	J. Etesami, F. Hu and W. Henkel, LCD codes and iterative decoding by projections, a first step towards an intuitive description of iterative decoding, in GLOBECOM, IEEE, 2011, 1-4.
[14]	M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, available online at http://www.codetables.de/
[15]	V. Grosso, F.-X. Standaert and E. Prouff, Low entropy masking schemes, revisited, in CARDIS (eds. A. Francillon and P. Rohatgi), Springer, 2013, 33-43.
[16]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003. doi: 10.1017/CBO9780511807077.
[17]	W. B. V. Kandasamy, F. Smarandache, R. Sujatha and R. S. R. Durai, Erasure Techniques in MRD Codes, Infinite Study, 2012.
[18]	S. Ling and C. Xing, Polyadic codes revisited, IEEE Trans. Inf. Theory, 50 (2004), 200-207. doi: 10.1109/TIT.2003.821986.
[19]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier, Amsterdam, 1977.
[20]	J. L. Massey, Linear codes with complementary duals, Discrete Math., 106/107 (1992), 337-342. doi: 10.1016/0012-365X(92)90563-U.
[21]	G. L. Mullen and D. Panario, Handbook of Finite Fields, Chapman and Hall/CRC, 2013. doi: 10.1201/b15006.
[22]	E. Prouff, M. Rivain and R. Bevan, Statistical Analysis of Second Order Differential Power Analysis, IEEE Trans. Computers, 58 (2009), 799-811. doi: 10.1109/TC.2009.15.
[23]	N. Sendrier, Linear codes with complementary duals meet the Gilbert-Varshamov bound, Discrete Math., 285 (2004), 345-347. doi: 10.1016/j.disc.2004.05.005.
[24]	A. Sharma, G. K. Bakshi and M. Raka, Polyadic codes of prime power length, Finite Fields Appl., 13 (2007), 1071-1085. doi: 10.1016/j.ffa.2006.12.006.
[25]	J. H. van Lint and F. J. MacWilliams, Generalized quadratic residue codes, IEEE Trans. Inf. Theory, 24 (1978), 730-737. doi: 10.1109/TIT.1978.1055965.
[26]	H. N. Ward, Quadratic residue codes and divisibility, in Handbook of Coding Theory (eds. V.S. Pless and W.C. Huffman), Elsevier Sci., 1998, 827-870.
[27]	X. Yang and J. L. Massey, The condition for a cyclic code to have a complementary dual, Discrete Math., 126 (1994), 391-393. doi: 10.1016/0012-365X(94)90283-6.

[1]	Xinmei Huang, Qin Yue, Yansheng Wu, Xiaoping Shi. Ternary Primitive LCD BCH codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021014
[2]	Haode Yan, Hao Liu, Chengju Li, Shudi Yang. Parameters of LCD BCH codes with two lengths. Advances in Mathematics of Communications, 2018, 12 (3) : 579-594. doi: 10.3934/amc.2018034
[3]	Cem Güneri, Ferruh Özbudak, Funda ÖzdemIr. On complementary dual additive cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 353-357. doi: 10.3934/amc.2017028
[4]	Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Addendum. Advances in Mathematics of Communications, 2011, 5 (3) : 543-546. doi: 10.3934/amc.2011.5.543
[5]	José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018
[6]	Angelot Behajaina. On BCH split metacyclic codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021045
[7]	Ranya Djihad Boulanouar, Aicha Batoul, Delphine Boucher. An overview on skew constacyclic codes and their subclass of LCD codes. Advances in Mathematics of Communications, 2021, 15 (4) : 611-632. doi: 10.3934/amc.2020085
[8]	Zihui Liu. Galois LCD codes over rings. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022002
[9]	Keita Ishizuka, Ken Saito. Construction for both self-dual codes and LCD codes. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2021070
[10]	Nigel Boston, Jing Hao. The weight distribution of quasi-quadratic residue codes. Advances in Mathematics of Communications, 2018, 12 (2) : 363-385. doi: 10.3934/amc.2018023
[11]	Nabil Bennenni, Kenza Guenda, Sihem Mesnager. DNA cyclic codes over rings. Advances in Mathematics of Communications, 2017, 11 (1) : 83-98. doi: 10.3934/amc.2017004
[12]	Heide Gluesing-Luerssen, Katherine Morrison, Carolyn Troha. Cyclic orbit codes and stabilizer subfields. Advances in Mathematics of Communications, 2015, 9 (2) : 177-197. doi: 10.3934/amc.2015.9.177
[13]	Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021002
[14]	José Ignacio Iglesias Curto. Generalized AG convolutional codes. Advances in Mathematics of Communications, 2009, 3 (4) : 317-328. doi: 10.3934/amc.2009.3.317
[15]	Sara D. Cardell, Joan-Josep Climent, Daniel Panario, Brett Stevens. A construction of $ \mathbb{F}_2 $-linear cyclic, MDS codes. Advances in Mathematics of Communications, 2020, 14 (3) : 437-453. doi: 10.3934/amc.2020047
[16]	Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297
[17]	Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Advances in Mathematics of Communications, 2010, 4 (1) : 69-81. doi: 10.3934/amc.2010.4.69
[18]	Gustavo Terra Bastos, Reginaldo Palazzo Júnior, Marinês Guerreiro. Abelian non-cyclic orbit codes and multishot subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 631-650. doi: 10.3934/amc.2020035
[19]	Martianus Frederic Ezerman, San Ling, Patrick Solé, Olfa Yemen. From skew-cyclic codes to asymmetric quantum codes. Advances in Mathematics of Communications, 2011, 5 (1) : 41-57. doi: 10.3934/amc.2011.5.41
[20]	Yunwen Liu, Longjiang Qu, Chao Li. New constructions of systematic authentication codes from three classes of cyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 1-16. doi: 10.3934/amc.2018001

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Claude Carlet Sylvain Guilley
on Google Scholar
Claude Carlet Sylvain Guilley

[Back to Top]