American Institute of Mathematical Sciences

Advanced
February  2016, 10(1): 53-61. doi: 10.3934/amc.2016.10.53

Yet another variation on minimal linear codes

Gérard Cohen 1, , Sihem Mesnager 2, and  Hugues Randriam 1,

1. 

Télécom ParisTech, UMR 5141, CNRS, 46 rue Barrault, 75634 Paris Cedex 13, France, France
2. 

University of Paris XIII and Paris VIII, Télécom ParisTech, LAGA, UMR 7539, CNRS, Sorbonne Paris Cité, France

Received  December 2014 Revised  May 2015 Published  March 2016

Minimal linear codes are linear codes such that the support of every codeword does not contain the support of another linearly independent codeword. Such codes have applications in cryptography, e.g. to secret sharing. We pursue here their study and construct improved asymptotically good families of minimal linear codes. We also consider quasi-minimal, $t$-minimal, and $t$-quasi-minimal linear codes, which are new variations on this notion.
Keywords: minimal codes, Linear codes, quasi-minimal codes..
Mathematics Subject Classification: 94B25, 94B27, 05D4.
Citation: Gérard Cohen, Sihem Mesnager, Hugues Randriam. Yet another variation on minimal linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 53-61. doi: 10.3934/amc.2016.10.53
References:
[1]

N. Alon, G. Cohen, M. Krivilevitch and S. Litsyn, Generalized hashing and applications, JCT-A, 104 (2003), 207-215. doi: 10.1016/j.jcta.2003.08.001.  Google Scholar

[2]

A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inf. Theory, 44 (1998), 2010-2017. doi: 10.1109/18.705584.  Google Scholar

[3]

A. Ashikhmin, A. Barg, G. Cohen and L. Huguet, Variations on minimal codewords in linear codes, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer, 1995, 96-105. doi: 10.1007/3-540-60114-7_7.  Google Scholar

[4]

A. Bassa, P. Beelen, A. Garcia and H. Stichtenoth, Towers of function fields over non-prime finite fields, Moscow Math. J., 15 (2015), 1-29. Google Scholar

[5]

G. Brassard, C. Crépeau and M. Santha, Oblivious transfers and intersecting codes, IEEE Trans. Inf. Theory, 42 (1996), 1769-1780. doi: 10.1109/18.556673.  Google Scholar

[6]

H. Chabanne, G. Cohen and A. Patey, Towards secure two-party computation from the wire-tap channel, in Information Security and Cryptology-ICISC 2013, Springer, 2013, 34-46. doi: 10.1007/978-3-319-12160-4_3.  Google Scholar

[7]

G. Cohen, S. Encheva, S. Litsyn and H.-G. Schaathun, Intersecting codes and separating codes, Discrete Appl. Math., 128 (2003), 75-83. doi: 10.1016/S0166-218X(02)00437-7.  Google Scholar

[8]

G. Cohen and A. Lempel, Linear intersecting codes, Discrete Math., 56 (1985), 35-43. doi: 10.1016/0012-365X(85)90190-6.  Google Scholar

[9]

G. Cohen, S. Mesnager and A. Patey, On minimal and quasi-minimal linear codes, in Proc. 14th Int. Conf. Crypt. Coding, Springer, Heidelberg, 2013, 85-98. doi: 10.1007/978-3-642-45239-0_6.  Google Scholar

[10]

G. Cohen and H.-G. Schaathun, Upper bounds on separating codes, IEEE Trans. Inf. Theory, 50 (2004), 1291-1295. doi: 10.1109/TIT.2004.828140.  Google Scholar

[11]

C. Ding and J. Yuan, Covering and secret sharing with linear codes, in DMTCS, Springer, 2003, 11-25. doi: 10.1007/3-540-45066-1_2.  Google Scholar

[12]

E. N. Gilbert, A comparison of signaling alphabets, Bell Syst. Techn. J., 31 (1952), 504-522. Google Scholar

[13]

F. J. MacWilliams and N. J. Sloane, The theory of error-correcting codes, North Holland, Amsterdam, 1977. Google Scholar

[14]

J. L. Massey, Minimal codewords and secret sharing, in Proc. 6th Joint Swedish-Russian Int. Workshop Info. Theory, 1993, 276-279. Google Scholar

[15]

J. L. Massey, Some applications of coding theory in cryptography, in Codes and Cyphers: Cryptography and Coding IV (ed. P.G. Farrell), 1995, 33-47. Google Scholar

[16]

H. Randriambololona, $(2,1)$-separating systems beyond the probabilistic bound, Israel J. Math., 195 (2013), 171-186. doi: 10.1007/s11856-012-0126-9.  Google Scholar

[17]

H. Randriambololona, Asymptotically good binary linear codes with asymptotically good self-intersection spans, IEEE Trans. Inf. Theory, 59 (2013), 3038-3045. doi: 10.1109/TIT.2013.2237944.  Google Scholar

[18]

H. Randriambololona, On products and powers of linear codes under componentwise multiplication, in Proc. 14th Int. Conf. Arithm. Geom. Crypt. Coding Theory (AGCT-14), Luminy, 2015, 3-7. doi: 10.1090/conm/637/12749.  Google Scholar

[19]

H. G. Schaathun, The Boneh-Shaw fingerprinting scheme is better than we thought, IEEE Trans. Inf. Forensics Sec., 1 (2006), 248-255. Google Scholar

[20]

Y. Song and Z. Li, Secret sharing with a class of minimal linear codes,, preprint, ().   Google Scholar

[21]

Y. Song, Z. Li, Y. Li and J. Li, A new multi-use multi-secret sharing scheme based on the duals of minimal linear codes, Sec. Commun. Netw., 8 (2015), 202-211. Google Scholar

[22]

M. A. Tsfasman and S. G. Vladut, Algebraic Geometric Codes, Kluwer, 1991. doi: 10.1007/978-94-011-3810-9.  Google Scholar

show all references

References:
[1]

N. Alon, G. Cohen, M. Krivilevitch and S. Litsyn, Generalized hashing and applications, JCT-A, 104 (2003), 207-215. doi: 10.1016/j.jcta.2003.08.001.  Google Scholar

[2]

A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inf. Theory, 44 (1998), 2010-2017. doi: 10.1109/18.705584.  Google Scholar

[3]

A. Ashikhmin, A. Barg, G. Cohen and L. Huguet, Variations on minimal codewords in linear codes, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer, 1995, 96-105. doi: 10.1007/3-540-60114-7_7.  Google Scholar

[4]

A. Bassa, P. Beelen, A. Garcia and H. Stichtenoth, Towers of function fields over non-prime finite fields, Moscow Math. J., 15 (2015), 1-29. Google Scholar

[5]

G. Brassard, C. Crépeau and M. Santha, Oblivious transfers and intersecting codes, IEEE Trans. Inf. Theory, 42 (1996), 1769-1780. doi: 10.1109/18.556673.  Google Scholar

[6]

H. Chabanne, G. Cohen and A. Patey, Towards secure two-party computation from the wire-tap channel, in Information Security and Cryptology-ICISC 2013, Springer, 2013, 34-46. doi: 10.1007/978-3-319-12160-4_3.  Google Scholar

[7]

G. Cohen, S. Encheva, S. Litsyn and H.-G. Schaathun, Intersecting codes and separating codes, Discrete Appl. Math., 128 (2003), 75-83. doi: 10.1016/S0166-218X(02)00437-7.  Google Scholar

[8]

G. Cohen and A. Lempel, Linear intersecting codes, Discrete Math., 56 (1985), 35-43. doi: 10.1016/0012-365X(85)90190-6.  Google Scholar

[9]

G. Cohen, S. Mesnager and A. Patey, On minimal and quasi-minimal linear codes, in Proc. 14th Int. Conf. Crypt. Coding, Springer, Heidelberg, 2013, 85-98. doi: 10.1007/978-3-642-45239-0_6.  Google Scholar

[10]

G. Cohen and H.-G. Schaathun, Upper bounds on separating codes, IEEE Trans. Inf. Theory, 50 (2004), 1291-1295. doi: 10.1109/TIT.2004.828140.  Google Scholar

[11]

C. Ding and J. Yuan, Covering and secret sharing with linear codes, in DMTCS, Springer, 2003, 11-25. doi: 10.1007/3-540-45066-1_2.  Google Scholar

[12]

E. N. Gilbert, A comparison of signaling alphabets, Bell Syst. Techn. J., 31 (1952), 504-522. Google Scholar

[13]

F. J. MacWilliams and N. J. Sloane, The theory of error-correcting codes, North Holland, Amsterdam, 1977. Google Scholar

[14]

J. L. Massey, Minimal codewords and secret sharing, in Proc. 6th Joint Swedish-Russian Int. Workshop Info. Theory, 1993, 276-279. Google Scholar

[15]

J. L. Massey, Some applications of coding theory in cryptography, in Codes and Cyphers: Cryptography and Coding IV (ed. P.G. Farrell), 1995, 33-47. Google Scholar

[16]

H. Randriambololona, $(2,1)$-separating systems beyond the probabilistic bound, Israel J. Math., 195 (2013), 171-186. doi: 10.1007/s11856-012-0126-9.  Google Scholar

[17]

H. Randriambololona, Asymptotically good binary linear codes with asymptotically good self-intersection spans, IEEE Trans. Inf. Theory, 59 (2013), 3038-3045. doi: 10.1109/TIT.2013.2237944.  Google Scholar

[18]

H. Randriambololona, On products and powers of linear codes under componentwise multiplication, in Proc. 14th Int. Conf. Arithm. Geom. Crypt. Coding Theory (AGCT-14), Luminy, 2015, 3-7. doi: 10.1090/conm/637/12749.  Google Scholar

[19]

H. G. Schaathun, The Boneh-Shaw fingerprinting scheme is better than we thought, IEEE Trans. Inf. Forensics Sec., 1 (2006), 248-255. Google Scholar

[20]

Y. Song and Z. Li, Secret sharing with a class of minimal linear codes,, preprint, ().   Google Scholar

[21]

Y. Song, Z. Li, Y. Li and J. Li, A new multi-use multi-secret sharing scheme based on the duals of minimal linear codes, Sec. Commun. Netw., 8 (2015), 202-211. Google Scholar

[22]

M. A. Tsfasman and S. G. Vladut, Algebraic Geometric Codes, Kluwer, 1991. doi: 10.1007/978-94-011-3810-9.  Google Scholar

[1]

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
[2]

Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233
[3]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055
[4]

Gianira N. Alfarano, Martino Borello, Alessandro Neri. A geometric characterization of minimal codes and their asymptotic performance. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020104
[5]

Nuh Aydin, Nicholas Connolly, Markus Grassl. Some results on the structure of constacyclic codes and new linear codes over GF(7) from quasi-twisted codes. Advances in Mathematics of Communications, 2017, 11 (1) : 245-258. doi: 10.3934/amc.2017016
[6]

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
[7]

Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195
[8]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[9]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259
[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]

Fernando Hernando, Diego Ruano. New linear codes from matrix-product codes with polynomial units. Advances in Mathematics of Communications, 2010, 4 (3) : 363-367. doi: 10.3934/amc.2010.4.363
[12]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163
[13]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019
[14]

Peter Vandendriessche. LDPC codes associated with linear representations of geometries. Advances in Mathematics of Communications, 2010, 4 (3) : 405-417. doi: 10.3934/amc.2010.4.405
[15]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024
[16]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[17]

Thomas Feulner. Canonization of linear codes over $\mathbb Z$4. Advances in Mathematics of Communications, 2011, 5 (2) : 245-266. doi: 10.3934/amc.2011.5.245
[18]

Tatsuya Maruta, Yusuke Oya. On optimal ternary linear codes of dimension 6. Advances in Mathematics of Communications, 2011, 5 (3) : 505-520. doi: 10.3934/amc.2011.5.505
[19]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129
[20]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences