Over the past few years, the codes $ {\mathcal{C}}_{n-1}(n,q) $ arising from the incidence of points and hyperplanes in the projective space $ {\rm{PG}}(n,q) $ attracted a lot of attention. In particular, small weight codewords of $ {\mathcal{C}}_{n-1}(n,q) $ are a topic of investigation. The main result of this work states that, if $ q $ is large enough and not prime, a codeword having weight smaller than roughly $ \frac{1}{2^{n-2}}q^{n-1}\sqrt{q} $ can be written as a linear combination of a few hyperplanes. Consequently, we use this result to provide a graph-theoretical sufficient condition for these codewords of small weight to be minimal.
Citation: |
Figure 1. The application of Construction 3.5 to an example codeword $ c\in {\mathcal{C}}_1(2,q) $ of weight $ 9q-12 $. More specifically, we consider nine lines of $ {\rm{PG}}(2,q) $ and define the codeword $ c: = \alpha(a_0-a_1-a_2)+2\alpha\,\widetilde{a}+\beta(b_0-b_1-b_2-b_3)+3\beta\,\widetilde{b} $. For this specific example, we assume $ q $ not prime, $ q \geqslant529 $ if $ h = 2 $ (to be able to apply Result 1.3) and $ q \geqslant125 $, $ p\notin\{2,3,7,11,13\} $, if $ h>2 $. Furthermore, $ \alpha,\beta\in{\mathbb{F}}_q^* $ are two non-zero elements such that $ 3\alpha+4\beta = 0 $. Lines are clustered in four 'stages', each of which consists of 'clustering' the lines by following the rule of thumb described in Construction 3.5. Holes that are about to 'merge' clusters are indicated by squares instead of circles. In the first stage (top left), every line forms its own cluster. In the second stage (top right), the solid bold lines form one cluster, as well as the dashed bold lines; the remaining lines $ \widetilde{a} $ and $ \widetilde{b} $ form two clusters on their own. In the third stage (bottom left), the line $ \widetilde{a} $ gets merged into the solid bold cluster and the line $ \widetilde{b} $ gets merged into the dashed bold cluster. Finally, in the last stage (bottom right), both clusters get merged into one. To explain more clearly how this merging process works, consider the point $ A $ in the second stage. At this stage, $ A $ belongs to both the support of the solid bold line cluster $ \{a_0,a_1,a_2\} $ (with non-zero value $ -2\alpha $) and the support of the cluster $ \{\widetilde{a}\} $ (with non-zero value $ 2\alpha $), and thus meets Property $ 2. $ of Definition 3.4. Moreover, $ A $ is a hole of $ c $, as well as a hole of $ {{c}}_{|{{\mathcal{V}}}} $ for every other cluster (and therefore fulfils Property $ 1. $ and $ 3. $ of Definition 3.4). Hence, the clusters $ \{a_0,a_1,a_2\} $ and $ \{\widetilde{a}\} $ are adjacent and thus will get merged in the next stage as Construction 3.5 prescribes.
[1] | S. Adriaensen and L. Denaux, Small weight codewords of projective geometric codes, J. Combin. Theory Ser. A, 180 (2021), 105395. doi: 10.1016/j.jcta.2020.105395. |
[2] | S. Adriaensen, L. Denaux, L. Storme and Z. Weiner, Small weight code words arising from the incidence of points and hyperplanes in $ \rm PG $$(n,q)$, Des. Codes Cryptogr., 88 (2020), 771-788. doi: 10.1007/s10623-019-00710-0. |
[3] | A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inform. Theory, 44 (1998), 2010-2017. doi: 10.1109/18.705584. |
[4] | E. F. Assmus and J. D. Key, Designs and Their Codes, Cambridge University Press, 1992. doi: 10.1017/CBO9781316529836. |
[5] | B. Bagchi and S. P. Inamdar, Projective geometric codes, J. Combin. Theory Ser. A, 99 (2002), 128-142. doi: 10.1006/jcta.2002.3265. |
[6] | D. Bartoli and M. Bonini, Minimal linear codes in odd characteristic, IEEE Trans. Inform. Theory, 65 (2019), 4152-4155. doi: 10.1109/TIT.2019.2891992. |
[7] | E. Berlekamp, R. McEliece and H. van Tilborg, On the inherent intractability of certain coding problems (corresp.), IEEE Trans. Inform. Theory, 24 (1978), 384-386. doi: 10.1109/tit.1978.1055873. |
[8] | G. R. Blakley, Safeguarding cryptographic keys, International Workshop on Managing Requirements Knowledge (MARK), (1979), 313–317. doi: 10.1109/MARK.1979.8817296. |
[9] | M. Bonini and M. Borello, Minimal linear codes arising from blocking sets, J. Algebraic Combin., 53 (2021), 327-341. doi: 10.1007/s10801-019-00930-6. |
[10] | J. Bruck and M. Naor, The hardness of decoding linear codes with preprocessing, IEEE Trans. Inform. Theory, 36 (1990), 381-385. doi: 10.1109/18.52484. |
[11] | H. Chabanne, G. D. Cohen and A. Patey, Towards secure two-party computation from the wire-tap channel, Information Security and Cryptology – ICISC 2013, 8565 (2014), 34-46. doi: 10.1007/978-3-319-12160-4_3. |
[12] | K. Chouinard, Weight distributions of codes from finite planes, Ph.D thesis, University of Virginia. |
[13] | G. D. Cohen, S. Mesnager and A. Patey, On minimal and quasi-minimal linear codes, Cryptography and Coding, 8308 (2013), 85-98. doi: 10.1007/978-3-642-45239-0_6. |
[14] | C. Ding, Z. Heng and Z. Zhou, Minimal binary linear codes, IEEE Trans. Inform. Theory, 64 (2018), 6536-6545. doi: 10.1109/TIT.2018.2819196. |
[15] | V. Fack, S. L. Fancsali, L. Storme, G. Van de Voorde and J. Winne, Small weight codewords in the codes arising from Desarguesian projective planes, Des. Codes Cryptogr., 46 (2008), 25-43. doi: 10.1007/s10623-007-9126-x. |
[16] | Z. Heng, C. Ding and Z. Zhou, Minimal linear codes over finite fields, Finite Fields Appl., 54 (2018), 176-196. doi: 10.1016/j.ffa.2018.08.010. |
[17] | M. Lavrauw, L. Storme, P. Sziklai and G. Van de Voorde, An empty interval in the spectrum of small weight codewords in the code from points and $k$-spaces of ${\rm{PG}}(n, q)$, J. Combin. Theory Ser. A, 116 (2009), 996-1001. doi: 10.1016/j.jcta.2008.09.004. |
[18] | M. Lavrauw, L. Storme and G. Van de Voorde, Linear codes from projective spaces, Error-Correcting Codes, Finite Geometries and Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 523 (2010), 185–202. doi: 10.1090/conm/523/10326. |
[19] | F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. II, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977 |
[20] | J. L. Massey, Minimal codewords and secret sharing, Proc. 6th Joint Swedish-Russian Int. Workshop on Info. Theory, (1993), 276–279. |
[21] | J. L. Massey, Some applications of coding theory in cryptography, Codes and Cyphers: Cryptography and Coding IV, (1995), 33–47. |
[22] | O. Polverino and F. Zullo, Codes arising from incidence matrices of points and hyperplanes in $ {\rm{PG}}(n, q)$, J. Combin. Theory Ser. A, 158 (2018), 1-11. doi: 10.1016/j.jcta.2018.03.013. |
[23] | L. D. Rudolph, A class of majority logic decodable codes, IEEE Trans. Inform. Theory, 13 (1967), 305–307, www.scopus.com, Cited By : 81. |
[24] | A. Shamir, How to share a secret, Commun. ACM., 22 (1979), 612-613. doi: 10.1145/359168.359176. |
[25] | T. Szőnyi and Z. Weiner, Stability of $k\bmod p$ multisets and small weight codewords of the code generated by the lines of PG(2, $q$), J. Combin. Theory Ser. A, 157 (2018), 321-333. doi: 10.1016/j.jcta.2018.02.005. |
[26] | J. Yuan and C. Ding, Secret sharing schemes from three classes of linear codes, IEEE Trans. Inform. Theory, 52 (2006), 206-212. doi: 10.1109/TIT.2005.860412. |
The application of Construction 3.5 to an example codeword
An example of a codeword