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

Yet another variation on minimal linear codes

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.
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. doi: 10.1016/j.jcta.2003.08.001.

[2]

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

[3]

A. Ashikhmin, A. Barg, G. Cohen and L. Huguet, Variations on minimal codewords in linear codes,, in Applied Algebra, (1995), 96. doi: 10.1007/3-540-60114-7_7.

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

[5]

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

[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, (2013), 34. doi: 10.1007/978-3-319-12160-4_3.

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

F. J. MacWilliams and N. J. Sloane, The theory of error-correcting codes,, North Holland, (1977).

[14]

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

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

[16]

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

[17]

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

[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), (2015), 3. doi: 10.1090/conm/637/12749.

[19]

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

[20]

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

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

[22]

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

show all references

References:
[1]

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

[2]

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

[3]

A. Ashikhmin, A. Barg, G. Cohen and L. Huguet, Variations on minimal codewords in linear codes,, in Applied Algebra, (1995), 96. doi: 10.1007/3-540-60114-7_7.

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

[5]

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

[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, (2013), 34. doi: 10.1007/978-3-319-12160-4_3.

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

F. J. MacWilliams and N. J. Sloane, The theory of error-correcting codes,, North Holland, (1977).

[14]

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

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

[16]

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

[17]

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

[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), (2015), 3. doi: 10.1090/conm/637/12749.

[19]

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

[20]

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

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

[22]

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

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

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225

[16]

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

[17]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021

[18]

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

[19]

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

[20]

J. De Beule, K. Metsch, L. Storme. Characterization results on weighted minihypers and on linear codes meeting the Griesmer bound. Advances in Mathematics of Communications, 2008, 2 (3) : 261-272. doi: 10.3934/amc.2008.2.261

2017 Impact Factor: 0.564

Metrics

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

Other articles
by authors

[Back to Top]