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

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

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

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

[5]

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

[6] S. Ball, Finite Geometry and Combinatorial Applications, volume 82., Cambridge University Press, 2015.  doi: 10.1017/CBO9781316257449.  Google Scholar
[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.  Google Scholar

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

[9]

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

[10]

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

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

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

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

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

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

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

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

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

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

[20]

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

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

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

[23]

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

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

[25] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge university press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[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.  Google Scholar

[27]

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

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

[29]

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

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

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

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

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

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

[35]

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

[36]

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

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

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

[39]

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

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

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

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

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

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

[5]

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

[6] S. Ball, Finite Geometry and Combinatorial Applications, volume 82., Cambridge University Press, 2015.  doi: 10.1017/CBO9781316257449.  Google Scholar
[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.  Google Scholar

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

[9]

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

[10]

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

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

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

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

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

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

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

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

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

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

[20]

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

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

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

[23]

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

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

[25] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge university press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[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.  Google Scholar

[27]

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

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

[29]

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

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

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

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

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

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

[35]

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

[36]

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

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

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

[39]

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

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

[1]

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

[2]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195

[3]

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

[4]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[5]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[6]

Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135

[7]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182

[8]

Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015

[9]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

[10]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169

[11]

Johannes Kellendonk, Lorenzo Sadun. Conjugacies of model sets. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 3805-3830. doi: 10.3934/dcds.2017161

[12]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[13]

Wenmin Gong, Guangcun Lu. On coupled Dirac systems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (8) : 4329-4346. doi: 10.3934/dcds.2017185

[14]

Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810

[15]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161

[16]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[17]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[18]

Graziano Crasta, Philippe G. LeFloch. Existence result for a class of nonconservative and nonstrictly hyperbolic systems. Communications on Pure & Applied Analysis, 2002, 1 (4) : 513-530. doi: 10.3934/cpaa.2002.1.513

[19]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451

[20]

Khosro Sayevand, Valeyollah Moradi. A robust computational framework for analyzing fractional dynamical systems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021022

2019 Impact Factor: 0.734

Article outline

[Back to Top]