February  2022, 16(1): 115-133. doi: 10.3934/amc.2020104

A geometric characterization of minimal codes and their asymptotic performance

1. 

Institute of Mathematics, University of Zurich, Winterthurerstrasse 190, 8057 Zurich, Switzerland

2. 

Université Paris 8, Laboratoire de Géométrie, Analyse et Applications, LAGA, Université Sorbonne Paris Nord, CNRS, UMR 7539, F-93430, Villetaneuse, France

3. 

Institute for Communications Engineering, Technical University of Munich, Theresienstrasse 90, 80333 Munich, Germany

* Corresponding author: Alessandro Neri

Received  January 2020 Revised  June 2020 Published  February 2022 Early access  August 2020

Fund Project: G. N. Alfarano acknowledges the support of Swiss National Science Foundation grant n. 188430. A. Neri acknowledges the support of Swiss National Science Foundation grant n. 187711

In this paper, we give a geometric characterization of minimal linear codes. In particular, we relate minimal linear codes to cutting blocking sets, introduced in a recent paper by Bonini and Borello. Using this characterization, we derive some bounds on the length and the distance of minimal codes, according to their dimension and the underlying field size. Furthermore, we show that the family of minimal codes is asymptotically good. Finally, we provide some geometrical constructions of minimal codes as cutting blocking sets.

Citation: 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
References:
[1]

E. Agrell, On the Voronoi neighbor ratio for binary linear block codes, IEEE Transactions on Information Theory, 44 (1998), 3064-3072.  doi: 10.1109/18.737535.

[2]

A. Alahmadi, C. Güneri, H. Shoaib and P. Solé, Long quasi-polycyclic $t$-CIS codes, Adv. Math. Commun., 12 (2018), 189–198, arXiv: 1703.03109. doi: 10.3934/amc.2018013.

[3]

A. AlahmadiF. Özdemir and P. Solé, On self-dual double circulant codes, Designs, Codes and Cryptography, 86 (2018), 1257-1265.  doi: 10.1007/s10623-017-0393-x.

[4]

A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Transactions on Information Theory, 44 (1998), 2010-2017.  doi: 10.1109/18.705584.

[5]

E. Assmus, The category of linear codes, IEEE Transactions on information theory, 44 (1998), 612-629.  doi: 10.1109/18.661508.

[6] S. Ball, Finite Geometry and Combinatorial Applications, volume 82., Cambridge University Press, 2015.  doi: 10.1017/CBO9781316257449.
[7]

S. Ball and A. Blokhuis, On the size of a double blocking set in ${\rm PG}(2, q)$, Finite Fields and their Applications, 2 (1996), 125-137.  doi: 10.1006/ffta.1996.9999.

[8]

D. Bartoli and M. Bonini, Minimal linear codes in odd characteristic, IEEE Transactions on Information Theory, 65 (2019), 4152-4155.  doi: 10.1109/TIT.2019.2891992.

[9]

D. Bartoli, M. Bonini and B. Güneș, An inductive construction of minimal codes, arXiv preprint, arXiv: 1911.09093, 2019.

[10]

A. Bishnoi, S. Mattheus and J. Schillewaert, Minimal multiple blocking sets, The Electronic Journal of Combinatorics, 25 (2018), 14pp. doi: 10.37236/7810.

[11]

G. R. Blakley, Safeguarding cryptographic keys, Proceedings of the 1979 AFIPS National Computer Conference, 48 (1979), 313-317.  doi: 10.1109/MARK.1979.8817296.

[12]

M. Bonini and M. Borello, Minimal linear codes arising from blocking sets, Journal of Algebraic Combinatorics, 2020, 1–15. doi: 10.1007/s10801-019-00930-6.

[13]

M. Borello and W. Willems, Group codes over fields are asymptotically good, Finite Fields and Their Applications, 68 (2020), 101738. doi: 10.1016/j.ffa.2020.101738.

[14]

W. BosmaJ. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbol. Comput., 24 (1997), 235-265.  doi: 10.1006/jsco.1996.0125.

[15]

C. CarletC. Ding and J. Yuan, Linear codes from highly nonlinear functions and their secret sharing schemes, IEEE Trans. Inf. Theory, 51 (2005), 2089-2102.  doi: 10.1109/TIT.2005.847722.

[16]

H. Chabanne, G. Cohen and A. Patey, Towards secure two-party computation from the wire-tap channel, Information security and cryptology—ICISC 2013, 34–46, Lecture Notes in Comput. Sci., 8565, Springer, Cham, 2014. doi: 10.1007/978-3-319-12160-4_3.

[17]

S. Chang and J. Y. Hyun, Linear codes from simplicial complexes, Designs, Codes and Cryptography, 86 (2018), 2167-2181.  doi: 10.1007/s10623-017-0442-5.

[18]

C. ChenW. W. Peterson and E. Weldon Jr, Some results on quasi-cyclic codes, Information and Control, 15 (1969), 407-423.  doi: 10.1016/S0019-9958(69)90497-5.

[19]

G. D. Cohen, S. Mesnager and A. Patey, On minimal and quasi-minimal linear codes, Cryptography and Coding, 85–98, Lecture Notes in Comput. Sci., 8308, Springer, Heidelberg, 2013. doi: 10.1007/978-3-642-45239-0_6.

[20]

C. Ding, Linear codes from some 2-designs, IEEE Transactions on Information Theory, 61 (2015), 3265-3275.  doi: 10.1109/TIT.2015.2420118.

[21]

C. DingD. R. Kohel and S. Ling, Secret-sharing with a class of ternary codes, Theoretical Computer Science, 246 (2000), 285-298.  doi: 10.1016/S0304-3975(00)00207-3.

[22]

C. DingC. LiN. Li and Z. Zhou, Three-weight cyclic codes and their weight distributions, Discrete Mathematics, 339 (2016), 415-427.  doi: 10.1016/j.disc.2015.09.001.

[23]

J. H. Griesmer, A bound for error-correcting codes, IBM J. Research Develop., 4 (1960), 532-542.  doi: 10.1147/rd.45.0532.

[24]

Z. HengC. Ding and Z. Zhou, Minimal linear codes over finite fields, Finite Fields and Their Applications, 54 (2018), 176-196.  doi: 10.1016/j.ffa.2018.08.010.

[25] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge university press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.
[26]

E. KarninJ. Greene and M. Hellman, On secret sharing systems, IEEE Transactions on Information Theory, 29 (1983), 35-41.  doi: 10.1109/TIT.1983.1056621.

[27]

W. Lu, X. Wu and X. Cao, The parameters of minimal linear codes, arXiv preprint, arXiv: 1911.07648, 2019.

[28]

J. L. Massey, Minimal codewords and secret sharing, In Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory, pages 276–279. Citeseer, 1993.

[29]

J. L. Massey, Some applications of coding theory in cryptography, Codes and Ciphers: Cryptography and Coding IV, 1995, 33–47.

[30]

R. J. McEliece and D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Communications of the ACM, 24 (1981), 583-584.  doi: 10.1145/358746.358762.

[31]

S. Mesnager, Linear codes with few weights from weakly regular bent functions based on a generic construction, Cryptogr. Commun., 9 (2017), 71-84.  doi: 10.1007/s12095-016-0186-5.

[32]

S. MesnagerF. Özbudak and A. Sınak, Linear codes from weakly regular plateaued functions and their secret sharing schemes, Des. Codes Cryptogr., 87 (2019), 463-480.  doi: 10.1007/s10623-018-0556-4.

[33]

S. Mesnager and A. Sınak, Several classes of minimal linear codes with few weights from weakly regular plateaued functions, IEEE Trans. Inf. Theory, 66 (2019), 2296-2310.  doi: 10.1109/TIT.2019.2956130.

[34]

B. Segre, Curve razionali normali e $k$-archi negli spazi finiti, Annali di Matematica Pura ed Applicata, 39 (1955), 357-379.  doi: 10.1007/BF02410779.

[35]

A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176.

[36]

R. C. Singleton, Maximum distance $q$-ary codes, IEEE Transactions on Information Theory, 10 (1964), 116-118.  doi: 10.1109/tit.1964.1053661.

[37]

C. Tang, Y. Qiu, Q. Liao and Z. Zhou, Full characterization of minimal linear codes as cutting blocking sets, arXiv preprint, arXiv: 1911.09867, 2019.

[38]

M. A. Tsfasman and S. G. Vlǎduţ, Algebraic-Geometric Codes, volume 58 of Mathematics and its Applications (Soviet Series), Kluwer Academic Publishers Group, Dordrecht, 1991. Translated from the Russian by the authors. doi: 10.1007/978-94-011-3810-9.

[39]

O. Veblen and J. W. Young, Projective Geometry, Vol. 1, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1965.

[40]

J. Yuan and C. Ding, Secret sharing schemes from three classes of linear codes, IEEE Transactions on Information Theory, 52 (2005), 206-212.  doi: 10.1109/TIT.2005.860412.

show all references

References:
[1]

E. Agrell, On the Voronoi neighbor ratio for binary linear block codes, IEEE Transactions on Information Theory, 44 (1998), 3064-3072.  doi: 10.1109/18.737535.

[2]

A. Alahmadi, C. Güneri, H. Shoaib and P. Solé, Long quasi-polycyclic $t$-CIS codes, Adv. Math. Commun., 12 (2018), 189–198, arXiv: 1703.03109. doi: 10.3934/amc.2018013.

[3]

A. AlahmadiF. Özdemir and P. Solé, On self-dual double circulant codes, Designs, Codes and Cryptography, 86 (2018), 1257-1265.  doi: 10.1007/s10623-017-0393-x.

[4]

A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Transactions on Information Theory, 44 (1998), 2010-2017.  doi: 10.1109/18.705584.

[5]

E. Assmus, The category of linear codes, IEEE Transactions on information theory, 44 (1998), 612-629.  doi: 10.1109/18.661508.

[6] S. Ball, Finite Geometry and Combinatorial Applications, volume 82., Cambridge University Press, 2015.  doi: 10.1017/CBO9781316257449.
[7]

S. Ball and A. Blokhuis, On the size of a double blocking set in ${\rm PG}(2, q)$, Finite Fields and their Applications, 2 (1996), 125-137.  doi: 10.1006/ffta.1996.9999.

[8]

D. Bartoli and M. Bonini, Minimal linear codes in odd characteristic, IEEE Transactions on Information Theory, 65 (2019), 4152-4155.  doi: 10.1109/TIT.2019.2891992.

[9]

D. Bartoli, M. Bonini and B. Güneș, An inductive construction of minimal codes, arXiv preprint, arXiv: 1911.09093, 2019.

[10]

A. Bishnoi, S. Mattheus and J. Schillewaert, Minimal multiple blocking sets, The Electronic Journal of Combinatorics, 25 (2018), 14pp. doi: 10.37236/7810.

[11]

G. R. Blakley, Safeguarding cryptographic keys, Proceedings of the 1979 AFIPS National Computer Conference, 48 (1979), 313-317.  doi: 10.1109/MARK.1979.8817296.

[12]

M. Bonini and M. Borello, Minimal linear codes arising from blocking sets, Journal of Algebraic Combinatorics, 2020, 1–15. doi: 10.1007/s10801-019-00930-6.

[13]

M. Borello and W. Willems, Group codes over fields are asymptotically good, Finite Fields and Their Applications, 68 (2020), 101738. doi: 10.1016/j.ffa.2020.101738.

[14]

W. BosmaJ. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbol. Comput., 24 (1997), 235-265.  doi: 10.1006/jsco.1996.0125.

[15]

C. CarletC. Ding and J. Yuan, Linear codes from highly nonlinear functions and their secret sharing schemes, IEEE Trans. Inf. Theory, 51 (2005), 2089-2102.  doi: 10.1109/TIT.2005.847722.

[16]

H. Chabanne, G. Cohen and A. Patey, Towards secure two-party computation from the wire-tap channel, Information security and cryptology—ICISC 2013, 34–46, Lecture Notes in Comput. Sci., 8565, Springer, Cham, 2014. doi: 10.1007/978-3-319-12160-4_3.

[17]

S. Chang and J. Y. Hyun, Linear codes from simplicial complexes, Designs, Codes and Cryptography, 86 (2018), 2167-2181.  doi: 10.1007/s10623-017-0442-5.

[18]

C. ChenW. W. Peterson and E. Weldon Jr, Some results on quasi-cyclic codes, Information and Control, 15 (1969), 407-423.  doi: 10.1016/S0019-9958(69)90497-5.

[19]

G. D. Cohen, S. Mesnager and A. Patey, On minimal and quasi-minimal linear codes, Cryptography and Coding, 85–98, Lecture Notes in Comput. Sci., 8308, Springer, Heidelberg, 2013. doi: 10.1007/978-3-642-45239-0_6.

[20]

C. Ding, Linear codes from some 2-designs, IEEE Transactions on Information Theory, 61 (2015), 3265-3275.  doi: 10.1109/TIT.2015.2420118.

[21]

C. DingD. R. Kohel and S. Ling, Secret-sharing with a class of ternary codes, Theoretical Computer Science, 246 (2000), 285-298.  doi: 10.1016/S0304-3975(00)00207-3.

[22]

C. DingC. LiN. Li and Z. Zhou, Three-weight cyclic codes and their weight distributions, Discrete Mathematics, 339 (2016), 415-427.  doi: 10.1016/j.disc.2015.09.001.

[23]

J. H. Griesmer, A bound for error-correcting codes, IBM J. Research Develop., 4 (1960), 532-542.  doi: 10.1147/rd.45.0532.

[24]

Z. HengC. Ding and Z. Zhou, Minimal linear codes over finite fields, Finite Fields and Their Applications, 54 (2018), 176-196.  doi: 10.1016/j.ffa.2018.08.010.

[25] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge university press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.
[26]

E. KarninJ. Greene and M. Hellman, On secret sharing systems, IEEE Transactions on Information Theory, 29 (1983), 35-41.  doi: 10.1109/TIT.1983.1056621.

[27]

W. Lu, X. Wu and X. Cao, The parameters of minimal linear codes, arXiv preprint, arXiv: 1911.07648, 2019.

[28]

J. L. Massey, Minimal codewords and secret sharing, In Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory, pages 276–279. Citeseer, 1993.

[29]

J. L. Massey, Some applications of coding theory in cryptography, Codes and Ciphers: Cryptography and Coding IV, 1995, 33–47.

[30]

R. J. McEliece and D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Communications of the ACM, 24 (1981), 583-584.  doi: 10.1145/358746.358762.

[31]

S. Mesnager, Linear codes with few weights from weakly regular bent functions based on a generic construction, Cryptogr. Commun., 9 (2017), 71-84.  doi: 10.1007/s12095-016-0186-5.

[32]

S. MesnagerF. Özbudak and A. Sınak, Linear codes from weakly regular plateaued functions and their secret sharing schemes, Des. Codes Cryptogr., 87 (2019), 463-480.  doi: 10.1007/s10623-018-0556-4.

[33]

S. Mesnager and A. Sınak, Several classes of minimal linear codes with few weights from weakly regular plateaued functions, IEEE Trans. Inf. Theory, 66 (2019), 2296-2310.  doi: 10.1109/TIT.2019.2956130.

[34]

B. Segre, Curve razionali normali e $k$-archi negli spazi finiti, Annali di Matematica Pura ed Applicata, 39 (1955), 357-379.  doi: 10.1007/BF02410779.

[35]

A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176.

[36]

R. C. Singleton, Maximum distance $q$-ary codes, IEEE Transactions on Information Theory, 10 (1964), 116-118.  doi: 10.1109/tit.1964.1053661.

[37]

C. Tang, Y. Qiu, Q. Liao and Z. Zhou, Full characterization of minimal linear codes as cutting blocking sets, arXiv preprint, arXiv: 1911.09867, 2019.

[38]

M. A. Tsfasman and S. G. Vlǎduţ, Algebraic-Geometric Codes, volume 58 of Mathematics and its Applications (Soviet Series), Kluwer Academic Publishers Group, Dordrecht, 1991. Translated from the Russian by the authors. doi: 10.1007/978-94-011-3810-9.

[39]

O. Veblen and J. W. Young, Projective Geometry, Vol. 1, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1965.

[40]

J. Yuan and C. Ding, Secret sharing schemes from three classes of linear codes, IEEE Transactions on Information Theory, 52 (2005), 206-212.  doi: 10.1109/TIT.2005.860412.

[1]

Ivan Landjev. On blocking sets in projective Hjelmslev planes. Advances in Mathematics of Communications, 2007, 1 (1) : 65-81. doi: 10.3934/amc.2007.1.65

[2]

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

[3]

Stefka Bouyuklieva, Zlatko Varbanov. Some connections between self-dual codes, combinatorial designs and secret sharing schemes. Advances in Mathematics of Communications, 2011, 5 (2) : 191-198. doi: 10.3934/amc.2011.5.191

[4]

Jesús Carrillo-Pacheco, Felipe Zaldivar. On codes over FFN$(1,q)$-projective varieties. Advances in Mathematics of Communications, 2016, 10 (2) : 209-220. doi: 10.3934/amc.2016001

[5]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127

[6]

Hans-Joachim Kroll, Sayed-Ghahreman Taherian, Rita Vincenti. Optimal antiblocking systems of information sets for the binary codes related to triangular graphs. Advances in Mathematics of Communications, 2022, 16 (1) : 169-183. doi: 10.3934/amc.2020107

[7]

Hiromichi Nakayama, Takeo Noda. Minimal sets and chain recurrent sets of projective flows induced from minimal flows on $3$-manifolds. Discrete and Continuous Dynamical Systems, 2005, 12 (4) : 629-638. doi: 10.3934/dcds.2005.12.629

[8]

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

[9]

Jop Briët, Assaf Naor, Oded Regev. Locally decodable codes and the failure of cotype for projective tensor products. Electronic Research Announcements, 2012, 19: 120-130. doi: 10.3934/era.2012.19.120

[10]

Kristian Bjerklöv, Russell Johnson. Minimal subsets of projective flows. Discrete and Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 493-516. doi: 10.3934/dcdsb.2008.9.493

[11]

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

[12]

P. Charters. Finding an asymptotically bad family of $q$-th power residue codes. Advances in Mathematics of Communications, 2009, 3 (1) : 53-58. doi: 10.3934/amc.2009.3.53

[13]

Somphong Jitman, Supawadee Prugsapitak, Madhu Raka. Some generalizations of good integers and their applications in the study of self-dual negacyclic codes. Advances in Mathematics of Communications, 2020, 14 (1) : 35-51. doi: 10.3934/amc.2020004

[14]

Steven T. Dougherty, Jon-Lark Kim, Patrick Solé. Double circulant codes from two class association schemes. Advances in Mathematics of Communications, 2007, 1 (1) : 45-64. doi: 10.3934/amc.2007.1.45

[15]

Beniamin Mounits, Tuvi Etzion, Simon Litsyn. New upper bounds on codes via association schemes and linear programming. Advances in Mathematics of Communications, 2007, 1 (2) : 173-195. doi: 10.3934/amc.2007.1.173

[16]

Ye Wang, Ran Tao. Constructions of linear codes with small hulls from association schemes. Advances in Mathematics of Communications, 2022, 16 (2) : 349-364. doi: 10.3934/amc.2020114

[17]

Roland Hildebrand. Barriers on projective convex sets. Conference Publications, 2011, 2011 (Special) : 672-683. doi: 10.3934/proc.2011.2011.672

[18]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075

[19]

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

[20]

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

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (404)
  • HTML views (634)
  • Cited by (3)

[Back to Top]