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

[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.  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, (2013), 34.  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.  doi: 10.1016/S0166-218X(02)00437-7.  Google Scholar

[8]

G. Cohen and A. Lempel, Linear intersecting codes,, Discrete Math., 56 (1985), 35.  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, (2013), 85.  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.  doi: 10.1109/TIT.2004.828140.  Google Scholar

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

[12]

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

[13]

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

[14]

J. L. Massey, Minimal codewords and secret sharing,, in Proc. 6th Joint Swedish-Russian Int. Workshop Info. Theory, (1993), 276.   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.   Google Scholar

[16]

H. Randriambololona, $(2,1)$-separating systems beyond the probabilistic bound,, Israel J. Math., 195 (2013), 171.  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.  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), (2015), 3.  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.   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.   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.  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.  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, (1995), 96.  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.   Google Scholar

[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.  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, (2013), 34.  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.  doi: 10.1016/S0166-218X(02)00437-7.  Google Scholar

[8]

G. Cohen and A. Lempel, Linear intersecting codes,, Discrete Math., 56 (1985), 35.  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, (2013), 85.  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.  doi: 10.1109/TIT.2004.828140.  Google Scholar

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

[12]

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

[13]

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

[14]

J. L. Massey, Minimal codewords and secret sharing,, in Proc. 6th Joint Swedish-Russian Int. Workshop Info. Theory, (1993), 276.   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.   Google Scholar

[16]

H. Randriambololona, $(2,1)$-separating systems beyond the probabilistic bound,, Israel J. Math., 195 (2013), 171.  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.  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), (2015), 3.  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.   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.   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]

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

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

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

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[5]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124
[6]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049
[7]

Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039
[8]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[9]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[10]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[11]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[12]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054
[13]

Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020120
[14]

Vivina Barutello, Gian Marco Canneori, Susanna Terracini. Minimal collision arcs asymptotic to central configurations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 61-86. doi: 10.3934/dcds.2020218
[15]

Tingting Wu, Li Liu, Lanqiang Li, Shixin Zhu. Repeated-root constacyclic codes of length $ 6lp^s $. Advances in Mathematics of Communications, 2021, 15 (1) : 167-189. doi: 10.3934/amc.2020051
[16]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122
[17]

Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020127
[18]

Ivan Bailera, Joaquim Borges, Josep Rifà. On Hadamard full propelinear codes with associated group $ C_{2t}\times C_2 $. Advances in Mathematics of Communications, 2021, 15 (1) : 35-54. doi: 10.3934/amc.2020041
[19]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076
[20]

Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences