1 | 15 | 15 |
2 | 19 | 19 |
3 | 20 | 22 |
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 [
Citation: |
Table 1.
1 | 15 | 15 |
2 | 19 | 19 |
3 | 20 | 22 |
Table 2.
1 | 10 | 10 |
2 | 14 | 14 |
3 | 15 | 17 |
4 | 18 | 19 |
Table 3.
1 | 5 | 5 |
2 | 9 | 9 |
3 | 10 | 12 |
4 | 13 | 14 |
5 | 14 | 15 |
Table 4.
1 | 4 | 4 |
2 | 5 | 7 |
3 | 8 | 9 |
4 | 9 | 10 |
Table 5.
1 | 3 | 3 |
2 | 4 | 5 |
3 | 5 | 6 |
Table 6.
The special case
m | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
0 | 0 | 14 | 15 | 29 | 43 | 45 | 59 | 73 | 87 | 90 | 104 | 118 | 132 | 146 | 150 | |
16 | 31 | 46 | 61 | 76 | 91 | 106 | 121 | 136 | 151 | 166 | 181 | 196 | 211 | 226 | 241 |
Table 7.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
6 | 12 | 17 | 21 | 24 | 26 | 27 | |
6 | 7 | 13 | 14 | 15 | 20 | 21 | |
22 | 24 | 27 | 31 | 36 | 42 | 49 | |
28 | 33 | 34 | 35 | 41 | 42 | 49 |
Table 8.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
5 | 6 | 11 | 12 | 16 | 17 | 20 | 21 | 23 | 24 | 25 | 26 | 27 | |
5 | 6 | 7 | 12 | 13 | 14 | 15 | 19 | 20 | 21 | 22 | 23 | 26 | |
16 | 17 | 19 | 20 | 23 | 24 | 28 | 29 | 34 | 35 | 41 | 42 | 49 | |
19 | 20 | 21 | 25 | 26 | 27 | 28 | 33 | 34 | 35 | 41 | 42 | 49 |
Table 9.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | |
5 | 10 | 14 | 17 | 19 | 20 | |
5 | 6 | 7 | 12 | 13 | 14 | |
16 | 19 | 23 | 28 | 34 | 41 | |
25 | 26 | 27 | 33 | 34 | 41 |
Table 10.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
4 | 5 | 9 | 10 | 13 | 14 | 16 | 17 | 18 | 19 | 20 | |
4 | 5 | 6 | 7 | 11 | 12 | 13 | 14 | 15 | 18 | 19 | |
11 | 12 | 15 | 16 | 20 | 21 | 26 | 27 | 33 | 34 | 41 | |
13 | 17 | 18 | 19 | 20 | 25 | 26 | 27 | 33 | 34 | 41 |
Table 11.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
3 | 4 | 5 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
3 | 4 | 5 | 6 | 7 | 10 | 11 | 12 | 13 | 14 | 15 | 17 | 18 | 19 | 20 | |
7 | 8 | 9 | 12 | 13 | 14 | 18 | 19 | 20 | 25 | 26 | 27 | 33 | 34 | 41 | |
9 | 10 | 11 | 12 | 13 | 17 | 18 | 19 | 20 | 25 | 26 | 27 | 33 | 34 | 41 |
Table 12.
Scheme based on
1 | 2 | 3 | 4 | 5 | |
4 | 8 | 11 | 13 | 14 | |
4 | 5 | 6 | 7 | 11 | |
11 | 15 | 20 | 26 | 33 | |
18 | 19 | 25 | 26 | 33 |
Table 13.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
14 | 28 | 41 | 53 | 64 | 74 | 83 | 91 | 98 | 104 | 109 | 113 | 116 | 118 | 119 | |
14 | 15 | 29 | 30 | 31 | 44 | 45 | 46 | 47 | 59 | 60 | 61 | 62 | 63 | 74 | |
106 | 108 | 111 | 115 | 120 | 126 | 133 | 141 | 150 | 160 | 171 | 183 | 196 | 210 | 225 | |
161 | 162 | 163 | 164 | 165 | 177 | 178 | 179 | 180 | 193 | 194 | 195 | 209 | 210 | 225 |
Table 14.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
13 | 26 | 38 | 49 | 59 | 68 | 76 | 83 | 89 | 94 | 98 | 101 | 103 | 104 | |
13 | 14 | 15 | 28 | 29 | 30 | 31 | 43 | 44 | 45 | 46 | 47 | 58 | 59 | |
92 | 95 | 99 | 104 | 110 | 117 | 125 | 134 | 144 | 155 | 167 | 180 | 194 | 209 | |
146 | 147 | 148 | 149 | 161 | 162 | 163 | 164 | 177 | 178 | 179 | 193 | 194 | 209 |
Table 15.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
12 | 24 | 35 | 45 | 54 | 62 | 69 | 75 | 80 | 84 | 87 | 89 | 90 | |
12 | 13 | 14 | 15 | 27 | 28 | 29 | 30 | 31 | 42 | 43 | 44 | 45 | |
79 | 83 | 88 | 94 | 101 | 109 | 118 | 128 | 139 | 151 | 164 | 178 | 193 | |
131 | 132 | 133 | 145 | 146 | 147 | 148 | 161 | 162 | 163 | 177 | 178 | 193 |
Table 16.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
11 | 22 | 32 | 41 | 49 | 56 | 62 | 67 | 71 | 74 | 76 | 77 | |
11 | 12 | 13 | 14 | 15 | 26 | 27 | 28 | 29 | 30 | 31 | 41 | |
67 | 72 | 78 | 85 | 93 | 102 | 112 | 123 | 135 | 148 | 162 | 177 | |
116 | 117 | 129 | 130 | 131 | 132 | 145 | 146 | 147 | 161 | 162 | 177 |
Table 17.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
10 | 20 | 29 | 37 | 44 | 50 | 55 | 59 | 62 | 64 | 65 | |
10 | 11 | 12 | 13 | 14 | 15 | 25 | 26 | 27 | 28 | 29 | |
56 | 62 | 69 | 77 | 86 | 96 | 107 | 119 | 132 | 146 | 161 | |
101 | 113 | 114 | 115 | 116 | 129 | 130 | 131 | 145 | 146 | 161 |
Table 18.
Scheme based on
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
9 | 18 | 26 | 33 | 39 | 44 | 48 | 51 | 53 | 54 | |
9 | 10 | 11 | 12 | 13 | 14 | 15 | 24 | 25 | 26 | |
46 | 53 | 61 | 70 | 80 | 91 | 103 | 116 | 130 | 145 | |
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
![]() |