Geodesic
Estimates of the neighborhood volumes of binary codes via their weight spectra
Matematičeskie voprosy kriptografii, Tome 4 (2013) no. 2, pp. 17-42 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We obtain two-sided estimates for the number of elements in the $r$-neighborhood of a code via the spectrum of distances between codewords. For the first and second order Reed–Muller codes the estimates are more explicit. A short review of codes with known distance spectrum is given and some applications of the coding theory to cryptography are discussed. 
@article{MVK_2013_4_2_a1,
     author = {A. A. Serov},
     title = {Estimates of the neighborhood volumes of binary codes via their weight spectra},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {17--42},
     year = {2013},
     volume = {4},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2013_4_2_a1/}
}
TY  - JOUR
AU  - A. A. Serov
TI  - Estimates of the neighborhood volumes of binary codes via their weight spectra
JO  - Matematičeskie voprosy kriptografii
PY  - 2013
SP  - 17
EP  - 42
VL  - 4
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2013_4_2_a1/
LA  - ru
ID  - MVK_2013_4_2_a1
ER  - 
%0 Journal Article
%A A. A. Serov
%T Estimates of the neighborhood volumes of binary codes via their weight spectra
%J Matematičeskie voprosy kriptografii
%D 2013
%P 17-42
%V 4
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2013_4_2_a1/
%G ru
%F MVK_2013_4_2_a1
A. A. Serov. Estimates of the neighborhood volumes of binary codes via their weight spectra. Matematičeskie voprosy kriptografii, Tome 4 (2013) no. 2, pp. 17-42. http://geodesic.mathdoc.fr/item/MVK_2013_4_2_a1/

[1] Agrell E., Vardy A., Zeger K., “Upper bounds for constant-weight codes”, IEEE Trans. Inf. Theory, 46:7 (2000), 2373–2395 | DOI | MR | Zbl

[2] Alfers D., Dinges H., “A normal approximation for Beta and Gamma tail probabilities”, Z. Wahrscheinlichkeitstheorie verw. Gebiete, 65 (1984), 399–420 | DOI | MR | Zbl

[3] Bocharova I., Hug F., Johannesson R., Kudryashov B. D., “On wieght enumerators and MacWilliams identity for convolutional codes”, Theor. Informatics and Appl., ITA, 2010

[4] Caragiu M., “On a class of constant weight codes”, Electr. J. Combinatorics, 3 (1996), Research Paper 4 | MR | Zbl

[5] Ding C., Yang J., Hamming weights in irreducible cyclic codes, 2011, 15 pp., arXiv: 1108.3887 | MR

[6] Doumen J. M., Some Applications of Coding Theory in Cryptography, PhD thesis, Eindhoven Univ. technology, 2003 | MR

[7] Gupta M. K., On some linear codes over $Z_{2^s}$, PhD Diss., Indian Inst. Technology, Kanpur, 1999

[8] Hammons A., Kumar P. V., Calderbank A. R., Sloane N. J. A., Sole P., “The $Z_4$-linearity of Kerdock, Preparata, Goethals and related codes”, IEEE Trans. Inform. Theory, 40 (1994), 301–319 | DOI | MR | Zbl

[9] Helleseth T., “Codes over $Z_4$”, Lect. Notes Comput. Sci., 2122, 2001, 47–55 | DOI | MR | Zbl

[10] Johansson T., Jonsson F., “Fast correlation attacks based on turbo code techniques”, Lect. Notes Comput. Sci., 1666, 1999, 181–197 | DOI | Zbl

[11] Johansson T., Jonsson F., “Improved fast correlation attacks on stream ciphers via convolutional codes”, Lect. Notes Comput. Sci., 1592, 1999, 347–362 | DOI | Zbl

[12] Jurrius R., Pellikaan R., Codes, arrangements and weight enumerators, Dept. of Math. and Comput. Sci., Coding and Crypto Group, The Netherlands, 2009 | MR

[13] Kerdock A. M., “A class of low-rate nonlinear binary code”, Inform. Contr., 20 (1972), 182–187 | DOI | MR | Zbl

[14] Knudsen L., Preneel B., “Hash functions based on block ciphers and quaternary codes”, ASIACRYPT 1996, Lect. Notes Comput. Sci., 1163, 1996, 77–90 | DOI | MR | Zbl

[15] Laywine C. F., Mullen G. L., Discrete mathematics using Latin squares, Wiley, 1998, 326 pp. | MR | Zbl

[16] Linial N., Samorodnitsky A., “Linear codes and character sums”, Combinatorica, 2002, 497–522 | DOI | MR | Zbl

[17] MacKay D. J., “A free energy minimization framework for inference problems in modulo 2 arithmetic”, Lect. Notes Comput. Sci., 1008, 1995, 179–195 | DOI | Zbl

[18] Massey J. L., “Some applications of coding theory in cryptography”, Codes and cyphers: cryptography and coding, 4 (1995), 33–47 | MR

[19] Matsumoto R., Kurosawa K. et al., “Primal-dual distance bounds of linear codes with application to cryptography”, Inf. Theory, 52:9 (2006), 4251–4256 | DOI | MR

[20] McEliece R. J., “A public-key cryptosystem based on algebraic coding theory”, DSN Progress Report, 1978, 42–44

[21] Meier W., Staffelbach O., “Fast correlation attacks on stream ciphers”, Lect. Notes Comput. Sci., 330, 1988, 301–314 | DOI | MR

[22] Meier W., Staffelbach O., “Fast correlation attacks on certain stream ciphers”, J. Cryptology, 1 (1989), 159–176 | DOI | MR | Zbl

[23] Montemanni R., Smith D. H., Heuristic construction of constant weight binary codes, Techn. Rep. No. IDSIA-12-07

[24] Navon M., Samorodnitsky A., “Linear programming bounds for codes via a covering argument”, Discr. Comput. Geometry, 41:2 (2009), 199–207 | DOI | MR | Zbl

[25] Niederreiter H., “Knapsack-type cryptosystems and algebraic coding theory”, Probl. upravl. i teorii inf., 15:2 (1986), 159–166 | MR | Zbl

[26] Perry P. N., Fossorier M. P., “The average value for the probability of an undetected error”, IEEE Trans. Inf. Theory, 54:5 (2008), 2372–2375 | DOI | MR

[27] Patterson N. J., “The algeraic dedoding of Goppa codes”, IEEE Trans. Inf. Theory, 21 (1975), 203–207 | DOI | MR | Zbl

[28] Preparata F. P., “A class of optimum nonlinear double-error correcting codes”, Inform. Contr., 13 (1968), 378–400 | DOI | MR | Zbl

[29] Rains E. M., “Optimal self-dual codes over $\mathbb Z_4$”, Discrete Math., 203 (1999), 215–228 | DOI | MR | Zbl

[30] Reed I. S., “A class of multiple-error-correcting codes and the decoding scheme”, IRE Trans. Inform. Theory, 1954, 38–49 | MR

[31] Sharma A., Bakshi G. K., “The weight distribution of some irreducible cyclic codes”, Finite Fields and Their Appl., 18:1 (2012), 144–159 | DOI | MR | Zbl

[32] Shiromoto K., “The weight enumerator of linear codes over $GF(q^m)$ having generator matrix over $GF(q)$”, Des., Codes and Cryptography, 16:1 (1999), 87–92 | DOI | MR | Zbl

[33] Siap I., “The complete weight enumerator for codes over $\mathcal M_{n\times s}(\mathbb F_q)$”, IMA Int. Conf., 2001, 20–26 | MR | Zbl

[34] Smith D. H., Hughes L. A., Perkins S., “A new table of constant weight codes of length greater than 28”, J. Combinatorics, 13:1 (2006), Article 2 | MR | Zbl

[35] Stinson D. R., Massey J. L., “An infinite class of counterexamples to a conjecture concerning non-linear resilient functions”, J. Cryptology, 8:3 (1995), 167–173 | DOI | MR | Zbl

[36] M. Abramovits, I. Stigan (red.), Spravochnik po spetsialnym funktsiyam, Nauka, M., 1979, 831 pp. | MR

[37] Bleikhut R., Teoriya i praktika kodov, kontroliruyuschikh oshibki, Mir, M., 1986 | MR

[38] Zinovev V. A., Khelleset T., “O vesovykh spektrakh sdvigov kodov tipa Getalsa”, Problemy peredachi informatsii, 40:2 (2004), 19–36 | MR | Zbl

[39] Zubkov A. M., Serov A. A., “Otsenki chisla bulevykh funktsii, imeyuschikh affinnye priblizheniya zadannoi tochnosti”, Diskretnaya matematika, 22:4 (2010), 3–19 | DOI | MR | Zbl

[40] Zubkov A. M., Serov A. A., “Polnoe dokazatelstvo universalnykh neravenstv dlya funktsii raspredeleniya binomialnogo zakona”, Teor. veroyatn. i primen., 57:3 (2012), 597–602 | DOI

[41] Lloid S. P., “Binarnoe blochnoe kodirovanie”, Kiberneticheskii sb., 1, Izd-vo inostr lit., M., 1960, 206–226

[42] Mak-Vilyams F. Dzh., Sloen N. Dzh. A., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979

[43] Serov A. A., Otsenki raspredelenii rasstoyanii ot sluchainoi bulevoi funktsii do affinnykh i kvadratichnykh funktsii, Kandidatskaya dissertatsiya, MIAN, M., 2011, 87 pp.

[44] Serov A. A., “Otsenki chisla bulevykh funktsii, imeyuschikh kvadratichnye priblizheniya zadannoi tochnosti”, Diskretnaya matematika, 24:3 (2012), 90–107 | DOI | MR | Zbl

[45] Sidelnikov V. M., Teoriya kodirovaniya, FIZMATLIT, M., 2008, 324 pp.

[46] Sidelnikov V. M., “O spektre vesov dvoichnykh kodov Bouza–Choudkhuri–Khokvingema”, Problemy peredachi informatsii, 7:1 (1971), 14–22 | MR | Zbl

[47] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 1, Mir, M., 1984 | MR | Zbl

[48] Shapiro G. S, Zlotnik D. L., “K matematicheskoi teorii kodov s ispravleniem oshibok”, Kiberneticheskii sb., 5, Izd-vo inostr. lit., M., 1962, 7–32