Article Contents
Article Contents

# Relative generalized Hamming weights of q-ary Reed-Muller codes

The authors are supported by the Danish National Research Foundation and the National Natural Science Foundation of China (Grant No. 11061130539) and The Danish Council for Independent Research (Grant No. DFF–4002-00367).
• Coset constructions of q-ary Reed-Muller codes can be used to store secrets on a distributed storage system in such a way that only parties with access to a large part of the system can obtain information while still allowing for local error-correction. In this paper we determine the relative generalized Hamming weights of these codes which can be translated into a detailed description of the information leakage [2,21,18,9]

Mathematics Subject Classification: Primary: 94A62, 94B65, 68P20; Secondary: 94B27.

 Citation:

• Figure 1.  Calculation of GHWs and RGHWs for $C_1={\mbox{RM}}_5(5, 2)$ and $C_2={\mbox{RM}}_5(3, 2)$

Figure 2.  The recursive algorithm VECA. We use the notation $((\beta_1, \ldots , \beta_{\kappa-1}), \beta_\kappa)=(\beta_1, \ldots , \beta_{\kappa-1}, \beta_\kappa)$ for concatenation

Figure 3.  The algorithm RHO

Table 1.  $C_1={\mbox{RM}}_5(2, 2), C_2={\mbox{RM}}_5(1, 2)$

 $r=m$ $d_r(C_1)$ $M_m(C_1, C_2)$ 1 15 15 2 19 19 3 20 22

Table 2.  $C_1={\mbox{RM}}_5(3, 2), C_2={\mbox{RM}}_5(2, 2)$

 $r=m$ $d_r(C_1)$ $M_m(C_1, C_2)$ 1 10 10 2 14 14 3 15 17 4 18 19

Table 3.  $C_1={\mbox{RM}}_5(4, 2), C_2={\mbox{RM}}_5(3, 2)$

 $r=m$ $d_r(C_1)$ $M_m(C_1, C_2)$ 1 5 5 2 9 9 3 10 12 4 13 14 5 14 15

Table 4.  $C_1={\mbox{RM}}_5(5, 2), C_2={\mbox{RM}}_5(4, 2)$

 $r=m$ $d_r(C_1)$ $M_m(C_1, C_2)$ 1 4 4 2 5 7 3 8 9 4 9 10

Table 5.  $C_1={\mbox{RM}}_5(6, 2), C_2={\mbox{RM}}_5(5, 2)$

 $r=m$ $d_r(C_1)$ $M_m(C_1, C_2)$ 1 3 3 2 4 5 3 5 6

Table 6.  The special case $u_2=q-2$ and $t=1$ with $q=16$. That is, $C_1={\mbox{RM}}_{16}(15, 2)$ and $C_2={\mbox{RM}}_{16}(14, 2)$. The function ${\mbox{diff}}(m)$ equals $M_m(C_1, C_2)-d_m(C_1)$

 m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ${\mbox{diff}}(m)$ 0 0 14 15 29 43 45 59 73 87 90 104 118 132 146 150 $M_m(C_1, C_2)$ 16 31 46 61 76 91 106 121 136 151 166 181 196 211 226 241

Table 7.  Scheme based on $C_1 = RM_8(6, 2)$ and $C_2 = RM_8(5, 2)$. For local error-correction 7 queries are needed

 $m$ 1 2 3 4 5 6 7 $t_m$ 6 12 17 21 24 26 27 $t_m^\prime$ 6 7 13 14 15 20 21 $r_m$ 22 24 27 31 36 42 49 $r_m^\prime$ 28 33 34 35 41 42 49

Table 8.  Scheme based on $C_1 = RM_8(6, 2)$ and $C_2 = RM_8(4, 2)$. For local error-correction 7 queries are needed

 $m$ 1 2 3 4 5 6 7 8 9 10 11 12 13 $t_m$ 5 6 11 12 16 17 20 21 23 24 25 26 27 $t_m^\prime$ 5 6 7 12 13 14 15 19 20 21 22 23 26 $r_m$ 16 17 19 20 23 24 28 29 34 35 41 42 49 $r_m^\prime$ 19 20 21 25 26 27 28 33 34 35 41 42 49

Table 9.  Scheme based on $C_1 = RM_8(5, 2)$ and $C_2 = RM_8(4, 2)$. For local error-correction 6 or 7 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 6 $t_m$ 5 10 14 17 19 20 $t_m^\prime$ 5 6 7 12 13 14 $r_m$ 16 19 23 28 34 41 $r_m^\prime$ 25 26 27 33 34 41

Table 10.  Scheme based on $C_1 = RM_8(5, 2)$ and $C_2 = RM_8(3, 2)$. For local error-correction 6 or 7 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 6 7 8 9 10 11 $t_m$ 4 5 9 10 13 14 16 17 18 19 20 $t_m^\prime$ 4 5 6 7 11 12 13 14 15 18 19 $r_m$ 11 12 15 16 20 21 26 27 33 34 41 $r_m^\prime$ 13 17 18 19 20 25 26 27 33 34 41

Table 11.  Scheme based on $C_1 = RM_8(5, 2)$ and $C_2 = RM_8(2, 2)$. For local error-correction 6 or 7 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 $t_m$ 3 4 5 8 9 10 12 13 14 15 16 17 18 19 20 $t_m^\prime$ 3 4 5 6 7 10 11 12 13 14 15 17 18 19 20 $r_m$ 7 8 9 12 13 14 18 19 20 25 26 27 33 34 41 $r_m^\prime$ 9 10 11 12 13 17 18 19 20 25 26 27 33 34 41

Table 12.  Scheme based on $C_1 = RM_8(4, 2)$ and $C_2 = RM_8(3, 2)$. For local error-correction 5 or 7 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 $t_m(RGHW)$ 4 8 11 13 14 $t_m(GHW)$ 4 5 6 7 11 $r_m(RGHW)$ 11 15 20 26 33 $r_m(GHW)$ 18 19 25 26 33

Table 13.  Scheme based on $C_1 = RM_{16}(14, 2)$ and $C_2 = RM_{16}(13, 2)$. For local error-correction 15 queries are needed

 $m$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 $t_m$ 14 28 41 53 64 74 83 91 98 104 109 113 116 118 119 $t_m^\prime$ 14 15 29 30 31 44 45 46 47 59 60 61 62 63 74 $r_m$ 106 108 111 115 120 126 133 141 150 160 171 183 196 210 225 $r_m^\prime$ 161 162 163 164 165 177 178 179 180 193 194 195 209 210 225

Table 14.  Scheme based on $C_1 = RM_{16}(13, 2)$ and $C_2 = RM_{16}(12, 2)$. For local error-correction 14 or 15 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 $t_m$ 13 26 38 49 59 68 76 83 89 94 98 101 103 104 $t_m^\prime$ 13 14 15 28 29 30 31 43 44 45 46 47 58 59 $r_m$ 92 95 99 104 110 117 125 134 144 155 167 180 194 209 $r_m^\prime$ 146 147 148 149 161 162 163 164 177 178 179 193 194 209

Table 15.  Scheme based on $C_1 = RM_{16}(12, 2)$ and $C_2 = RM_{16}(11, 2)$. For local error-correction 13 or 15 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 6 7 8 9 10 11 12 13 $t_m$ 12 24 35 45 54 62 69 75 80 84 87 89 90 $t_m^\prime$ 12 13 14 15 27 28 29 30 31 42 43 44 45 $r_m$ 79 83 88 94 101 109 118 128 139 151 164 178 193 $r_m^\prime$ 131 132 133 145 146 147 148 161 162 163 177 178 193

Table 16.  Scheme based on $C_1 = RM_{16}(11, 2)$ and $C_2 = RM_{16}(10, 2)$. For local error-correction 12 or 15 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 6 7 8 9 10 11 12 $t_m$ 11 22 32 41 49 56 62 67 71 74 76 77 $t_m^\prime$ 11 12 13 14 15 26 27 28 29 30 31 41 $r_m$ 67 72 78 85 93 102 112 123 135 148 162 177 $r_m^\prime$ 116 117 129 130 131 132 145 146 147 161 162 177

Table 17.  Scheme based on $C_1 = RM_{16}(10, 2)$ and $C_2 = RM_{16}(9, 2)$. For local error-correction 11 or 15 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 6 7 8 9 10 11 $t_m$ 10 20 29 37 44 50 55 59 62 64 65 $t_m^\prime$ 10 11 12 13 14 15 25 26 27 28 29 $r_m$ 56 62 69 77 86 96 107 119 132 146 161 $r_m^\prime$ 101 113 114 115 116 129 130 131 145 146 161

Table 18.  Scheme based on $C_1 = RM_{16}(9, 2)$ and $C_2 = RM_{16}(8, 2)$. For local error-correction 10 or 15 queries are needed, depending on the error-probability

 $m$ 1 2 3 4 5 6 7 8 9 10 $t_m$ 9 18 26 33 39 44 48 51 53 54 $t_m^\prime$ 9 10 11 12 13 14 15 24 25 26 $r_m$ 46 53 61 70 80 91 103 116 130 145 $r_m^\prime$ 97 98 99 100 113 114 115 129 130 145
•  [1] H. E. Andersen and O. Geil, Evaluation codes from order domain theory, Finite Fields Appl., 14 (2008), 92-123.  doi: 10.1016/j.ffa.2006.12.004. [2] T. Bains, Generalized Hamming Weights and Their Applications to Secret Sharing Schemes Master's thesis, Univ. Amsterdam, 2008. [3] S. L. Bezrukov and U. Leck, Macaulay posets Electr. J. Combin. 1000 (2005), DS12. [4] H. Chen, R. Cramer, S. Goldwasser, R. De Haan and V. Vaikuntanathan, Secure computation from random error correcting codes, in Adv. Crypt. -EUROCRYPT 2007, Springer, 2007, 291–310. doi: 10.1007/978-3-540-72540-4_17. [5] D. A. Cox, J. Little and D. O'Shea, Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra 3rd edition, Springer, 2012. doi: 10.1007/978-1-4757-2181-2. [6] I. Duursma and J. Shen, Multiplicative secret sharing schemes from Reed-Muller type codes, in Proc. 2012 IEEE Int. Symp. Inf. Theory (ISIT), IEEE, 2012,264–268. [7] O. Geil, S. Martin, U. Martí nez-Peñas, R. Matsumoto and D. Ruano, On asymptotically good ramp secret sharing schemes preprint, arXiv: 1502.05507 [8] O. Geil, S. Martin, U. Martí nez-Peñas and D. Ruano, Refined analysis of RGHWs of code pairs coming from Garcia-Stichtenoths second tower J. Algebra Comb. Discrete Struct. Appl. to appear. doi: 10.13069/jacodesmath.34390. [9] O. Geil, S. Martin, R. Matsumoto, D. Ruano and Y. Luo, Relative generalized Hamming weights of one-point algebraic geometric codes, IEEE Trans. Inf. Theory, 60 (2014), 5938-5949.  doi: 10.1109/TIT.2014.2345375. [10] O. Geil, R. Matsumoto and D. Ruano, Feng–Rao decoding of primary codes, Finite Fields Appl., 23 (2013), 35-52.  doi: 10.1016/j.ffa.2013.03.005. [11] P. Heijnen, Some Classes of Linear Codes Ph. D thesis, Technische Universiteit Eindhoven, 1999. [12] P. Heijnen and R. Pellikaan, Generalized Hamming weights of q-ary Reed-Muller codes in IEEE Trans. Inform. Theory Citeseer, 1998. doi: 10.1109/18.651015. [13] T. Helleseth, T. Kløve and J. Mykkeltveit, The weight distribution of irreducible cyclic codes with block lengths $n_1((q^l- 1)/n)$, Discr. Math., 18 (1077), 179-211.  doi: 10.1016/0012-365X(77)90078-4. [14] T. Høholdt, On (or in) Dick Blahut's footprint, Codes, Curves and Signals (ed. A. Vardy), Kluwer Acad. Publ. , 1998, 3–9. doi: 10.1007/978-1-4615-5121-8_1. [15] J. Katz and L. Trevisan, On the efficiency of local decoding procedures for error-correcting codes, in Proc. 32nd Ann. ACM Symp. Theory Comp. , ACM, 2000, 80–86. doi: 10.1145/335305.335315. [16] T. Kløve, The weight distribution of linear codes over $GF(q^l)$ having generator matrix over $GF(q)^*$, Discr. Math., 23 (1978), 159-168.  doi: 10.1016/0012-365X(78)90114-0. [17] N. Koblitz, A Course in Number Theory and Cryptography Springer, 1994. doi: 10.1007/978-1-4419-8592-7. [18] J. Kurihara, T. Uyematsu and R. Matsumoto, Secret sharing schemes based on linear codes can be precisely characterized by the relative generalized Hamming weight, IEICE Trans. Fundam. Electr. Commun. Comp. Sci., 95 (2012), 2067-2075. [19] K. Lee, Bounds for generalized Hamming weights of general AG codes, Finite Fields Appl., 34 (2015), 265-279.  doi: 10.1016/j.ffa.2015.02.006. [20] Z. Liu, W. Chen and Y. Luo, The relative generalized Hamming weight of linear $q$-ary codes and their subcodes, Des. Codes Crypt., 48 (2008), 111-123.  doi: 10.1007/s10623-008-9170-1. [21] Y. Luo, C. Mitrpant, A. H. Vinck and K. Chen, Some new characters on the wire-tap channel of type Ⅱ, IEEE Trans. Inf. Theory, 51 (2005), 1222-1229.  doi: 10.1109/TIT.2004.842763. [22] A. B. Sørensen, Projective Reed-Muller codes, IEEE Trans. Inf. Theory, 37 (1991), 1567-1576.  doi: 10.1109/18.104317. [23] M. Tsfasman and S. G. Vladut, Algebraic-Geometric Codes Kluwer Acad. Publ. , 1991. doi: 10.1007/978-94-011-3810-9. [24] V. K. Wei, Generalized Hamming weights for linear codes, IEEE Trans. Inf. Theory, 37 (1991), 1412-1418.  doi: 10.1109/18.133259. [25] A. D. Wyner, The wire-tap channel, Bell System Techn. J., 54 (1975), 1355-1387.  doi: 10.1002/j.1538-7305.1975.tb02040.x. [26] S. Yekhanin, Locally decodable codes, Found. Trends Theor. Comp. Sci., 6 (2010), 139-255.  doi: 10.1561/0400000030. [27] J. Zhang and K. Feng, Relative generalized Hamming weights of cyclic codes preprint, arXiv: 1505.07277

Figures(3)

Tables(18)