Yet another variation on minimal linear codes

Gérard  Cohen; Sihem  Mesnager; Hugues  Randriam

doi:10.3934/amc.2016.10.53

Article Contents

2016, Volume 10, Issue 1: 53-61. Doi: 10.3934/amc.2016.10.53

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

Yet another variation on minimal linear codes

1.
Télécom ParisTech, UMR 5141, CNRS, 46 rue Barrault, 75634 Paris Cedex 13
2.
University of Paris XIII and Paris VIII, Télécom ParisTech, LAGA, UMR 7539, CNRS, Sorbonne Paris Cité

Received: December 2014

Revised: May 2015

Published: February 2016

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 94B25, 94B27, 05D40.

Citation:

Related Papers

Cited by

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, arXiv:1202.4058
[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.