Yet another variation on minimal linear codes

Previous Article
Probability estimates for reachability of linear systems defined over finite fields
AMC Home
This Issue
Next Article
On extendability of additive code isometries

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

Abstract
Related Papers

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.
[2]	A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inf. Theory, 44 (1998), 2010-2017. 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, Algebraic Algorithms and Error-Correcting Codes, Springer, 1995, 96-105. 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-29.
[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.
[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.
[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.
[8]	G. Cohen and A. Lempel, Linear intersecting codes, Discrete Math., 56 (1985), 35-43. 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, Springer, Heidelberg, 2013, 85-98. 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-1295. doi: 10.1109/TIT.2004.828140.
[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.
[12]	E. N. Gilbert, A comparison of signaling alphabets, Bell Syst. Techn. J., 31 (1952), 504-522.
[13]	F. J. MacWilliams and N. J. Sloane, The theory of error-correcting codes, North Holland, Amsterdam, 1977.
[14]	J. L. Massey, Minimal codewords and secret sharing, in Proc. 6th Joint Swedish-Russian Int. Workshop Info. Theory, 1993, 276-279.
[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.
[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.
[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.
[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.
[19]	H. G. Schaathun, The Boneh-Shaw fingerprinting scheme is better than we thought, IEEE Trans. Inf. Forensics Sec., 1 (2006), 248-255.
[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-211.
[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-215. 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-2017. 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, Algebraic Algorithms and Error-Correcting Codes, Springer, 1995, 96-105. 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-29.
[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.
[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.
[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.
[8]	G. Cohen and A. Lempel, Linear intersecting codes, Discrete Math., 56 (1985), 35-43. 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, Springer, Heidelberg, 2013, 85-98. 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-1295. doi: 10.1109/TIT.2004.828140.
[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.
[12]	E. N. Gilbert, A comparison of signaling alphabets, Bell Syst. Techn. J., 31 (1952), 504-522.
[13]	F. J. MacWilliams and N. J. Sloane, The theory of error-correcting codes, North Holland, Amsterdam, 1977.
[14]	J. L. Massey, Minimal codewords and secret sharing, in Proc. 6th Joint Swedish-Russian Int. Workshop Info. Theory, 1993, 276-279.
[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.
[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.
[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.
[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.
[19]	H. G. Schaathun, The Boneh-Shaw fingerprinting scheme is better than we thought, IEEE Trans. Inf. Forensics Sec., 1 (2006), 248-255.
[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-211.
[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]	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, 2022, 16 (1) : 115-133. 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]	Enhui Lim, Frédérique Oggier. On the generalised rank weights of quasi-cyclic codes. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022010
[12]	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
[13]	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
[14]	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
[15]	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
[16]	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
[17]	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
[18]	Thomas Feulner. Canonization of linear codes over $\mathbb Z$₄. Advances in Mathematics of Communications, 2011, 5 (2) : 245-266. doi: 10.3934/amc.2011.5.245
[19]	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
[20]	Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020129

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Gérard Cohen Sihem Mesnager Hugues Randriam
on Google Scholar
Gérard Cohen Sihem Mesnager Hugues Randriam

[Back to Top]