×

zbMATH — the first resource for mathematics

Cardinality spectra of components of correlation immune functions, bent functions, perfect colorings, and codes. (English. Russian original) Zbl 1276.06008
Probl. Inf. Transm. 48, No. 1, 47-55 (2012); translation from Probl. Peredachi Inf. 48, No. 1, 54-63 (2012).
Summary: We study cardinalities of components of perfect codes and colorings, correlation-immune functions, and bent functions (sets of ones of these functions). Based on results of Kasami and Tokura, we show that for any of these combinatorial objects the component cardinality in the interval from \(2^k\) to \(2^{k+1}\) can only take values of the form \(2^{k+1}-2^p\), where \(p\in\{0,\dots ,k\}\) and \(2^k\) is the minimum component cardinality for a combinatorial object with the same parameters. For bent functions, we prove existence of components of any cardinality in this spectrum. For perfect colorings with certain parameters and for correlation-immune functions, we find components of some of the above-given cardinalities.
Reviewer: Reviewer (Berlin)

MSC:
06E30 Boolean functions
05C15 Coloring of graphs and hypergraphs
94A60 Cryptography
94B25 Combinatorial codes
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Fon-Der-Flaass, D.G., A Bound on Correlation Immunity, Sib. Elektron. Mat. Izv., 2007, vol. 4, pp. 133–135. · Zbl 1132.05309
[2] Tarannikov, Yu.V., On Correlation-Immune and Stable Boolean Functions, Mat. Vopr. Kibern., vol. 11, Moscow: Fizmatlit, 2002, pp. 91–148. · Zbl 1280.94128
[3] Etzion, T. and Vardy, A., On Perfect Codes and Tilings: Problems and Solutions, SIAM J. Discrete Math., 1998, vol. 11, no. 2, pp. 205–223. · Zbl 0908.94035 · doi:10.1137/S0895480196309171
[4] Avgustinovich, S.V., Heden, O, and Solov’eva, F.I., On Intersections of Perfect Binary Codes, Bayreuth. Math. Schr. 2005, no. 74, pp. 1–6. · Zbl 1100.94027
[5] Avgustinovich, S.V., Heden, O., and Solov’eva, F.I., On Intersection Problem for Perfect Binary Codes, Des. Codes Cryptogr., 2006, vol. 39, no. 3, pp. 317–322. · Zbl 1172.94640 · doi:10.1007/s10623-005-4982-8
[6] Avgustinovich, S.V., Lobstein, A.C., and Solov’eva, F.I., Intersection Matrices for Partitions by Binary Perfect Codes, IEEE Trans. Inform. Theory, 2001, vol. 47, no. 4, pp. 1621–1624. · Zbl 1017.94019 · doi:10.1109/18.923749
[7] Vasil’ev, Yu.L., Avgustinovich, S.V., and Krotov, D.S., On Shifting Sets in the Binary Hypercube, Diskretn. Anal. Issled. Oper., 2008, vol. 15, no. 3, pp. 11–21 [J. Appl. Ind. Math. (Engl. Transl.), 2009, vol. 3, no. 2, pp. 290–296]. · Zbl 1249.94059
[8] Heden, O., Soloveva, F.I., and Mogilnykh, I.Yu., Intersections of Perfect Binary Codes, in Proc. 2010 IEEE Region 8 Int. Conf. on Computational Technologies in Electrical and Electronics Engineering (SIBIRCON), Irkutsk Listvyanka, Russia, 2010. Piscataway: IEEE, 2010, pp. 52–54.
[9] Soloveva, F.I. and Los’, A.V., Intersections of q-ary Perfect Codes, Sibirsk. Mat. Zh., 2008, vol. 49, no. 2, pp. 464–474 [Sib. Math. J. (Engl. Transl.), 2008, vol. 49, no. 2, pp. 375–382].
[10] Kolomeec, N.A. and Pavlov, A.V., Properties of Bent Functions with Minimal Distance, Prikl. Diskr. Mat., 2009, no. 4, pp. 5–20.
[11] Kasami, T. and Tokura, N., On the Weight Structure of Reed-Muller Codes, IEEE Trans. Inform. Theory, 1970, vol. 16, no. 6, pp. 752–759. · Zbl 0205.20604 · doi:10.1109/TIT.1970.1054545
[12] Logachev, O.A., Sal’nikov, A.A., and Yashchenko, V.V., Bulevy funktsii v teorii kodirovaniya i kriptologii (Boolean Functions in Coding Theory and Cryptology), Moscow: MCCME, 2004.
[13] MacWilliams, F.J. and Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977. Translated under the title Teoriya kodov, ispravlyayushchikh oshibki, Moscow: Svyaz’, 1979.
[14] Kasami, T., Tokura, N., and Azumi, S., On the Weight Enumeration of Weights Less than 2.5d of Reed-Muller Codes, Inform. and Control, 1976, vol. 30, no. 4, pp. 380–395. · Zbl 0324.94003 · doi:10.1016/S0019-9958(76)90355-7
[15] Avgustinovich, S.V., private communication (talk given at the Coding Theory seminar, Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences), 2003.
[16] Potapov, V.N., On Perfect Colorings of Boolean n-Cube and Correlation Immune Functions with Small Density, Sib. Elektron. Mat. Izv., 2010, vol. 7, pp. 372–382. · Zbl 1329.05117
[17] Avgustinovich, S.V., Heden, O., and Solov’eva, F.I., The Classification of Some Perfect Codes, Des. Codes Cryptogr., 2004, vol. 31, no. 3, pp. 313–318. · Zbl 1048.94018 · doi:10.1023/B:DESI.0000015891.01562.c1
[18] Phelps, K.T., A General Product Construction for Error Correcting Codes, SIAM J. Algebr. Discrete Methods, 1984, vol. 5, no. 2, pp. 224–228. · Zbl 0546.94015 · doi:10.1137/0605023
[19] Krotov, D.S. and Potapov, V.N., On Switching Equivalence of n-ary Quasigroups of Order 4 and Perfect Binary Codes, Probl. Peredachi Inf., 2010, vol. 46, no. 3, pp. 22–28 [Probl. Inf. Trans. (Engl. Transl.), 2010, vol. 46, no. 3, pp. 219–224].
[20] Potapov, V.N., Latin Bitrade, ArXiv e-print arXiv:1104.1295v1, 2011.
[21] Krotov, D.S. and Potapov, V.N., On Multifold MDS and Perfect Codes That Are Not Splittable into Onefold Codes, Probl. Peredachi Inf., 2004, vol. 40, no. 1, pp. 6–14 [Probl. Inf. Trans. (Engl. Transl.), 2004, vol. 40, no. 1, pp. 5–12]. · Zbl 1083.94022
[22] Fon-Der-Flaas, D.G., Perfect 2-Colorings of a Hypercube, Sibirsk. Mat. Zh., 2007, vol. 48, no. 4, pp. 923–930 [cm[Sib. Math. J. (Engl. Transl.), 2007, vol. 48, no. 4, pp. 740–745]]. · Zbl 1164.05348 · doi:10.1007/s11202-007-0095-0
[23] Sarkar, P., Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions, Cryptology ePrint Archive: Report 2000/049, 2000. Available at http://eprint.iacr.org/2000/049 .
[24] Avgustinovich, S.V. and Vasil’eva, A.Yu., Computation of a Centered Function from Its Values on the Middle Layers of the Boolean Cube, Diskretn. Anal. Issled. Oper., Ser. 1, 2003, vol. 10, no. 2, pp. 3–16. · Zbl 1067.94018
[25] Tokareva, N.N., Bent Functions: Results and Applications. A Survey, Prikl. Diskr. Mat., 2009, no. 1, pp. 15–37.
[26] Carlet, C., Boolean Functions for Cryptography and Error Correcting Codes, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Crama, Y. and Hammer, P.L., Eds., Cambridge: Cambridge Univ. Press, 2010, ch. 8, pp. 257–397. · Zbl 1209.94035
[27] Carlet, C., Two New Classes of Bent Functions, Advances in Cryptology-EUROCRYPT’93. Proc. Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, Helleseth, T., Ed., Lect. Notes Comp. Sci., vol. 765, Berlin: Springer, 1994, pp. 77–101. · Zbl 0951.94542
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.