Characteristics of Hadamard square of special Reed~--- Muller subcodes

V. Vysotskaya

Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 75-88.

Résumé

The existence of some structure in a code can lead to the decrease of security of the whole system built on it. Often subcodes are used to “disguise” the code as a “general-looking” one. However, the security of subcodes, whose Hadamard square is equal to the square of the original code, can be reduced to the security of this code. The paper finds the limiting conditions on the number of vectors of degree $ r $ whose removing retains this weakness for Reed — Muller subcodes and, accordingly, conditions for it to vanish. For $ r = 2 $ the exact structure of all resistant subcodes has been found. For an arbitrary code $\mathrm{RM}(r, m) $, the desired number of vectors to remove for providing the security has been estimated from both sides. Finally, the ratio of subcodes with Hadamard square unequal to the square of the original code has been proved to tend to zero if additional conditions on the codimension of the subcode and the parameter $ r $ are imposed and $ m \rightarrow \infty $. Thus, the implementation of checks proposed in the paper helps to immediately filter out some insecure subcodes.

Détail

Keywords: post-quantum cryptography, code-based cryptography, Reed — Muller codes, Reed — Muller subcodes, McEliece cryptosystem.
Mots-clés : Hadamard product

Bibliographie

[1] Shor P. V., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Computing, 26:5 (1997), 1484–1509 | DOI | Zbl

[2] McEliece R. J., “A public-key cryptosystem based on algebraic coding theory”, DSN Progress Report, 4244 (1978), 114–116

[3] Niederreiter H., “Knapsack-type cryptosystems and algebraic coding theory”, Problems Control Inform. Theory, 15:2 (1986), 159–166 | Zbl

[4] NIST Call for Proposals, , 2016 https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Cryptography-Standardization/Call-for-Proposals

[5] Wieschebrink C., “An attack on a modified Niederreiter encryption scheme”, LNCS, 3958, 2006, 14–26 | Zbl

[6] Wieschebrink C., “Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes”, LNCS, 6061, 2010, 61–72 | Zbl

[7] Berger T. P., Loidreau P., “How to mask the structure of codes”, Designs, Codes, Cryptogr., 35:1 (2005), 63–79 | DOI | Zbl

[8] Couvreur A., Marquez-Corbella I., Pellikaan R., “Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes”, Coding Theory Applications, CIM Ser. Math. Sci., 3, 2015, 133–140 | DOI | Zbl

[9] Lee Y., Lee W., Kim Y. S., No J.-S., “Modified pqsigRM: RM code-based signature scheme”, IEEE Access, 8 (2020), 177506–177518 | DOI

[10] Borodin M. A., Chizhov I. V., “Effective attack on the McEliece cryptosystem based on Reed — Muller codes”, Discr. Math. Appl., 24:5 (2014), 273–280 | Zbl

[11] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, LNCS, 4515, 347–360 | Zbl

[12] Chizhov I. V., Borodin M. A., “Hadamard products classification of subcodes of Reed — Muller codes codimension 1”, Discr. Math. Appl., 32:1 (2020), 115–134

[13] Couvreur A., Gaborit P., Gauthier-Umãna V., et al., “Distinguisher-based attacks on public-key cryptosystems using Reed — Solomon codes”, Designs, Codes, Cryptogr., 73:2 (2014), 641–666 | DOI | Zbl

[14] Erdös P., Spencer J., Probabilistic Methods in Combinatorics, Akadèmiai Kiadó, Budapest, 1974, 106 pp. | Zbl

[15] Rödl V., “On a Packing and Covering Problem”, European J. Combinatorics, 6:1 (1985), 69–78 | DOI | Zbl