American Institute of Mathematical Sciences

Advanced
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

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, (1990).   Google Scholar

[2]

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

[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., (2013).  doi: 10.1145/2527317.2527324.  Google Scholar

[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, (2015), 82.  doi: 10.1109/HST.2015.7140242.  Google Scholar

[5]

S. Bhasin, J.-L. Danger, S. Guilley, T. Ngo and L. Sauvage, Hardware trojan horses in cryptographic IP cores,, in FDTC, (2013), 15.   Google Scholar

[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., (2014).  doi: 10.1145/2668322.2668329.  Google Scholar

[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, (2010).   Google Scholar

[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, (2014), 40.   Google Scholar

[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), (2010), 257.   Google Scholar

[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., (2015).   Google Scholar

[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.  doi: 10.1109/TIT.2012.2200651.  Google Scholar

[12]

B. Chen, H. Q. Dinh and H. Liu, Repeated-root constacyclic codes of length $2l^mp^n$,, preprint, ().   Google Scholar

[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, (2011), 1.   Google Scholar

[14]

M. Grassl, Bounds on the minimum distance of linear codes and quantum codes,, available online at , ().   Google Scholar

[15]

V. Grosso, F.-X. Standaert and E. Prouff, Low entropy masking schemes, revisited,, in CARDIS (eds. A. Francillon and P. Rohatgi), (2013), 33.   Google Scholar

[16]

W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes,, Cambridge University Press, (2003).  doi: 10.1017/CBO9780511807077.  Google Scholar

[17]

W. B. V. Kandasamy, F. Smarandache, R. Sujatha and R. S. R. Durai, Erasure Techniques in MRD Codes,, Infinite Study, (2012).   Google Scholar

[18]

S. Ling and C. Xing, Polyadic codes revisited,, IEEE Trans. Inf. Theory, 50 (2004), 200.  doi: 10.1109/TIT.2003.821986.  Google Scholar

[19]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes,, Elsevier, (1977).   Google Scholar

[20]

J. L. Massey, Linear codes with complementary duals,, Discrete Math., 106/107 (1992), 337.  doi: 10.1016/0012-365X(92)90563-U.  Google Scholar

[21]

G. L. Mullen and D. Panario, Handbook of Finite Fields,, Chapman and Hall/CRC, (2013).  doi: 10.1201/b15006.  Google Scholar

[22]

E. Prouff, M. Rivain and R. Bevan, Statistical Analysis of Second Order Differential Power Analysis,, IEEE Trans. Computers, 58 (2009), 799.  doi: 10.1109/TC.2009.15.  Google Scholar

[23]

N. Sendrier, Linear codes with complementary duals meet the Gilbert-Varshamov bound,, Discrete Math., 285 (2004), 345.  doi: 10.1016/j.disc.2004.05.005.  Google Scholar

[24]

A. Sharma, G. K. Bakshi and M. Raka, Polyadic codes of prime power length,, Finite Fields Appl., 13 (2007), 1071.  doi: 10.1016/j.ffa.2006.12.006.  Google Scholar

[25]

J. H. van Lint and F. J. MacWilliams, Generalized quadratic residue codes,, IEEE Trans. Inf. Theory, 24 (1978), 730.  doi: 10.1109/TIT.1978.1055965.  Google Scholar

[26]

H. N. Ward, Quadratic residue codes and divisibility,, in Handbook of Coding Theory (eds. V.S. Pless and W.C. Huffman), (1998), 827.   Google Scholar

[27]

X. Yang and J. L. Massey, The condition for a cyclic code to have a complementary dual,, Discrete Math., 126 (1994), 391.  doi: 10.1016/0012-365X(94)90283-6.  Google Scholar

show all references

References:
[1]

S. Barnett, Matrices: Methods and Applications,, Clarendon Press, (1990).   Google Scholar

[2]

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

[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., (2013).  doi: 10.1145/2527317.2527324.  Google Scholar

[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, (2015), 82.  doi: 10.1109/HST.2015.7140242.  Google Scholar

[5]

S. Bhasin, J.-L. Danger, S. Guilley, T. Ngo and L. Sauvage, Hardware trojan horses in cryptographic IP cores,, in FDTC, (2013), 15.   Google Scholar

[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., (2014).  doi: 10.1145/2668322.2668329.  Google Scholar

[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, (2010).   Google Scholar

[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, (2014), 40.   Google Scholar

[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), (2010), 257.   Google Scholar

[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., (2015).   Google Scholar

[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.  doi: 10.1109/TIT.2012.2200651.  Google Scholar

[12]

B. Chen, H. Q. Dinh and H. Liu, Repeated-root constacyclic codes of length $2l^mp^n$,, preprint, ().   Google Scholar

[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, (2011), 1.   Google Scholar

[14]

M. Grassl, Bounds on the minimum distance of linear codes and quantum codes,, available online at , ().   Google Scholar

[15]

V. Grosso, F.-X. Standaert and E. Prouff, Low entropy masking schemes, revisited,, in CARDIS (eds. A. Francillon and P. Rohatgi), (2013), 33.   Google Scholar

[16]

W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes,, Cambridge University Press, (2003).  doi: 10.1017/CBO9780511807077.  Google Scholar

[17]

W. B. V. Kandasamy, F. Smarandache, R. Sujatha and R. S. R. Durai, Erasure Techniques in MRD Codes,, Infinite Study, (2012).   Google Scholar

[18]

S. Ling and C. Xing, Polyadic codes revisited,, IEEE Trans. Inf. Theory, 50 (2004), 200.  doi: 10.1109/TIT.2003.821986.  Google Scholar

[19]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes,, Elsevier, (1977).   Google Scholar

[20]

J. L. Massey, Linear codes with complementary duals,, Discrete Math., 106/107 (1992), 337.  doi: 10.1016/0012-365X(92)90563-U.  Google Scholar

[21]

G. L. Mullen and D. Panario, Handbook of Finite Fields,, Chapman and Hall/CRC, (2013).  doi: 10.1201/b15006.  Google Scholar

[22]

E. Prouff, M. Rivain and R. Bevan, Statistical Analysis of Second Order Differential Power Analysis,, IEEE Trans. Computers, 58 (2009), 799.  doi: 10.1109/TC.2009.15.  Google Scholar

[23]

N. Sendrier, Linear codes with complementary duals meet the Gilbert-Varshamov bound,, Discrete Math., 285 (2004), 345.  doi: 10.1016/j.disc.2004.05.005.  Google Scholar

[24]

A. Sharma, G. K. Bakshi and M. Raka, Polyadic codes of prime power length,, Finite Fields Appl., 13 (2007), 1071.  doi: 10.1016/j.ffa.2006.12.006.  Google Scholar

[25]

J. H. van Lint and F. J. MacWilliams, Generalized quadratic residue codes,, IEEE Trans. Inf. Theory, 24 (1978), 730.  doi: 10.1109/TIT.1978.1055965.  Google Scholar

[26]

H. N. Ward, Quadratic residue codes and divisibility,, in Handbook of Coding Theory (eds. V.S. Pless and W.C. Huffman), (1998), 827.   Google Scholar

[27]

X. Yang and J. L. Massey, The condition for a cyclic code to have a complementary dual,, Discrete Math., 126 (1994), 391.  doi: 10.1016/0012-365X(94)90283-6.  Google Scholar

[1]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79
[2]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[3]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[4]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265
[5]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133
[6]

Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135
[7]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225
[8]

Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024
[9]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[10]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446
[11]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1
[12]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[13]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034
[14]

Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056
[15]

Dan Wei, Shangjiang Guo. Qualitative analysis of a Lotka-Volterra competition-diffusion-advection system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2599-2623. doi: 10.3934/dcdsb.2020197
[16]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[17]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[18]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis of a thermal frictional contact problem with long memory. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021031
[19]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137
[20]

Xiaoyi Zhou, Tong Ye, Tony T. Lee. Designing and analysis of a Wi-Fi data offloading strategy catering for the preference of mobile users. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021038

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (130)
  • HTML views (0)
  • Cited by (39)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences