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

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

Olav Geil; Stefano Martin

doi:10.3934/amc.2017041

Article Contents

2017, Volume 11, Issue 3: 503-531. Doi: 10.3934/amc.2017041

This issue Previous Article Private set intersection: New generic constructions and feasibility results Next Article New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions

$t_m^\prime$

$r_m^\prime$

Olav Geil and
Stefano Martin

Department of Mathematical Sciences, Aalborg University, Fredrik Bajersvej 7G, DK-9220, Aalborg Øst, Denmark

Received: August 31, 2015

Published: September 2017

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).

Abstract Full Text(HTML) Figure(3) / Table(18) Related Papers Cited by

Abstract

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]

Keywords:

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

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 3. The algorithm RHO

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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